Magic Giant Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Magic Giant Sudoku

Postby Serg » Wed Jun 10, 2020 12:31 pm

Hi, Mathimagics!
I was wrong saying that Magic Giant Sudoku is just another representation of "traditional" N^4 x N^4 Sudoku. I missed your initial requirement of orthogonality. But I have an idea to try randomly generate MG Sudoku. Say, generate a bunch of 81 x 81 traditional Sudoku and then separate MG Sudoku from those random grids. Probability to find new MG Sudoku grids is rather low, but maybe I'll have a trial ...

Serg
Serg
2018 Supporter
 
Posts: 717
Joined: 01 June 2010
Location: Russia

Re: Magic Giant Sudoku

Postby Mathimagics » Wed Jun 10, 2020 12:51 pm

tarek wrote:When I decided to do this variant I was using DLX.

I also built a DLX solver for this, but moving from MG-16 to MG-81 is a bit like moving from a search space the size of a pea to one the size of Jupiter.

It's fine for tightly constrained puzzles (mostly completed grids), but it really struggles with loosely constrained cases.

For example, the grid construction problem - if I use a complete (81x81) set of givens for the "A grid", and only the first row for the "B grid", and ask it to find any solution it really struggles. The few times I've tried I had to kill it after 24-36 hours.

We have fast ways now to build valid solution grids, which is fine, but I still would like to know whether a solution grid in which the A-grids are all ED is possible or not. I am hoping that SAT will come to the rescue for that particular problem.
Last edited by Mathimagics on Wed Jun 10, 2020 1:02 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1585
Joined: 27 May 2015
Location: Canberra

Re: Magic Giant Sudoku

Postby Mathimagics » Wed Jun 10, 2020 1:00 pm

Serg wrote:Probability to find new MG Sudoku grids is rather low, but maybe I'll have a trial ...

In the absence of any better tools, that might be the only way we are going to find them, so I wish you good luck with your tests!

Meanwhile I'll start working on a SAT approach ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1585
Joined: 27 May 2015
Location: Canberra

Re: Magic Giant Sudoku

Postby tarek » Wed Jun 10, 2020 5:32 pm

