The New Sudoku Players' Forum

[Mathimagics]

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.

This not surprising. If the box size is 4x4, or 8x8, etc, then symmetries within the box can be exploited to generate valid boxes in successive bands. Not with odd box sizes though ...

[Mathimagics]

Update: we have found grids for 16,715 different ranks. This includes all ranks in the range [0, 16649]. The maximum rank for which a grid example has been found is now 16939.

Grid with Rank 16939: 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 7 2 3 |
| 9 7 F E | 0 B C 2 | D 3 5 4 | 1 6 8 A |
| D A B 6 | 3 8 E F | 1 2 7 C | 0 5 9 4 |
+---------+---------+---------+---------+
| 1 F A 2 | 6 C 5 9 | 4 8 0 E | D 3 7 B |
| 3 C E 4 | 8 1 7 A | F 6 B D | 2 9 0 5 |
| 6 0 5 7 | D 2 B 4 | 3 A 1 9 | E C F 8 |
| B 8 9 D | F 0 3 E | 5 C 2 7 | A 1 4 6 |
+---------+---------+---------+---------+
| 2 E 4 F | 5 6 0 C | 7 D 9 8 | 3 B A 1 |
| 5 B 3 9 | A E D 8 | 2 F 6 1 | 7 4 C 0 |
| A 6 7 8 | B 4 9 1 | C 0 E 3 | F 2 5 D |
| C D 0 1 | 2 7 F 3 | B 5 4 A | 8 E 6 9 |
+---------+---------+---------+---------+
| 7 3 1 5 | C A 2 0 | 9 4 D F | 6 8 B E |
| 8 2 D B | E F 4 5 | A 1 C 6 | 9 0 3 7 |
| E 9 C A | 7 D 8 6 | 0 B 3 5 | 4 F 1 2 |
| F 4 6 0 | 9 3 1 B | E 7 8 2 | 5 A D C |
+---------+---------+---------+---------+


[Mathimagics]

.
Update: we have found grids for 16,889 different ranks. This includes all ranks in the range [0, 16830]. The maximum rank for which a grid example has been found is now 17106.

Grid with Rank 17106: 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 | E 0 F 7 | 6 3 B 2 |
| 7 B F D | 8 E 3 2 | C 5 1 6 | 9 4 A 0 |
| 9 6 E A | F B 0 C | 3 D 4 2 | 1 5 7 8 |
+---------+---------+---------+---------+
| 1 A 3 F | C 2 7 5 | B 8 0 9 | 4 E 6 D |
| 2 0 C 4 | A 8 D 9 | 6 F 7 E | B 1 3 5 |
| 6 E 5 8 | B 4 F 1 | D 2 C 3 | 0 7 9 A |
| D 7 9 B | 6 0 E 3 | 1 A 5 4 | 8 2 F C |
+---------+---------+---------+---------+
| 3 2 7 E | 5 1 8 F | 9 B 6 0 | A C D 4 |
| 5 F D 6 | E 7 4 B | A C 3 8 | 2 0 1 9 |
| 8 4 0 9 | 2 6 C A | F E D 1 | 3 B 5 7 |
| A C B 1 | 3 D 9 0 | 7 4 2 5 | E F 8 6 |
+---------+---------+---------+---------+
| B 9 1 7 | D C 2 6 | 4 3 8 F | 5 A 0 E |
| C 3 4 5 | 7 F B E | 0 6 9 A | D 8 2 1 |
| E 8 6 2 | 0 A 1 4 | 5 7 B D | F 9 C 3 |
| F D A 0 | 9 3 5 8 | 2 1 E C | 7 6 4 B |
+---------+---------+---------+---------+


[Mathimagics]

.
Update: we have found grids for 16,962 different ranks. This includes all ranks in the range [0, 16880]. The maximum rank for which a grid example has been found is now 17115.

The vicinity search process has been given a big boost by adopting a new method - searching known grids for new seeds using "one-band removal". For each grid G in our "grid pool", we do the following:

• remove the lowest ranked band in G, shift the bands up

• set band 4, col 1 to the 4 available values

• we now have a puzzle with 192 + 4 givens. Using a 16x16 Sudoku solver, we find all solutions, checking each solution grid for the desired properties:
  
  
  • the grid is new wrt the known grid pool
  • the grid has rank > RMIN, where RMIN is a selectable rank threshold value. Currently we use RMIN = 16500.

