Sudoku16: Minlex Forms

Programs which generate, solve, and analyze Sudoku puzzles

Sudoku16: Minlex Forms

Postby Mathimagics » Mon Jan 11, 2021 4:03 pm

.
We now have software tools for producing canonical forms (minlex) for 16 x 16 Sudoku grids/puzzles in a very efficient manner.

These tools are derived (in my case, anyway) from the groundbreaking work of Michael Deverin (aka holdout) (see Minlex Forms with Chaining).

The essential idea is that we can determine the minlex form for any pair of rows/columns in the same band/stack, without having to check every possible transformation.

For 16x16 grids, the number of VPT's (validity-preserving transformations) applicable to a pair of rows is 24 ^ 5 = 7,962,624. There are 48 pairs (24 row pairs and 24 column pairs) that need to be considered. That's a total of 382,205,952 candidate pairs.

For 9x9 Sudoku grids, there are only 23,328 candidate pairs (1296 transformations and 18 row/col pairs).

Amazingly, however, we can get minlex forms for 16x16 grids faster than the classical canonicalisation functions (eg GridChecker) can do 9x9 grids ... :shock:

The new tools also return automorphism group size information, just like the classical 9x9 minlex functions.

My own version of "Minlex16" was developed some time back (Sept 2020), but for various reasons it is not easily distributed. But my good friend Serg has since come up with a truly "whiz-bang" (and highly original) implementation, one that is much more suitable for distribution, and I understand that he will make that available here in the near future ...

Some elementary analysis of Sudoku16 ED grid distribution is now possible, and some basic results will be listed in the next post ...

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Sudoku16: Minlex Forms

Postby Mathimagics » Mon Jan 11, 2021 4:09 pm

.
Number of Different Possible Row #2 Values

I will adopt the "hex" grid representation throughout ... thus any grid in minlex form has row 1 = "0123 4567 89AB CDEF".

How many different MR2's (minlex row 2's) are possible?

If we take any pair of rows/cols of a valid grid (from the same band or stack), and convert them to minlex form, then there are 18,695 different MR2's that can result. The MR2 table, a sorted list, is attached below. Here are the first (and last) few entries of that table:

Code: Select all
4567 0123 CDEF 89AB
4567 0123 CDEF 89BA
4567 0123 CDEF 8AB9
. . .
. . .
458C 9D2E F137 B0A6
458C 9D2E F137 BA06
458C 9D2E F317 BA06


For any pair of rows/cols, we define its rank to be the position of its corresponding MR2 in the MR2 table.

For a band, stack, or a complete grid, the rank is defined as the minimum rank found among its 6 (for a band/stack) or 48 (for a full grid) row/col pairs.

Given a rank value X, then as X increases, it becomes less and less probable that any complete grid actually exists that has rank X.

The question of exactly which ranks are actually possible in full grids is a subject of ongoing research, and will be discussed in more detail in subsequent posts.

Meanwhile, here is a grid in minlex form, which has rank 1, and which is composed of 64 x UA4's. It has 18,432 automorphisms, which is believed to be the maximum possible:

Grid with Most Automorphisms: Show
Code: Select all
+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 6 7 | 0 1 2 3 | C D E F | 8 9 A B |
| 8 9 A B | C D E F | 0 1 2 3 | 4 5 6 7 |
| C D E F | 8 9 A B | 4 5 6 7 | 0 1 2 3 |
+---------+---------+---------+---------+
| 1 0 3 2 | 5 4 7 6 | 9 8 B A | D C F E |
| 5 4 7 6 | 1 0 3 2 | D C F E | 9 8 B A |
| 9 8 B A | D C F E | 1 0 3 2 | 5 4 7 6 |
| D C F E | 9 8 B A | 5 4 7 6 | 1 0 3 2 |
+---------+---------+---------+---------+
| 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 B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |
| E F C D | A B 8 9 | 6 7 4 5 | 2 3 0 1 |
+---------+---------+---------+---------+
| 3 2 1 0 | 7 6 5 4 | B A 9 8 | F E D C |
| 7 6 5 4 | 3 2 1 0 | F E D C | B A 9 8 |
| B A 9 8 | F E D C | 3 2 1 0 | 7 6 5 4 |
| F E D C | B A 9 8 | 7 6 5 4 | 3 2 1 0 |
+---------+---------+---------+---------+


