## Sudoku16: Minlex Forms

Programs which generate, solve, and analyze Sudoku puzzles

### Sudoku16: Minlex Forms

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

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

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Sudoku16: Minlex Forms

.
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 89AB4567 0123 CDEF 89BA4567 0123 CDEF 8AB9. . .. . .458C 9D2E F137 B0A6458C 9D2E F137 BA06458C 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)!

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku16: Minlex Forms

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

### Re: Sudoku16: Minlex Forms

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

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku16: Minlex Forms

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

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.

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku16: Minlex Forms

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: 2196
Joined: 05 May 2005
Location: Tenerife

### Re: Sudoku16: Minlex Forms

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.

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.

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku16: Minlex Forms

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

### Re: Sudoku16: Minlex Forms

Thanks to you both .... thats clear !
coloin

Posts: 2196
Joined: 05 May 2005
Location: Tenerife

### Sudoku16: Minlex Forms

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

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku16: Minlex Forms

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

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku16: Minlex Forms (special case)

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`

m_b_metcalf
2017 Supporter

Posts: 13173
Joined: 15 May 2006
Location: Berlin

### Re: Sudoku16: Minlex Forms (special case)

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

### Re: Sudoku16: Minlex Forms

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

### Re: Sudoku16: Minlex Forms (special case)

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 `

m_b_metcalf
2017 Supporter

Posts: 13173
Joined: 15 May 2006
Location: Berlin

Next