The New Sudoku Players' Forum

[Serg]

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

[Mathimagics]

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.

[Mathimagics]

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

[tarek]

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

[Mathimagics]

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

[Serg]

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

[Mathimagics]

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!

[Mathimagics]

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

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

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

[Serg]

Hi, Mathimagics!

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

[tarek]

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

Well done!!!