## Magic Giant Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: Magic Giant Sudoku

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: 716
Joined: 01 June 2010
Location: Russia

### Re: Magic Giant Sudoku

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.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: Magic Giant Sudoku

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 ...

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: Magic Giant Sudoku

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

tarek

Posts: 3745
Joined: 05 January 2006

### Re: Magic Giant Sudoku

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 ...

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: Magic Giant Sudoku

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: 716
Joined: 01 June 2010
Location: Russia

### Re: Magic Giant Sudoku

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 63A3 6B 19 B4BB 13 64 A969 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!

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: Magic Giant Sudoku

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!

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]

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: Magic Giant Sudoku

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!

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
`0123456789ABCDEF89ABCDEF0123456745670123CDEF89ABCDEF89AB4567012330127456B89AFCDEB89AFCDE3012745674563012FCDEB89AFCDEB89A7456301223016745AB89EFCDAB89EFCD2301674567452301EFCDAB89EFCDAB8967452301123056749AB8DEFC9AB8DEFC1230567456741230DEFC9AB8DEFC9AB8567412300123456789ABCDEF45670123CDEF89AB98BADCFE10325476DCFE98BA54761032123056749AB8DEFC56741230DEFC9AB88BA9CFED03214765CFED8BA94765032167452301EFCDAB8923016745AB89EFCDFEDCBA9876543210BA98FEDC3210765474563012FCDEB89A30127456B89AFCDEEDCFA98B65472103A98BEDCF21036547`

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 | +---------+---------+---------+---------+    +---------+---------+---------+---------+`

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: Magic Giant Sudoku

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: 716
Joined: 01 June 2010
Location: Russia

### Re: Magic Giant Sudoku

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

Well done!!!

tarek

Posts: 3745
Joined: 05 January 2006

Previous