[EDIT] Unable to post the MR2 table just now, it looks like the forum attachment quota has been reached (again)! :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Sudoku16: Minlex Forms

Postby Serg » Tue Jan 12, 2021 11:14 pm

Hi, Mathimagics!
I know you have done hard work searching for minlex form's examples for all 18695 16 x 16 Sudoku solution grid ranks. I.e. canonicalized solution grids having r1+r2 row pairs with given ranks. Could you publish intervals of ranks for which examples were found and intervals of impossible ranks for r1+r2 pairs in 16 x 16 Sudoku solution grid minlex forms?

Serg
Serg
2018 Supporter
 
Posts: 768
Joined: 01 June 2010
Location: Ukraine

Re: Sudoku16: Minlex Forms

Postby Mathimagics » Wed Jan 13, 2021 5:39 am

Hi Serg,

As you know, grids with very high ranks are rare, and thus very hard to find.

I have been searching using various methods that are essentially based on "vicinity search". Given a grid with G, with rank X, then grids in the immediate vicinity (within 1 or 2 UA's) are likely to have similar ranks. By collecting these and searching them, I was able to build a collection of high-ranking grid examples.

We use zero-based ranking, so ranks are in the range [0, 18694]. To date I have found grids for all ranks up to and including 16618. The maximum rank for which a grid example has been found is 16789.

Of course, what began as a river of new rank findings has slowed considerably, at first to a trickle, and now it looks to have run completely dry! :?

In any case, this search method is unable to answer the question: what is the highest possible rank for a grid?. It merely establishes a lower bound.

To find the answer we need to resort to other means. I will describe these in another post.

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

Re: Sudoku16: Minlex Forms

Postby Mathimagics » Wed Jan 13, 2021 6:37 am

.
What ranks are not possible?

Let TR be the rank to be tested. For a grid to exist with rank TR, there must first be a band with rank TR.

We can enumerate the valid bands. We fix rows 1 and 2 for rank TR, then enumerate all the different valid row 3's. There are roughly 564 million row 3's for any fixed R1 + R2. For acceptance, an R3 candidate must satisfy both of these properties:

  • rank(R1, R3) >= TR
  • rank(R2, R3) >= TR


For any R3 that passes these tests, we then need to enumerate the R4 settings (331,776 = 24 ^ 4 possibilities). If we find an R4 that has all of these properties:

  • rank(R1, R4) >= TR
  • rank(R2, R4) >= TR
  • rank(R3, R4) >= TR


... then congratulations, we have a valid band of rank TR. :cool:


Obviously, the more valid R3's we find, the longer the whole process takes. And as we reduce the test rank TR, the number of valid R3's steadily increases.

So, although band enumeration for TR = 18694 took about 15 minutes, for TR = 18520 it took 75 minutes, and for TR = 18400 it took 4 hours. :(

The band enumeration has completed ~350 rank values, from 18694 down to 18356, and has found bands for 50 of these. Bands exist for rank 18688, so we haven't lowered the upper bound by very much! :?

But that should change when we have a process that can combine the known bands and attempt to build a complete grid.

This "Band Assembly" is the tricky part - if a grid exists where every band/stack has min rank TR, then we should be able to "build" a grid using only the set of known band completions (one with rank TR, the rest with rank TR or more).

It would seem that there are a limited number of ways in which these bands can be combined, so I am hoping this should be a fairly quick process.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Sudoku16: Minlex Forms

Postby coloin » Fri Jan 15, 2021 12:32 am

Very interesting work ! and amazing that the process is so fast

Just to be clear ..and to compare with the 9*9 model

The grid with the most automorphism would be equivalent to the MC grid ?

In 9*9 there are only 15 MR2 combinations, and only one doesnt feature in the table of minlex ed 9*9 grids
In 16*16 there are 18695 MR2s, and many of the higher ones dont feature in the big 6e98 number of ed grids !

In 9*9 there are 416 ED bands, We can only gu-estimate this number in the 16*16 case.

Im sure in the future we may well have the particular large min-lex band and its automorphic max min-lex grid !
coloin
 
Posts: 2083
Joined: 05 May 2005

Re: Sudoku16: Minlex Forms

Postby Mathimagics » Fri Jan 15, 2021 2:08 pm

coloin wrote:In 9*9 there are only 15 MR2 combinations, and only one doesnt feature in the table of minlex ed 9*9 grids
In 16*16 there are 18695 MR2s, and many of the higher ones dont feature in the big 6e98 number of ed grids !

Indeed, both of these statements are correct. :cool:

The grid with the most automorphism would be equivalent to the MC grid ?

That depends on how you interpret the term "most canonical". Serg and I have a difference of opinion here ... :?

This is what you get if you construct a 16x16 grid that is "equivalent" to the 9x9 MC grid, ie has the pattern of repeating minirows cyclically shifted:

Code: Select all
+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 6 7 | 0 1 2 3 | C D E F | 8 9 A B |
| 8 9 A B | C D E F | 4 5 6 7 | 0 1 2 3 |
| C D E F | 8 9 A B | 0 1 2 3 | 4 5 6 7 |
+---------+---------+---------+---------+
| 1 0 3 2 | 5 4 7 6 | 9 8 B A | D C F E |
| 5 4 7 6 | 1 0 3 2 | D C F E | 9 8 B A |
| 9 8 B A | D C F E | 5 4 7 6 | 1 0 3 2 |
| D C F E | 9 8 B A | 1 0 3 2 | 5 4 7 6 |
+---------+---------+---------+---------+
| 2 3 1 0 | 6 7 5 4 | A B 9 8 | E F D C |
| 6 7 5 4 | 2 3 1 0 | E F D C | A B 9 8 |
| A B 9 8 | E F D C | 6 7 5 4 | 2 3 1 0 |
| E F D C | A B 9 8 | 2 3 1 0 | 6 7 5 4 |
+---------+---------+---------+---------+
| 3 2 0 1 | 7 6 4 5 | B A 8 9 | F E C D |
| 7 6 4 5 | 3 2 0 1 | F E C D | B A 8 9 |
| B A 8 9 | F E C D | 7 6 4 5 | 3 2 0 1 |
| F E C D | B A 8 9 | 3 2 0 1 | 7 6 4 5 |
+---------+---------+---------+---------+

This looks very similar to the "grid with most automorphisms" shown in the post above, but this grid has only 2048 automorphisms

Finally, yes, counting ED bands is not going to be possible anytime soon (until the cost of Cray's comes down).

The identification of those MR2's that can actually occur in an ED minlex grid, while certainly challenging, looks to be feasible.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Sudoku16: Minlex Forms

Postby Serg » Fri Jan 15, 2021 8:13 pm

Hi, coloin!
I'd like to comment your question about 16 x 16 MC grid.
Mathimagics wrote:
coloin wrote:The grid with the most automorphism would be equivalent to the MC grid ?

That depends on how you interpret the term "most canonical". Serg and I have a difference of opinion here ... :?

9 x 9 MC grid has many interesting properties, not only maximum number of automorphisms. It, for example, has no U4 unavoidable sets. To my mind, the main property of 9 x 9 MC grid is its cyclical structure.
Code: Select all
      MC grid
+-----+-----+-----+
|1 2 3|4 5 6|7 8 9|
|4 5 6|7 8 9|1 2 3|
|7 8 9|1 2 3|4 5 6|
+-----+-----+-----+
|2 3 1|5 6 4|8 9 7|
|5 6 4|8 9 7|2 3 1|
|8 9 7|2 3 1|5 6 4|
+-----+-----+-----+
|3 1 2|6 4 5|9 7 8|
|6 4 5|9 7 8|3 1 2|
|9 7 8|3 1 2|6 4 5|
+-----+-----+-----+

Each band contains 3 different forms of minirows only, each band's row is previous upper row cyclically shifted left 3 times. Minirows of the second band (B456) are produced from the first band's minirows by cyclical shift left 1 times. Such grid structure is very symmetrical and gives us a method to construct solution grid of any N^2 x N^2 Sudoku solution grids (16 x 16, 100 x 100, etc.). Latin squares built by cyclically shifting left upper row are called "back circulant Latin squares". I think the name "back circulant Sudoku grid" is better for 9 x 9 MC grid, but the name "MC grid" can no longer be changed, because it has been used for a long time.

"Back circulant Sudoku grid" for 16 x 16 Sudoku should looks like that.
Code: Select all
Back circulant 16 x 16 Sudoku grid
+---------+---------+---------+---------+
| 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 |
| C D E F | 0 1 2 3 | 4 5 6 7 | 8 9 A B |
+---------+---------+---------+---------+
| 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C |
| 5 6 7 4 | 9 A B 8 | D E F C | 1 2 3 0 |
| 9 A B 8 | D E F C | 1 2 3 0 | 5 6 7 4 |
| D E F C | 1 2 3 0 | 5 6 7 4 | 9 A B 8 |
+---------+---------+---------+---------+
| 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D |
| 6 7 4 5 | A B 8 9 | E F C D | 2 3 0 1 |
| A B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |
| E F C D | 2 3 0 1 | 6 7 4 5 | A B 8 9 |
+---------+---------+---------+---------+
| 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E |
| 7 4 5 6 | B 8 9 A | F C D E | 3 0 1 2 |
| B 8 9 A | F C D E | 3 0 1 2 | 7 4 5 6 |
| F C D E | 3 0 1 2 | 7 4 5 6 | B 8 9 A |
+---------+---------+---------+---------+

Unfortunately, this solution grid isn't minlex form. If we reduce it to minlex form, we'll get solution grid, published by Mathimagics:
Code: Select all
+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 6 7 | 0 1 2 3 | C D E F | 8 9 A B |
| 8 9 A B | C D E F | 4 5 6 7 | 0 1 2 3 |
| C D E F | 8 9 A B | 0 1 2 3 | 4 5 6 7 |
+---------+---------+---------+---------+
| 1 0 3 2 | 5 4 7 6 | 9 8 B A | D C F E |
| 5 4 7 6 | 1 0 3 2 | D C F E | 9 8 B A |
| 9 8 B A | D C F E | 5 4 7 6 | 1 0 3 2 |
| D C F E | 9 8 B A | 1 0 3 2 | 5 4 7 6 |
+---------+---------+---------+---------+
| 2 3 1 0 | 6 7 5 4 | A B 9 8 | E F D C |
| 6 7 5 4 | 2 3 1 0 | E F D C | A B 9 8 |
| A B 9 8 | E F D C | 6 7 5 4 | 2 3 1 0 |
| E F D C | A B 9 8 | 2 3 1 0 | 6 7 5 4 |
+---------+---------+---------+---------+
| 3 2 0 1 | 7 6 4 5 | B A 8 9 | F E C D |
| 7 6 4 5 | 3 2 0 1 | F E C D | B A 8 9 |
| B A 8 9 | F E C D | 7 6 4 5 | 3 2 0 1 |
| F E C D | B A 8 9 | 3 2 0 1 | 7 6 4 5 |
+---------+---------+---------+---------+

Unfortunately this grid has less regular structure than 9 x 9 MC grid and contains U4 UA sets.

So, I think that 16 x 16 solution grid with maximum (18432) number of automorphisms is better called "Most Automorphic grid" or "MA grid", but back circulant 16 x 16 Sudoku grid let be called "16 x 16 MC grid".

Serg
Serg
2018 Supporter
 
Posts: 768
Joined: 01 June 2010
Location: Ukraine

Re: Sudoku16: Minlex Forms

Postby coloin » Fri Jan 15, 2021 9:19 pm

Thanks to you both .... thats clear !
coloin
 
Posts: 2083
Joined: 05 May 2005

Sudoku16: Minlex Forms

Postby Mathimagics » Sun Jan 17, 2021 6:49 am

.
Highest Ranked Band

The highest rank for which a complete band can be formed is rank 18688:

Code: Select all
 +---------+---------+---------+---------+
 | 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
 | 4 5 8 C | 9 D 2 3 | E F 1 7 | B A 6 0 |
 | 6 9 F A | E B C 1 | 0 D 4 2 | 8 7 3 5 |
 | E B 7 D | 8 0 F A | 3 5 C 6 | 2 4 9 1 |
 +---------+---------+---------+---------+

0123456789ABCDEF458C9D23EF17BA6069FAEBC10D428735EB7D80FA35C62491


Minlex Band Enumeration (Progress)

This table shows number of minlex bands (NMB), that is, the number of ED 4-row forms, by descending order of rank, for rank range [18312, 18694]. Ranks with NMB = 0 are omitted, and there are just 56 cases with NMB > 0 in this range.

Minlex Band Enumeration: Show
Code: Select all
   Rank          NMB
   -----------------
   18688           1
   18685           1
   18683           1
   18603           4
   18601          13
   18467           1
   18460           5
   18458           8
   18430           3
   18428           7
   18425           3
   18414          11
   18413          15
   18402          38
   18400          94
   18399          19
   18398          23
   18396          30
   18394          38
   18393           2
   18392           3
   18391         113
   18390         121
   18389          89
   18388           6
   18387         110
   18386          25
   18370         259
   18368         442
   18367          87
   18366          96
   18364         138
   18362         156
   18361          47
   18360          56
   18359         278
   18358        1021
   18357         483
   18356         269
   18355          77
   18354         432
   18353         372
   18352         114
   18351          75
   18343          13
   18342          16
   18341          31
   18338           5
   18337          12
   18336          19
   18335          32
   18327           5
   18326          12
   18325          19
   18324          32
   18312        8246


Rank 18312, the last entry in the table above, marks a turning point. Every rank below this has NMB > 0, and the counts rise dramatically. The band enumeration process has now reached rank 18045, and the average NMB for the range [18312, 18405] is 161,000. :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Sudoku16: Minlex Forms

Postby Mathimagics » Sun Jan 17, 2021 9:47 am

Mathimagics wrote: To date I have found grids for all ranks up to and including 16618. The maximum rank for which a grid example has been found is 16789.

Update: we have found grids for all ranks up to and including 16622. The maximum rank for which a grid example has been found is now 16935.

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

Re: Sudoku16: Minlex Forms (special case)

Postby m_b_metcalf » Sun Jan 17, 2021 1:13 pm

Your discussion of the second row of a 16x16 solution grid reminded me of a surprising (to me) discovery that I made a long time ago while trying to generate large grids. A very special example of such a grid is shown below. Before going into details, maybe you can spot what I'm leading up to?

Regards,

Mike

Code: Select all
 9 0 D C 2 7 6 5 F 3 E 1 4 A 8 B
 E 3 1 F 8 A B 4 C 0 9 D 5 7 2 6
 5 2 7 6 0 D C 9 B 8 4 A E 1 3 F
 4 8 A B 3 1 F E 6 2 5 7 9 D 0 C
 C D 0 9 A 8 4 B E 1 F 3 6 2 7 5
 B A 8 4 D 0 9 C 5 7 6 2 F 3 1 E
 F 1 3 E 7 2 5 6 9 D C 0 B 8 A 4
 6 7 2 5 1 3 E F 4 A B 8 C 0 D 9
 7 6 5 2 C 9 0 D 8 B A 4 1 E F 3
 1 F E 3 B 4 8 A 0 C D 9 7 5 6 2
 D C 9 0 6 5 2 7 3 F 1 E A 4 B 8
 A B 4 8 F E 3 1 2 6 7 5 D 9 C 0
 0 9 C D 4 B A 8 1 E 3 F 2 6 5 7
 8 4 B A 9 C D 0 7 5 2 6 3 F E 1
 2 5 6 7 E F 1 3 A 4 8 B 0 C 9 D
 3 E F 1 5 6 7 2 D 9 0 C 8 B 4 A
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 12268
Joined: 15 May 2006
Location: Berlin

Re: Sudoku16: Minlex Forms (special case)

Postby Serg » Sun Jan 17, 2021 1:49 pm

Hi, Mike!
m_b_metcalf wrote:Your discussion of the second row of a 16x16 solution grid reminded me of a surprising (to me) discovery that I made a long time ago while trying to generate large grids. A very special example of such a grid is shown below. Before going into details, maybe you can spot what I'm leading up to?
Code: Select all
 9 0 D C 2 7 6 5 F 3 E 1 4 A 8 B
 E 3 1 F 8 A B 4 C 0 9 D 5 7 2 6
 5 2 7 6 0 D C 9 B 8 4 A E 1 3 F
 4 8 A B 3 1 F E 6 2 5 7 9 D 0 C
 C D 0 9 A 8 4 B E 1 F 3 6 2 7 5
 B A 8 4 D 0 9 C 5 7 6 2 F 3 1 E
 F 1 3 E 7 2 5 6 9 D C 0 B 8 A 4
 6 7 2 5 1 3 E F 4 A B 8 C 0 D 9
 7 6 5 2 C 9 0 D 8 B A 4 1 E F 3
 1 F E 3 B 4 8 A 0 C D 9 7 5 6 2
 D C 9 0 6 5 2 7 3 F 1 E A 4 B 8
 A B 4 8 F E 3 1 2 6 7 5 D 9 C 0
 0 9 C D 4 B A 8 1 E 3 F 2 6 5 7
 8 4 B A 9 C D 0 7 5 2 6 3 F E 1
 2 5 6 7 E F 1 3 A 4 8 B 0 C 9 D
 3 E F 1 5 6 7 2 D 9 0 C 8 B 4 A

I don't understand, what do you mean.
You grid in minlex form:
Code: Select all
+-------+-------+-------+-------+
|0 1 2 3|4 5 6 7|8 9 A B|C D E F|
|4 5 6 7|0 1 2 3|C D E F|8 9 A B|
|8 9 A B|C D E F|0 1 2 3|4 5 6 7|
|C D E F|8 9 A B|4 5 6 7|0 1 2 3|
+-------+-------+-------+-------+
|1 0 3 2|5 4 7 6|9 8 B A|D C F E|
|5 4 7 6|1 0 3 2|D C F E|9 8 B A|
|9 8 B A|D C F E|1 0 3 2|5 4 7 6|
|D C F E|9 8 B A|5 4 7 6|1 0 3 2|
+-------+-------+-------+-------+
|2 3 0 1|6 7 4 5|B A 9 8|F E D C|
|6 7 4 5|2 3 0 1|F E D C|B A 9 8|
|A B 8 9|E F C D|3 2 1 0|7 6 5 4|
|E F C D|A B 8 9|7 6 5 4|3 2 1 0|
+-------+-------+-------+-------+
|3 2 1 0|7 6 5 4|A B 8 9|E F C D|
|7 6 5 4|3 2 1 0|E F C D|A B 8 9|
|B A 9 8|F E D C|2 3 0 1|6 7 4 5|
|F E D C|B A 9 8|6 7 4 5|2 3 0 1|
+-------+-------+-------+-------+
Automorphisms: 1024

This grid has very regular 1st and 2nd bands, but 3rd and 4th bands are somewhat "broken".

Serg
Serg
2018 Supporter
 
Posts: 768
Joined: 01 June 2010
Location: Ukraine

Re: Sudoku16: Minlex Forms

Postby Serg » Sun Jan 17, 2021 1:59 pm

Hi, Mathimagics!
Mathimagics wrote:
Mathimagics wrote: To date I have found grids for all ranks up to and including 16618. The maximum rank for which a grid example has been found is 16789.

Update: we have found grids for all ranks up to and including 16622. The maximum rank for which a grid example has been found is now 16935.

Grid with Rank 16935: Show
Code: Select all
+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 8 C | 1 9 A D | 6 E F 0 | B 2 3 7 |
| 7 A F E | 0 C B 3 | 5 4 D 2 | 9 8 1 6 |
| B D 9 6 | 2 E 8 F | C 7 3 1 | 5 4 A 0 |
+---------+---------+---------+---------+
| 1 4 D B | 7 F 2 0 | 3 6 5 E | 8 A C 9 |
| 3 C E 7 | 9 4 1 5 | F D 8 A | 6 B 0 2 |
| 5 8 0 2 | A D C 6 | 4 B 9 7 | 1 E F 3 |
| 9 F 6 A | B 8 3 E | 1 0 2 C | D 7 4 5 |
+---------+---------+---------+---------+
| 2 9 3 0 | E 6 D 4 | A F 1 8 | 7 5 B C |
| C 6 A 8 | 5 7 0 1 | E 3 B 4 | F 9 2 D |
| D 7 B 1 | 3 A F C | 9 2 6 5 | 4 0 8 E |
| F E 4 5 | 8 2 9 B | 0 C 7 D | 3 1 6 A |
+---------+---------+---------+---------+
| 6 3 1 4 | D B 7 9 | 2 A E F | 0 C 5 8 |
| 8 2 5 D | F 0 4 A | 7 1 C 6 | E 3 9 B |
| A B C 9 | 6 1 E 8 | D 5 0 3 | 2 F 7 4 |
| E 0 7 F | C 3 5 2 | B 8 4 9 | A 6 D 1 |
+---------+---------+---------+---------+

Congratulations! It's really hard work - to find high rank examples of 16 x 16 grids.

Serg
Serg
2018 Supporter
 
Posts: 768
Joined: 01 June 2010
Location: Ukraine

Re: Sudoku16: Minlex Forms (special case)

Postby m_b_metcalf » Sun Jan 17, 2021 2:30 pm

Serg wrote:Automorphisms: 1024

This grid has very regular 1st and 2nd bands, but 3rd and 4th bands are somewhat "broken".

Serg,
Yes, you're on the right track. The grid is an isomorph of the first one below. What I noticed back then was that it was very difficult to generate large grids, say 100x100, but if they were of even size, then it was relatively easy to generate a grid where every even row is a reverse copy of the previous odd row. The second grid below is a more random example

Code: Select all
 1 2 3 4 5 6 7 8 9 A B C D E F 0
 0 F E D C B A 9 8 7 6 5 4 3 2 1
 9 A B C D E F 0 1 2 3 4 5 6 7 8
 8 7 6 5 4 3 2 1 0 F E D C B A 9
 D E F 0 1 2 3 4 5 6 7 8 9 A B C
 4 3 2 1 0 F E D C B A 9 8 7 6 5
 5 6 7 8 9 A B C D E F 0 1 2 3 4
 C B A 9 8 7 6 5 4 3 2 1 0 F E D
 2 1 4 3 6 5 8 7 A 9 C B E D 0 F
 F 0 D E B C 9 A 7 8 5 6 3 4 1 2
 A 9 C B E D 0 F 2 1 4 3 6 5 8 7
 7 8 5 6 3 4 1 2 F 0 D E B C 9 A
 E D 0 F 2 1 4 3 6 5 8 7 A 9 C B
 3 4 1 2 F 0 D E B C 9 A 7 8 5 6
 6 5 8 7 A 9 C B E D 0 F 2 1 4 3
 B C 9 A 7 8 5 6 3 4 1 2 F 0 D E 

Code: Select all
 D 8 4 3 5 6 F 2 E B 9 0 1 7 A C
 C A 7 1 0 9 B E 2 F 6 5 3 4 8 D
 2 0 6 F 7 D 4 8 3 C 1 A E B 9 5
 5 9 B E A 1 C 3 8 4 D 7 F 6 0 2
 9 D F 6 B 7 E 1 5 3 8 2 0 C 4 A
 A 4 C 0 2 8 3 5 1 E 7 B 6 F D 9
 E 2 8 B D 0 6 4 C 9 A F 7 1 5 3
 3 5 1 7 F A 9 C 4 6 0 D B 8 2 E
 6 E A 5 3 F 1 B 7 D 2 8 9 0 C 4
 4 C 0 9 8 2 D 7 B 1 F 3 5 A E 6
 B F 3 2 9 E 5 A 6 0 4 C 8 D 1 7
 7 1 D 8 C 4 0 6 A 5 E 9 2 3 F B
 0 3 E C 4 5 8 F D 2 B 6 A 9 7 1
 1 7 9 A 6 B 2 D F 8 5 4 C E 3 0
 F 6 5 D 1 3 A 0 9 7 C E 4 2 B 8
 8 B 2 4 E C 7 9 0 A 3 1 D 5 6 F
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 12268
Joined: 15 May 2006
Location: Berlin

Next

Return to Software