Sudoku Players' Forum (clone)

Very good !!
I did think it an increasingly unlikely scenario that a grid has all the 48 row pairs of high rank - and that an automorphic grid with all similar high ranking might be more likely !!! Well found !

.
I have found some more high-ranking automorphic grids. These are not H-grids, but they are close relations, and were found while searching for H-grids.

Pursuing my "band knitting" analogy, we need a term for the number of distinct minlex bands (horizontal and vertical) in a grid. The vast majority of grids will have 8 different bands, and H-grids by definition only have one, but any number in between is possible.

I suggest the term k-ply. So H-grids are 1-ply, and the most common grids (with all different bands) are 8-ply. I also conjecture that low-ply grids are far more likely to be automorphic than normal grids.

The first example is 3-ply, it has rank 17371 and 8 automorphisms:

Code: Select all

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

The minlex bands are shown here, tagged with their rank, and a code that indicates which bands are distinct:

Code: Select all

Minlex Bands:
 1: 0123456789ABCDEF458C239D71EFAB6069BF1CEA350D4278AE7D08FB246C1953 # 17371  A
 2: 0123456789ABCDEF458C239DEF17AB0669FAC1EB420D8735EB7D80FAC6354219 # 17411  B
 3: 0123456789ABCDEF458C239DEF17AB0669FAC1EB420D8735EB7D80FAC6354219 # 17411  B
 4: 0123456789ABCDEF458C239DEF17AB0669FAC1EB420D3587EB7D80FAC6351942 # 17411  C

Minlex Stacks:
 1: 0123456789ABCDEF458C239D71EFAB6069BF1CEA350D4278AE7D08FB246C1953 # 17371  A
 2: 0123456789ABCDEF458C239DEF17AB0669FAC1EB420D8735EB7D80FAC6354219 # 17411  B
 3: 0123456789ABCDEF458C239DEF17AB0669FAC1EB420D8735EB7D80FAC6354219 # 17411  B
 4: 0123456789ABCDEF458C239DEF17AB0669FAC1EB420D3587EB7D80FAC6351942 # 17411  C


Here is a second example. Like the grid above it has rank 17371 and has 8 automorphisms, and is 3-ply, but with slightly different composition:

Hi, Mathimagics!

Mathimagics wrote:... HB-grid, which has rank 17,411, and 34 grid automorphisms!

Code: Select all

+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 8 C | 2 3 9 D | E F 1 7 | A B 0 6 |
| 6 9 B E | 1 C F A | 3 5 0 D | 4 2 8 7 |
| A F 7 D | 0 8 E B | C 6 4 2 | 1 9 3 5 |
+---------+---------+---------+---------+
| 1 3 9 2 | 7 A B 8 | 6 4 E C | F 0 5 D |
| 5 7 4 8 | E 9 1 F | A 0 D 3 | 2 6 B C |
| B 6 E 0 | 3 D C 5 | 7 2 F 1 | 8 A 9 4 |
| C A D F | 6 4 2 0 | B 8 9 5 | 7 3 1 E |
+---------+---------+---------+---------+
| 2 8 3 9 | 5 6 0 4 | D E 7 F | B 1 C A |
| 7 4 1 5 | D 2 3 C | 9 B 6 A | 0 E F 8 |
| D E 0 B | 9 F A 1 | 4 C 2 8 | 5 7 6 3 |
| F C A 6 | B 7 8 E | 5 1 3 0 | D 4 2 9 |
+---------+---------+---------+---------+
| 3 D C A | F 0 5 6 | 1 7 B E | 9 8 4 2 |
| 8 B 5 7 | A 1 4 9 | 2 3 C 6 | E F D 0 |
| 9 2 F 1 | 8 E 7 3 | 0 D 5 4 | 6 C A B |
| E 0 6 4 | C B D 2 | F A 8 9 | 3 5 7 1 |
+---------+---------+---------+---------+
Grid rank = 17411, automorphisms = 32


Congratulations! I could not even imagine that such HB-grids exist. Very interesting! (Please, correct a typo - "34 grid automorphisms" - of course there must be "32" automorphisms.)

Well done!

Serg

Thanks, Serg!

I have corrected that typo.

We already did have one example of a HB-grid from the start, of course, the "most automorphic" grid. And I will look further for "low-rank" HB-grids, as well as continuing the search from the high-rank end.

.
In a HB-grid, every one of the 48 row/col pairs has the same rank.

If A and B are both HB-grids, and rank(A) = rank(B), does it then follow that A and B are isomorphic?

Remarkably (to me anyway), the answer is "not necessarily"

Here we have 3 ED grids, all of which are HB-grids with rank 0:



Perhaps this is only possible with rank 0, because of its unique properties ...

.

I have improved the "Band Knit" process considerably, and over the past 5 days have used it to test all the 226,142 known H-bands to see if they can be knitted into a 1-ply grid. Any such result is clearly an HB-grid.

I found just 155 HB-grids, of which 129 have rank 0.

[ EDIT ] this set is actually far from complete, see the following post