• repeat for the transpose of G

We mark those grids processed so that subsequent iterations test only the newly found grids.

Grid with Rank 17115: 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 | E 2 7 F | 0 3 B 6 |
| 6 A F E | B C 3 2 | 4 D 5 0 | 9 8 7 1 |
| 9 7 B D | 8 F 0 E | 1 C 3 6 | 5 4 2 A |
+---------+---------+---------+---------+
| 1 8 7 6 | 9 B 5 C | 2 3 E 4 | A 0 F D |
| 3 C A 5 | 7 1 4 0 | F B 6 D | 2 E 8 9 |
| B F 0 2 | D 3 E 8 | 7 1 9 A | 4 6 C 5 |
| D 9 E 4 | 6 2 F A | 0 5 8 C | 7 1 3 B |
+---------+---------+---------+---------+
| 2 B 9 F | E D 8 1 | 6 A 4 7 | 3 5 0 C |
| 8 4 3 0 | C A B F | D E 2 5 | 1 9 6 7 |
| A E 5 1 | 3 7 2 6 | C 8 0 9 | B F D 4 |
| C 6 D 7 | 0 4 9 5 | 3 F B 1 | 8 2 A E |
+---------+---------+---------+---------+
| 5 3 1 B | 2 8 C 4 | A 6 D E | F 7 9 0 |
| 7 2 6 9 | A 0 D B | 5 4 F 8 | E C 1 3 |
| E 0 4 8 | F 6 1 9 | B 7 C 3 | D A 5 2 |
| F D C A | 5 E 7 3 | 9 0 1 2 | 6 B 4 8 |
+---------+---------+---------+---------+


[Serg]

Hi, Mathimagics!
The speed of your search has increased significantly.
What bands are you choosing for new bands' production?

• the grid has rank > RMIN, where RMIN is a selectable rank threshold value. Currently we use RMIN = 16500.

It would seem that you should choose new band with rank lower than other 3 band's ranks

Serg

[Mathimagics]

Hello Serg!

What bands are you choosing for new bands' production?

I am sorry, but I do not understand this question. The search process finds new grids having rank > RMIN, not new bands. Perhaps my description above was not clear ...

Tracking "new bands" would require an ED bands database, and there are far too many of these, probably trillions at the very least ...

How many ED bands are there? I might be able to obtain a fairly good approximation for that ...

[Serg]

Hi, Mathimagics!

What bands are you choosing for new bands' production?

I am sorry, but I do not understand this question. The search process finds new grids having rank > RMIN, not new bands.

It's my typo. I wanted to ask, what grids are you choosing for new bands' production? Is this random choice (from known grids having rank > RMIN)?

Let's consider some 16 x 16 Sudoku solution grid. Its band/stack ranks are: R1, R2, ... R8. Let Rm is the lowest band/stack rank, Rn is the band/stack next lowest rank, i.e. Rn >= Rm, but is not higher, than remaining bands/stacks ranks. It looks like we should replace band/stack with lowest rank by new band/stack with rank >= Rn, isn't it?

Serg

[Mathimagics]

what grids are you choosing for new bands' production? Is this random choice (from known grids having rank > RMIN)?

It started with a pool of just 50,000 grids with rank > 16500 (the result of months of previous searching). Every grid in this pool was processed in the first round, and every new grid in the 2nd round, etc.

At the end of each round, the pool is expanded further by processing the new grids with the existing (UA) vicinity search method. After just 4 rounds (2 weeks) the total pool size has grown to 650,000.

When the pool becomes too big, then I could introduce random selection, but I rather think it might be simpler just to increase RMIN from 16500 to some higher value.

It looks like we should replace band/stack with lowest rank by new band/stack with rank >= Rn, isn't it?

That would be ideal, yes, but we can't easily perform that operation: "replace band Rm by new band with rank >= Rn".

We can, however, go through ALL of the bands that can replace Rm (effectively, this means getting all solutions to the corresponding puzzle with 3 bands fixed) and check each case for the desired properties.

Consider a generalised 3-band puzzle, where we have removed one band, then transposed the grid so is a "3-stack puzzle". The boxes are labelled as band/stack numbers:

Code: Select all

  +----+----+----+----+
  | 11 | 12 | 13 |    |
  +----+----+----+----+
  | 21 | 22 | 23 |    |
  +----+----+----+----+
  | 31 | 32 | 33 |    |
  +----+----+----+----+
  | 41 | 42 | 34 |    |
  +----+----+----+----+