My DLX Matrix for 81x81 Sudoku^2 is 65610 columns x 531441 rows so more like the Galaxy Far Far Away not just Jupiter :(

tarek
User avatar
tarek
 
Posts: 3747
Joined: 05 January 2006

Re: Magic Giant Sudoku

Postby Mathimagics » Wed Jun 10, 2020 6:19 pm

Those numbers tally with mine.

Of course, that row count is for a totally blank grid. Here there be dragons ...

With reasonable supply of givens you should need only a fraction of that, say less than 50,000. That does, at least, reduce the memory footprint ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1585
Joined: 27 May 2015
Location: Canberra

Re: Magic Giant Sudoku

Postby Serg » Wed Jun 10, 2020 8:14 pm

Hi, Mathimagics!
I tried to find MG Sudoku 81x81 by random search ... No MGS were found among 10^9 random 81x81 ordinary Sudoku solution grids. Random search is useless in this case.

Serg
Serg
2018 Supporter
 
Posts: 717
Joined: 01 June 2010
Location: Russia

Re: Magic Giant Sudoku

Postby Mathimagics » Thu Jun 11, 2020 10:00 am

Mathimagics wrote:Here is a 4 x 4 box that might be part of a 16 x 16 orthog pair grid:
Code: Select all
14 B9 AB 63
A3 6B 19 B4
BB 13 64 A9
69 A4 B3 1B

I can't believe I actually said that! :?

Call the symbol pairs A and B. By definition, in every 4x4 box, both A and B must each have 16 different values, doh! :roll:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1585
Joined: 27 May 2015
Location: Canberra

Re: Magic Giant Sudoku

Postby Mathimagics » Fri Jun 12, 2020 3:37 am

Mathimagics wrote: ... moving from MG-16 to MG-81 is a bit like moving from a search space the size of a pea to one the size of Jupiter.

I call this combinatorial explosion "P2P" (pea-to-planet) syndrome.

Another case where P2P is evident, sadly, is in what I thought might not be too hard - finding a pair of Orthogonal 16 x 16 Sudoku's.

Finding OPs (orthog pairs) with 9 x 9 grids is done very easily - enumerate the transversals, look for a set of 9 that are mutually disjoint (ie that hit every cell).

The average number of transversals for 9 x 9 Sudoku is just 21 (the absolute maximum is 279). You can find ALL orthog pairs for a batch of 10,000 grids in just a few seconds.

But, among the few 16 x 16 grids that I have tested, there is an average of 500,000 transversals! :shock:

Finding just one subset of 16 disjoint transversals among this huge pool is, inevitably, very, very hard ... none of these tests have run to completion, even after many hours. :(

[Note: we need one example of a pair of orthog 16 x 16 Sudoku's in order to construct an MG-256]
User avatar
Mathimagics
2017 Supporter
 
Posts: 1585
Joined: 27 May 2015
Location: Canberra

Re: Magic Giant Sudoku

Postby Mathimagics » Sat Jun 13, 2020 9:46 am

I have found not one, but two cases of OS16's (pairs of orthogonal 16 x 16 Sudokus)

Finding them by searching was simply too hard, :? ... so I tried to find a way to build one directly, and hey, presto, it worked! 8-)

Grid pairs AB can be formed this way for grids A that have repeating mini-rows, ie MC grid or its close relatives.

Code: Select all
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
 | 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |    | 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F | A[r1]
 | 8 9 A B | C D E F | 0 1 2 3 | 4 5 6 7 |    | 4 5 6 7 | 0 1 2 3 | C D E F | 8 9 A B | A[r3]
 | 4 5 6 7 | 0 1 2 3 | C D E F | 8 9 A B |    | 9 8 B A | D C F E | 1 0 3 2 | 5 4 7 6 | swapX(A[r2])
 | C D E F | 8 9 A B | 4 5 6 7 | 0 1 2 3 |    | D C F E | 9 8 B A | 5 4 7 6 | 1 0 3 2 | swapX(A[r4])
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
 | 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E |    | 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C | swapY(A[r5])
 | B 8 9 A | F C D E | 3 0 1 2 | 7 4 5 6 |    | 5 6 7 4 | 1 2 3 0 | D E F C | 9 A B 8 | swapY(A[r7])
 | 7 4 5 6 | 3 0 1 2 | F C D E | B 8 9 A |    | 8 B A 9 | C F E D | 0 3 2 1 | 4 7 6 5 | swapX(A[r6])
 | F C D E | B 8 9 A | 7 4 5 6 | 3 0 1 2 |    | C F E D | 8 B A 9 | 4 7 6 5 | 0 3 2 1 | swapX(A[r8])
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
 | 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D |    | 6 7 4 5 | 2 3 0 1 | E F C D | A B 8 9 | A[r11]
 | A B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |    | 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D | A[r9]
 | 6 7 4 5 | 2 3 0 1 | E F C D | A B 8 9 |    | F E D C | B A 9 8 | 7 6 5 4 | 3 2 1 0 | swapX(A[r12])
 | E F C D | A B 8 9 | 6 7 4 5 | 2 3 0 1 |    | B A 9 8 | F E D C | 3 2 1 0 | 7 6 5 4 | swapX(A[r10])
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
 | 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C |    | 7 4 5 6 | 3 0 1 2 | F C D E | B 8 9 A | swapY(A[r15])
 | 9 A B 8 | D E F C | 1 2 3 0 | 5 6 7 4 |    | 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E | swapY(A[r13])
 | 5 6 7 4 | 1 2 3 0 | D E F C | 9 A B 8 |    | E D C F | A 9 8 B | 6 5 4 7 | 2 1 0 3 | swapX(A[r16])
 | D E F C | 9 A B 8 | 5 6 7 4 | 1 2 3 0 |    | A 9 8 B | E D C F | 2 1 0 3 | 6 5 4 7 | swapX(A[r14])
 +---------+---------+---------+---------+    +---------+---------+---------+---------+

1-line grids: Show
Code: Select all
0123456789ABCDEF89ABCDEF0123456745670123CDEF89ABCDEF89AB4567012330127456B89AFCDEB89AFCDE3012745674563012FCDEB89AFCDEB89A7456301223016745AB89EFCDAB89EFCD2301674567452301EFCDAB89EFCDAB8967452301123056749AB8DEFC9AB8DEFC1230567456741230DEFC9AB8DEFC9AB856741230
0123456789ABCDEF45670123CDEF89AB98BADCFE10325476DCFE98BA54761032123056749AB8DEFC56741230DEFC9AB88BA9CFED03214765CFED8BA94765032167452301EFCDAB8923016745AB89EFCDFEDCBA9876543210BA98FEDC3210765474563012FCDEB89A30127456B89AFCDEEDCFA98B65472103A98BEDCF21036547

The annotations show how grid B is built from the rows of grid A. swapX is the swapping of columns pairwise in the row, eg c1234 -> c2143, and swapY swaps the pairs in each mini-row, eg c1234 -> c3412, etc.

What is really interesting that the very same "recipe" works again with a slightly different grid A:

Example 2: Show
Code: Select all
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
 | 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |    | 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
 | 4 5 6 7 | 8 9 A B | C D E F | 0 1 2 3 |    | 8 9 A B | C D E F | 0 1 2 3 | 4 5 6 7 |
 | 8 9 A B | C D E F | 0 1 2 3 | 4 5 6 7 |    | 5 4 7 6 | 9 8 B A | D C F E | 1 0 3 2 |
 | C D E F | 0 1 2 3 | 4 5 6 7 | 8 9 A B |    | D C F E | 1 0 3 2 | 5 4 7 6 | 9 8 B A |
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
 | 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C |    | 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E |
 | 5 6 7 4 | 9 A B 8 | D E F C | 1 2 3 0 |    | B 8 9 A | F C D E | 3 0 1 2 | 7 4 5 6 |
 | 9 A B 8 | D E F C | 1 2 3 0 | 5 6 7 4 |    | 6 5 4 7 | A 9 8 B | E D C F | 2 1 0 3 |
 | D E F C | 1 2 3 0 | 5 6 7 4 | 9 A B 8 |    | E D C F | 2 1 0 3 | 6 5 4 7 | A 9 8 B |
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
 | 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D |    | A B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |
 | 6 7 4 5 | A B 8 9 | E F C D | 2 3 0 1 |    | 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D |
 | A B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |    | F E D C | 3 2 1 0 | 7 6 5 4 | B A 9 8 |
 | E F C D | 2 3 0 1 | 6 7 4 5 | A B 8 9 |    | 7 6 5 4 | B A 9 8 | F E D C | 3 2 1 0 |
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
 | 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E |    | 9 A B 8 | D E F C | 1 2 3 0 | 5 6 7 4 |
 | 7 4 5 6 | B 8 9 A | F C D E | 3 0 1 2 |    | 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C |
 | B 8 9 A | F C D E | 3 0 1 2 | 7 4 5 6 |    | C F E D | 0 3 2 1 | 4 7 6 5 | 8 B A 9 |
 | F C D E | 3 0 1 2 | 7 4 5 6 | B 8 9 A |    | 4 7 6 5 | 8 B A 9 | C F E D | 0 3 2 1 |
 +---------+---------+---------+---------+    +---------+---------+---------+---------+
User avatar
Mathimagics
2017 Supporter
 
Posts: 1585
Joined: 27 May 2015
Location: Canberra

Re: Magic Giant Sudoku

Postby Serg » Sun Jun 14, 2020 12:27 pm

Hi, Mathimagics!
Mathimagics wrote:I have found not one, but two cases of OS16's (pairs of orthogonal 16 x 16 Sudokus)

Congratulations! (Yes, MC grid is suitable tool for large Sudoku solution grids generation.)

Serg
Serg
2018 Supporter
 
Posts: 717
Joined: 01 June 2010
Location: Russia

Re: Magic Giant Sudoku

Postby tarek » Sun Jun 14, 2020 3:11 pm

Mathimagics wrote:I have found not one, but two cases of OS16's (pairs of orthogonal 16 x 16 Sudokus)

Well done!!!
User avatar
tarek
 
Posts: 3747
Joined: 05 January 2006

Previous

Return to Sudoku variants