The full list is given below, each grid tagged with its rank ("r" and automorphism count ("a".

In the post above, I wondered whether any ranks other than 0 might have multiple HB-grids, and the answer is "yes". You will find in the list several instances of different HB-grids with the same rank, eg rank 823, 829 etc...

I have only just noticed, also, that only 2 grids in the list don't have (non-trivial) automorphisms (rank = 92, and rank = 11456);


Cheers
MM

.
Well, it's been quite a day! I found a bug in BandKnit which only became apparent when I tried to re-knit a test grid using its minlex bands/stacks.

(And so the HB-grid list posted above is far from complete!)

It was only testing 1/576 of the possible combinations in its outermost loop. Having fixed that, I then restarted the HB-grid search, finding that there are indeed grids with rank 18688.

There are 7 of them, in fact, and are listed below. In minlex order, the last is this one:

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 |
+---------+---------+---------+---------+
| 1 C B E | A F 9 6 | 7 8 3 5 | D 0 4 2 |
| 3 2 D 9 | C 8 5 4 | A B 6 0 | F E 1 7 |
| 7 6 5 4 | 3 2 1 0 | D C E F | 9 8 A B |
| A F 0 8 | D 7 B E | 4 2 9 1 | 5 3 C 6 |
+---------+---------+---------+---------+
| 2 4 9 1 | 6 C 3 5 | F A 0 8 | E B 7 D |
| 8 7 3 5 | 2 4 0 D | C 1 B E | 6 9 F A |
| B A 6 0 | 7 1 E F | 2 3 D 9 | 4 5 8 C |
| C D E F | B A 8 9 | 6 7 5 4 | 0 1 2 3 |
+---------+---------+---------+---------+
| 5 3 C 6 | 1 9 4 2 | B E 7 D | A F 0 8 |
| 9 8 A B | F E D C | 1 0 2 3 | 7 6 5 4 |
| D 0 4 2 | 5 3 7 8 | 9 6 F A | 1 C B E |
| F E 1 7 | 0 6 A B | 5 4 8 C | 3 2 D 9 |
+---------+---------+---------+---------+
Rank = 18688, 1-ply, aut =   384

We can state with some confidence, that the grid above is the maximum minlex grid, since there are no bands, and thus no grids, with a higher rank (18689 to 18694).

Very good .... consider yourself very much "stabbed in the back" by those sudoku-16 solution grid "gods" !!!
But pleasing to have the answer definitively !!!
And an automorphic grid did turn out to be the max .....

coloin wrote:And an automorphic grid did turn out to be the max .....

Yes, this set of 7 grids seems functionally "equivalent" to band 416 ...

This is also the very first instance of a complete 16x16 ED band enumeration ...

Hi, Mathimagics!

Mathimagics wrote:

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 |
+---------+---------+---------+---------+
| 1 C B E | A F 9 6 | 7 8 3 5 | D 0 4 2 |
| 3 2 D 9 | C 8 5 4 | A B 6 0 | F E 1 7 |
| 7 6 5 4 | 3 2 1 0 | D C E F | 9 8 A B |
| A F 0 8 | D 7 B E | 4 2 9 1 | 5 3 C 6 |
+---------+---------+---------+---------+
| 2 4 9 1 | 6 C 3 5 | F A 0 8 | E B 7 D |
| 8 7 3 5 | 2 4 0 D | C 1 B E | 6 9 F A |
| B A 6 0 | 7 1 E F | 2 3 D 9 | 4 5 8 C |
| C D E F | B A 8 9 | 6 7 5 4 | 0 1 2 3 |
+---------+---------+---------+---------+
| 5 3 C 6 | 1 9 4 2 | B E 7 D | A F 0 8 |
| 9 8 A B | F E D C | 1 0 2 3 | 7 6 5 4 |
| D 0 4 2 | 5 3 7 8 | 9 6 F A | 1 C B E |
| F E 1 7 | 0 6 A B | 5 4 8 C | 3 2 D 9 |
+---------+---------+---------+---------+
Rank = 18688, 1-ply, aut =   384

We can state with some confidence, that the grid above is the maximum minlex grid, since there are no bands, and thus no grids, with a higher rank (18689 to 18694).

Congratulations with this unexpected discovery! It was hard to beleive for me that it was possible to find maximum minlex 16 x 16 Sudoku grid. I'll try to confirm your statement that band's minlex forms with r1+r2 ranks from 18689 to 18694 don't exist.

Serg

Serg wrote:I'll try to confirm your statement that band's minlex forms with r1+r2 ranks from 18689 to 18694 don't exist.

Hi Serg!

That would be great, to have that confirmed ...

Once you have done that, you might like to go further and check the full list of 327 ranks for which no minlex band forms exist, by my reckoning. These are listed below (10 per line).

Cheers
MM

.
We do appear to have identified both the first and the last of the 16x16 ED grids ...

Just to put this into some sort of cosmic perspective:

Code: Select all

         Number of  grids:  est 6E98
Atoms in visible universe:  est 1E80
       Number of ED grids:  est 2E71


Hi, Mathimagics!

Mathimagics wrote:

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 |
+---------+---------+---------+---------+
| 1 C B E | A F 9 6 | 7 8 3 5 | D 0 4 2 |
| 3 2 D 9 | C 8 5 4 | A B 6 0 | F E 1 7 |
| 7 6 5 4 | 3 2 1 0 | D C E F | 9 8 A B |
| A F 0 8 | D 7 B E | 4 2 9 1 | 5 3 C 6 |
+---------+---------+---------+---------+
| 2 4 9 1 | 6 C 3 5 | F A 0 8 | E B 7 D |
| 8 7 3 5 | 2 4 0 D | C 1 B E | 6 9 F A |
| B A 6 0 | 7 1 E F | 2 3 D 9 | 4 5 8 C |
| C D E F | B A 8 9 | 6 7 5 4 | 0 1 2 3 |
+---------+---------+---------+---------+
| 5 3 C 6 | 1 9 4 2 | B E 7 D | A F 0 8 |
| 9 8 A B | F E D C | 1 0 2 3 | 7 6 5 4 |
| D 0 4 2 | 5 3 7 8 | 9 6 F A | 1 C B E |
| F E 1 7 | 0 6 A B | 5 4 8 C | 3 2 D 9 |
+---------+---------+---------+---------+
Rank = 18688, 1-ply, aut =   384

We can state with some confidence, that the grid above is the maximum minlex grid, since there are no bands, and thus no grids, with a higher rank (18689 to 18694).

Serg wrote:I'll try to confirm your statement that band's minlex forms with r1+r2 ranks from 18689 to 18694 don't exist.

Now I've done exhaustive search for 20 last two-row ranks (18675-18694). Here are results.

Code: Select all

Two-row   r2 row of two-row   Does band's minlex form with such r2 row exist?
rank      minlex form

18675     458C9A3DE1F6B027    No
18676     458C9A3DE1F6B072    No
18677     458C9A3DE1F6B270    No
18678     458C9A3DE1F6B702    No
18679     458C9A3DE1F76B02    No
18680     458C9A3DE1F7B026    No
18681     458C9A3DE1F7B062    No
18682     458C9A3DE1F7B260    No
18683     458C9D23EF06AB17    Yes
18684     458C9D23EF06AB71    No
18685     458C9D23EF06BA71    Yes
18686     458C9D23EF07AB61    No
18687     458C9D23EF07BA61    No
18688     458C9D23EF17BA60    Yes
18689     458C9D2EF037A1B6    No
18690     458C9D2EF037AB16    No
18691     458C9D2EF037BA16    No
18692     458C9D2EF137B0A6    No
18693     458C9D2EF137BA06    No
18694     458C9D2EF317BA06    No

So, I can confirm your statement "... there are no bands, and thus no grids, with a higher rank (18689 to 18694)." and thus I confirm the grid you published is maximum 16 x 16 Sudoku minlex grid.

Serg

Serg wrote:I can confirm your statement "... there are no bands, and thus no grids, with a higher rank (18689 to 18694)." and thus I confirm the grid you published is maximum 16 x 16 Sudoku minlex grid.

That's excellent, thank you, Serg !

Mathimagics wrote:

• we have found grids for 17,065 different ranks. This includes all ranks in the range [0, 17028]

• the maximum rank for which a grid example has been found is now 17158.

So a minor milestone reached, all indicators >= 17000 ...

The discovery of very high-ranking 1-ply grids (and some 2/3-ply) by BandKnit has had a good side-effect, such grids tend to have high-ranking neighbours, and so the overall search effort has been greatly boosted. Today's status report is:

• we have found grids for 17,722 different ranks. This includes all ranks in the range [0, 17580]

• the maximum rank is now fixed at 18688.

• with 327 ranks known to have no grids possible, the number of unresolved ranks is down to (18695 - 17722 - 327) = 646

BandKnit is a very expensive process, and so it can't really be used to prove/disprove grid-existence for most unresolved ranks. For some cases a 1-ply search can be done (and has been done), but below a certain point the number of minlex bands is simply too great to even do a 1-ply search.

But for the very top ranks, it has at least given us some resolution. This table lists, in descending order, the top 10 ranks for which minlex bands exist, and what we know about them:

Code: Select all

 Rank     NMB    Grids    Status
 ================================
 18688      1        7    Complete
 18685      1       10    Complete
 18683      1       23    Complete
 18603      4        0    Complete
 ---------------------------------
 18601     13       ??    Open
 ---------------------------------
 18467      1      yes   
 18460      5      yes   
 18458      8      yes   
 18430      3       ??    Open
 18428      7       ??    Open


Notes:

• the top 4 ranks have been completely tested by BandKnit, and the result is that we now know the 40 highest minlex grids (the "Top 40"

• rank 18603 is the highest rank for which there are minlex bands, but no minlex grids

• rank 18601 has been partly tested, and there no 1-ply or 2-ply grids. To complete (ie check all-ply) the search would require approx 90 core-days. This this can be done in a week (on PC JACK) or so, so I do intend to complete that.

• for the remaining ranks, we have found 1-ply grids and/or grids via the general search for those marked "yes". Otherwise (marked ??) the status is unresolved.