Suppose that stacks 1 to 3 have rank >= X. We can easily enumerate recursively all the possible Box(14) settings that result in a band 1 with rank >= X.

For each of these Box(14) settings, we can then apply the same recursive process to Box(24), and so on for Box(34) and Box(44).

But we still have to check every valid Box(44) completion, looking at rank of stack 4, since the stack rank can't really be determined until it is completed.

(In practice, it is actually faster to stop the recursion after Box(14), testing each case with a fast solver to generate all the solutions for the remaining 3 boxes.)

After the 4th round (of 1 band removals + UA vicinity search) the search status is now:

• we have found grids for 17,000 different ranks. This includes all ranks in the range [0, 16926]. The maximum rank for which a grid example has been found is still 17115.

[coloin]

Tracking "new bands" would require an ED bands database, and there are far too many of these, probably trillions at the very least ...
....
How many ED bands are there? I might be able to obtain a fairly good approximation for that ...

from Mos
est number of 16*16 grids ~ 5.9584×1098
est number of ED 16*16 grids ~ 2.2458×1071

number of bands

For a 4x4 Sudoku:

Code: Select all

    q(1,1) =   20,922,789,888,000    [16!]                                                         
    q(1,2) =      248,341,303,296                                                                   
    q(1,3) =          564,438,622                                                                   
    q(1,4) =              331,776    [24^4]                             
Note that q(1,3) is not an exact value; the others are.                                             
Multiply these and you'll get the band 1 count (but you have to use the exact value for q(1,3),     
a ratio whose denominator will cancel out in the complete product, leaving an integer).             
[edit] The exact value of q(1,3) is 5215977308160 / 9241

Multiplying these = 973038982740573238251518542982676480000 = = 9.7304×1038

Of note the q(1,2) = 248,341,303,296 which also equals the ways to populate Row 2 with a given Row 1 ...

I wonder does that mean that the number of ED Box 1/ Box 2 combinations is 18,695 the same as ED R1/R2 combimations ! ?

[Mathimagics]

Of note the q(1,2) = 248,341,303,296 which also equals the ways to populate Row 2 with a given Row 1 ...

I wonder does that mean that the number of ED Box 1/ Box 2 combinations is 18,695, the same as ED R1/R2 combinations ! ?

My first thought is "yes". The number of box 2 completions (with fixed box 1) is the same as the number of row 2 completions (with fixed row 1). This is true for 9x9 Sudoku, at least. So the ED counts should match.

Regarding the estimation of the number of ED bands, we do have an estimate of 243,356,637,289,512,960 which is the result of dividing the number of bands with fixed row 1 by the number of VPT's for a band (24 ^ 6).

This estimation method ignores automorphisms, but it becomes increasingly accurate as we increase the number of rows used in the partial grids which we are counting, as the automorphism counts are greatly reduced for each extra row that we add to the grid.

This is demonstrated by these 9x9 results:

Code: Select all

9 x 9:
                         Count     ED estimate         ED actual     actual/est
 ------------------------------------------------------------------------------
 Row2:                  12,096               4.67             15        3
 Bands:              2,612,736             336               416        1.24
 Grids: 18,383,222,420,692,992   5,472,447,994     5,472,730,538        1.00005


For 16x16, we have only these results:

Code: Select all

16x16:
                         Count     ED estimate         ED actual     actual/est
 ------------------------------------------------------------------------------
 Row2:         248,341,303,296          15,594            18,695        1.199


 Bands: 46,506,177,615,378,500,246,568,960
 ED est:           243,356,637,289,512,960
 ED actual:                            ???


Notice that the ratio of actual/estimated for row 2 completions is 1.2, which is comparable to the ratio for 9x9 bands.

It would seem likely, then, that the estimate show for 16x16 ED bands is, relatively speaking, very close to the actual figure.

[Mathimagics]

After the 10th round (of 1 band removals + UA vicinity search) the search status is now:

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

Grid with rank 17158: 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 | E 3 F 7 | B 0 2 6 |
| A 6 F E | 0 B C 3 | 4 2 5 D | 8 7 9 1 |
| D 7 9 B | F 2 E 8 | 6 C 0 1 | 5 4 3 A |
+---------+---------+---------+---------+
| 1 C B D | 3 8 5 9 | F A 4 6 | 0 2 7 E |
| 8 A 7 6 | B E 0 F | D 5 3 2 | 9 C 1 4 |
| 9 2 5 F | D 4 7 C | 1 E 8 0 | 3 6 A B |
| E 3 0 4 | 6 A 1 2 | 9 B 7 C | F 8 5 D |
+---------+---------+---------+---------+
| 2 0 1 A | 9 C 3 5 | 7 4 6 E | D F B 8 |
| 3 F 4 7 | A D B 6 | C 8 1 5 | 2 E 0 9 |
| 6 8 D 9 | 7 1 F E | 2 0 B 3 | A 5 4 C |
| B E C 5 | 2 0 8 4 | A D 9 F | 1 3 6 7 |
+---------+---------+---------+---------+
| 5 B 6 0 | 8 7 D 1 | 3 F E A | 4 9 C 2 |
| 7 9 3 1 | C F 4 B | 0 6 2 8 | E A D 5 |
| C 4 E 8 | 5 3 2 A | B 7 D 9 | 6 1 F 0 |
| F D A 2 | E 6 9 0 | 5 1 C 4 | 7 B 8 3 |
+---------+---------+---------+---------+

[coloin]

So you are homing in on the max min-lex grid for Sudoku16 !!!
What are the chances that there will be an automorphic grid with all 4 horizontal bands and all 4 vertical bands the same .... [equiv to band 416 in Sudoku9]
hang about ....
We havent actually found the max min-lex triple row never mind the quad row [band] yet ... but .... you will have a good chance to approach these in your new grid exemplars ...?

[Mathimagics]

Hi coloin!

We haven't actually found the max min-lex triple row never mind the quad row [band] yet ...

Actually we have! I have enumerated all the minlex bands for the highest ranks, and the max 3-row minlex form that I found is this one, with rank 18693:

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 E | F 1 3 7 | B A 0 6 |
| 6 E F A | C B 8 1 | D 0 4 2 | 3 7 5 9 |
| . . . . | . . . . | . . . . | . . . . |
+---------+---------+---------+---------+


No band completions for that rank. The highest-ranked minlex band found is this one, it has 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 |
+---------+---------+---------+---------+


Intriguingly, this band has 48 automorphisms.

[coloin]

Ah .... i see that you indeed had posted the max minlex band which has the initial MR2 rank 18688 before ... but no min lex grid with this
I think that you mentioned that it gets progressively harder to find the complete grids ...which is as ever the case !
And I now see that you are indeed going down the MR3 route where all 3 pairs have higher rank ... very challenging.
Maybe you will find an automorphic grid which has high rank in all bands .... for for all 48 pairs to have high rank is progressively more unlikely..

[Mathimagics]

What are the chances that there will be an automorphic grid with all 4 horizontal bands and all 4 vertical bands the same .... [equiv to band 416 in Sudoku9] ??

Let's call a grid homogenous if all of its bands/stacks are the same: all are some transformation/relabelling of the same root band. For short I'll call these grids H-grids.

Similarly, a H-band is a band which is homogeneous with respect to its rows. So, every row-pair (all 6 of them) in a H-band has the same rank. If an H-grid has an H-band as its root, I'll call that a HB-grid. So, in a HB-grid, every one of its 48 row/col pairs has the same rank. Doubly homogeneous!

I enumerated all of the H-bands a while back, because it was fairly quick to do (compared to most other tasks in the 16x16 world), and also because I thought they might be more likely to produce grid automorphisms. I found that only 788 ranks (4.2% of 18695) have H-bands, and that the total number of H-bands was 226,142.

Now, prompted by coloin's observation above, I produced a first version of my "Band Knitting" program (BK), and used it to test whether any of the H-bands could be knitted together to form a HB-grid. Naturally I started with the highest-ranked cases and worked backwards.

BK isn't very efficient yet (more work is needed), but it works ok, and after a couple of days it found this HB-grid, which has rank 17,411, and 32 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


So, is this the "equivalent" of the 9x9 grid for band 416?

Possibly, but it's really too early to say. If a higher-ranked grid (G) exists, then there are two scenarios:

• G is a H-grid whose root band is not an H-band

• G is a blend of more than one band

It would be nice if we had any way of telling whether the first scenario is even possible. Otherwise there are 100's of millions of minlex bands with rank > 17411 that have to be tested, and so BK will need to be a whole lot faster before we can hope to undertake that search.

And the second scenario is exponentially worse than the first ...