The New Sudoku Players' Forum

[Serg]

Hi, all!
I studied patterns occupying alone band (stack) of the grid. Here is an example of such pattern:

Code: Select all

+-----+-----+-----+
|. . .|. . .|. . x|
|. . .|. . .|. x x|
|. . .|. . x|. . .|
+-----+-----+-----+

As usual "x" denotes band's cells which must contain puzzle's clues.

How many are there essentially different one-band patterns?

I assume common set of isomorphic transformations:
1. Boxes permutations (6 ways).
2. Rows permutations within the band (6 ways).
3. Columns permutations within B1 box (6 ways).
4. Columns permutations within B2 box (6 ways).
5. Columns permutations within B3 box (6 ways).

2 patterns are called isomorphic when the first pattern can be transformed to the second pattern by some sequence of isomorphic transformations.
There are 2^27 one-band patterns in total (band contains 27 cells, each cell can belong or not belong to the pattern) = 134217728 patterns.
A pattern can have at most 7776 isomorhic patterns (6^5). So, there can exist not less than 134217728/7776 = 17260.51 essentially different one-band patterns. Real number of such patterns is certainly higher because of automorphisms - "average" pattern has less than 7776 isomorhic patterns.

I wrote special program to count all essentially different one-band patterns. It turns out, there are 51912 essentially different one-band patterns.

But some of such one-band patterns cannot participate patterns of valid sudoku puzzles, because they contain, for example, 2 empty rows. Let me call such one-band patterns invalid (valid one-band patterns can participate patterns of valid sudoku puzzles). To filter out invalid patterns one should consider not only patterns having empty rows, but also patterns having 2 empty boxes and third box containing less than 4 clues (see thread Investigation of one-band-free patterns on this forum). It turns out that there are 31 invalid one-band patterns only. So, there exist 51912-31=51881 valid one-band patterns.

To present my results in details I should consider band maps. Such map has 3 digits - one digit per box, denoting number of clues of each box. For example, posted above band has map

Code: Select all

0 1 3

We shall consider ordered band maps where boxes are sorted in such way that B2 box has not less clues than B1 box and B3 box has not less clues than B2 box. There are 220 ordered band maps (simple combinatoric calculation - starting with "0 0 0" map and ending with "9 9 9" map).

Here are more detailed results for all 220 different band maps.

Code: Select all

Band  Patterns Valid Invalid

0 0 0     1      0      1
0 0 1     1      0      1
0 0 2     3      0      3
0 0 3     6      0      6
0 0 4     7      4      3
0 0 5     7      6      1
0 0 6     6      6      0
0 0 7     3      3      0
0 0 8     1      1      0
0 0 9     1      1      0
0 1 1     2      1      1
0 1 2     6      5      1
0 1 3    12     11      1
0 1 4    16     16      0
0 1 5    16     16      0
0 1 6    12     12      0
0 1 7     6      6      0
0 1 8     2      2      0
0 1 9     1      1      0
0 2 2    12     11      1
0 2 3    36     35      1
0 2 4    48     48      0
0 2 5    48     48      0
0 2 6    36     36      0
0 2 7    18     18      0
0 2 8     6      6      0
0 2 9     3      3      0
0 3 3    45     44      1
0 3 4   100    100      0
0 3 5   100    100      0
0 3 6    76     76      0
0 3 7    36     36      0
0 3 8    12     12      0
0 3 9     6      6      0
0 4 4    76     76      0
0 4 5   134    134      0
0 4 6   100    100      0
0 4 7    48     48      0
0 4 8    16     16      0
0 4 9     7      7      0
0 5 5    76     76      0
0 5 6   100    100      0
0 5 7    48     48      0
0 5 8    16     16      0
0 5 9     7      7      0
0 6 6    45     45      0
0 6 7    36     36      0
0 6 8    12     12      0
0 6 9     6      6      0
0 7 7    12     12      0
0 7 8     6      6      0
0 7 9     3      3      0
0 8 8     2      2      0
0 8 9     1      1      0
0 9 9     1      1      0
1 1 1     3      2      1
1 1 2    12     11      1
1 1 3    24     23      1
1 1 4    32     32      0
1 1 5    32     32      0
1 1 6    24     24      0
1 1 7    12     12      0
1 1 8     4      4      0
1 1 9     2      2      0
1 2 2    27     26      1
1 2 3    96     95      1
1 2 4   129    129      0
1 2 5   129    129      0
1 2 6    96     96      0
1 2 7    45     45      0
1 2 8    15     15      0
1 2 9     6      6      0
1 3 3   114    113      1
1 3 4   280    280      0
1 3 5   280    280      0
1 3 6   208    208      0
1 3 7    96     96      0
1 3 8    32     32      0
1 3 9    12     12      0
1 4 4   202    202      0
1 4 5   377    377      0
1 4 6   280    280      0
1 4 7   129    129      0
1 4 8    43     43      0
1 4 9    16     16      0
1 5 5   202    202      0
1 5 6   280    280      0
1 5 7   129    129      0
1 5 8    43     43      0
1 5 9    16     16      0
1 6 6   114    114      0
1 6 7    96     96      0
1 6 8    32     32      0
1 6 9    12     12      0
1 7 7    27     27      0
1 7 8    15     15      0
1 7 9     6      6      0
1 8 8     4      4      0
1 8 9     2      2      0
1 9 9     1      1      0
2 2 2    38     37      1
2 2 3   168    167      1
2 2 4   225    225      0
2 2 5   225    225      0
2 2 6   168    168      0
2 2 7    81     81      0
2 2 8    27     27      0
2 2 9    12     12      0
2 3 3   342    341      1
2 3 4   840    840      0
2 3 5   840    840      0
2 3 6   624    624      0
2 3 7   288    288      0
2 3 8    96     96      0
2 3 9    36     36      0
2 4 4   606    606      0
2 4 5  1131   1131      0
2 4 6   840    840      0
2 4 7   387    387      0
2 4 8   129    129      0
2 4 9    48     48      0
2 5 5   606    606      0
2 5 6   840    840      0
2 5 7   387    387      0
2 5 8   129    129      0
2 5 9    48     48      0
2 6 6   342    342      0
2 6 7   288    288      0
2 6 8    96     96      0
2 6 9    36     36      0
2 7 7    81     81      0
2 7 8    45     45      0
2 7 9    18     18      0
2 8 8    12     12      0
2 8 9     6      6      0
2 9 9     3      3      0
3 3 3   286    285      1
3 3 4   990    990      0
3 3 5   990    990      0
3 3 6   738    738      0
3 3 7   342    342      0
3 3 8   114    114      0
3 3 9    45     45      0
3 4 4  1312   1312      0
3 4 5  2480   2480      0
3 4 6  1840   1840      0
3 4 7   840    840      0
3 4 8   280    280      0
3 4 9   100    100      0
3 5 5  1312   1312      0
3 5 6  1840   1840      0
3 5 7   840    840      0
3 5 8   280    280      0
3 5 9   100    100      0
3 6 6   738    738      0
3 6 7   624    624      0
3 6 8   208    208      0
3 6 9    76     76      0
3 7 7   168    168      0
3 7 8    96     96      0
3 7 9    36     36      0
3 8 8    24     24      0
3 8 9    12     12      0
3 9 9     6      6      0
4 4 4   657    657      0
4 4 5  1766   1766      0
4 4 6  1312   1312      0
4 4 7   606    606      0
4 4 8   202    202      0
4 4 9    76     76      0
4 5 5  1766   1766      0
4 5 6  2480   2480      0
4 5 7  1131   1131      0
4 5 8   377    377      0
4 5 9   134    134      0
4 6 6   990    990      0
4 6 7   840    840      0
4 6 8   280    280      0
4 6 9   100    100      0
4 7 7   225    225      0
4 7 8   129    129      0
4 7 9    48     48      0
4 8 8    32     32      0
4 8 9    16     16      0
4 9 9     7      7      0
5 5 5   657    657      0
5 5 6  1312   1312      0
5 5 7   606    606      0
5 5 8   202    202      0
5 5 9    76     76      0
5 6 6   990    990      0
5 6 7   840    840      0
5 6 8   280    280      0
5 6 9   100    100      0
5 7 7   225    225      0
5 7 8   129    129      0
5 7 9    48     48      0
5 8 8    32     32      0
5 8 9    16     16      0
5 9 9     7      7      0
6 6 6   286    286      0
6 6 7   342    342      0
6 6 8   114    114      0
6 6 9    45     45      0
6 7 7   168    168      0
6 7 8    96     96      0
6 7 9    36     36      0
6 8 8    24     24      0
6 8 9    12     12      0
6 9 9     6      6      0
7 7 7    38     38      0
7 7 8    27     27      0
7 7 9    12     12      0
7 8 8    12     12      0
7 8 9     6      6      0
7 9 9     3      3      0
8 8 8     3      3      0
8 8 9     2      2      0
8 9 9     1      1      0
9 9 9     1      1      0

Totally processed 220 bands

Patterns in total: 51912
Valid patterns:    51881
Invalid patterns:     31


Let's consider, for example, band map "1 1 1". As you can see from the table posted above, there are 3 non-isomorphic patterns for this map, but 1 pattern is invalid, so there are 2 valid non-isomorphic patterns for this map.

Here are all non-isomorphic patterns for map "1 1 1":

Code: Select all

+-----+-----+-----+          +-----+-----+-----+          +-----+-----+-----+
|. . .|. . .|. . .|          |. . .|. . .|. . .|          |. . .|. . .|. . x|
|. . .|. . .|. . .|          |. . .|. . .|. . x|          |. . .|. . x|. . .|
|. . x|. . x|. . x|          |. . x|. . x|. . .|          |. . x|. . .|. . .|
+-----+-----+-----+          +-----+-----+-----+          +-----+-----+-----+

As you can see, the first pattern is invalid, because it contains 2 empty rows. So, there exist 2 valid non-isomorphic patterns for this map.

It is worth noting that 2 maps ("3 4 5" and "4 5 6") have maximal number of patterns - 2480. This is because boxes containing 4 or 5 clues have maximal numbers of clues placement variants (7).

Note that every band (stack) of every valid sudoku pattern has one of the posted above form (up to isomorhisms).

Continuation follows...

Serg

[Serg]

Hi, people!
Here are some theoretic considerations concerning one-band patterns.

Definition.
Pattern A is called complementary to pattern B, if each band cell belongs to one of 2 sets only, but not to both - set of pattern A cells containing clues and set of pattern B cells containing clues.

Example of complementary one-band patterns:

Code: Select all

+-----+-----+-----+          +-----+-----+-----+
|. . .|. . .|. . .|          |x x x|x x x|x x x|
|. . .|. . .|. . x|          |x x x|x x x|x x .|
|. . x|. . x|. x .|          |x x .|x x .|x . x|
+-----+-----+-----+          +-----+-----+-----+

If we consider all one-band patterns having the same band map, we'll find that all complementary one-band patterns of these patterns have the same band map. This map can be produced by complementing each digit of the band to digit "9" and reordering produced band map. Such band maps are called complementary too.

The first band of the above example has band map

Code: Select all

1 1 2

The second band of the above example (complementary) has band map

Code: Select all

7 8 8

Lemma 1.
Both complementary band maps have the same number of patterns (valid and invalid).

Proof.
"Complementation" transformation commutes with each isomorphic transformation of the band (no matter what is done first - complementation or boxes/rows/columns permutations, result will be the same). So, if 2 band patterns are isomorphic to each other, 2 band patterns being complementary to these band patterns are isomorphic to each other too. And vice versa.

Lemma 2.
There is no "autocomplementary" one-band patterns, i.e. complementary pattern of any one-band pattern cannot be isomorphic to original pattern.

Proof.
Let's consider band maps of original one-band pattern and its complementary pattern. Let's denote by "N1 N2 N3" band map of original pattern and by "C1 C2 C3" - band map of complementary pattern. Then C1 = 9 - N1 or C2 = 9 - N1 or C3 = 9 - N1. Assume that autocomplementary one-band pattern exists. Then N1 = 9 - N1 or N2 = 9 - N1 or N3 = 9 - N1. But N is not equal to 9 - N for N = 0,1, ..., 9. Let's treat N2 = 9 - N1. We should consider several variants for N3 digit.
a) N3 != N1 and N3 != 9 - N1. Then 9 - N3 != N1 and 9 - N3 != 9 - N1 (i.e. != N2) and 9 - N3 != N3. So, complementary band map differs from original band map at least by one digit.
b) N3 = N1. Original band map: "N1 N2 N1", complementary band map: "N2 N1 N2" (note that N1 != N2). So, complementary band map differs from original band map.
c) N3 = 9 - N1. Original band map: "N1 N2 N2", complementary band map: "N2 N1 N1" (note that N1 != N2). So, complementary band map differs from original band map.
Therefore our assumption about autocomplementary one-band pattern existance is wrong.

Theorem.
Total number of non-isomorphic one-band patterns (valid and invalid) is even.

Proof.
Let's consider all possible (220) band maps. That maps can be divided by pairs such that each pair contains original band map and its complementary band map because complementation of complementary one-band pattern coincides with original one-band pattern and there is no autocomplementary one-band patterns. So, total number of non-isomorphic one-band patterns (valid and invalid) must be even.

I used "Lemma 1" and "Theorem" results to cross-check my program.

Serg

[Serg]

Hi, all!
Some final considerations.

What about number of all essentially different sudoku grid patterns?
I can estimate this number using approach from my post in this thread.
I assume common set of grid isomorphic transformations:

1. Transposing (2 ways).
2. Bands permutations (6 ways).
3. Rows permutations within the band B123 (6 ways).
4. Rows permutations within the band B456 (6 ways).
5. Rows permutations within the band B789 (6 ways).
6. Stacks permutations (6 ways).
7. Columns permutations within the stack B147 (6 ways).
8. Columns permutations within the stack B258 (6 ways).
9. Columns permutations within the stack B369 (6 ways).

So, the maximal number of different patterns being isomorphic to each other - 2 x 6^8 = 3359232.

Possible number of sudoku grid patterns: 2^81 = 2 x 10^24 (approx.)

Number of all essentially different sudoku grid patterns cannot be less than 2^81/3359232 = 6 x 10^17 (approx.)

It would be interesting to know exact number of all essentially different sudoku grid patterns.

Serg

[dobrichev]

Hi Serg,

I expected different continuation of your last work - estimation of some upper limit of patterns capable to generate minimal puzzles.
Is it possible to reduce further the 51881 ED patterns adding minimality constraint like max 8 givens in a row/box?
Next, is it too complex to combine in 9 boxes the 3 boxes of these 51881 one-band patterns? Are there some logical simplifications?

Cheers,
MD

[coloin]

Hi serg.
Yes we could take it a bit furthur

What about trying to estimate the number of patterns with n clues [n is 17-39]

From this we could have an estimate of the number of minimal puzzles per n-clue pattern

Given that the average number of minimal puzzles per grid solution is 5e14 [?]
This means that there are approx 2e24 total minimal puzzles
picking n=25 and we know the distribution of puzzles ? 1/5 ? have 25 clues
This means that maybe there are 4e23 puzzles with 25 clues
number of ways to have 25 clues = 81!/56! *25! ~ 5e20
reducing by 6^8 *2 ~3e6 = 2e14 different patterns

number of minimal puzzles per pattern might be 4e23 /2e14
= 2e9 minimal puzzles per 25 clue pattern

hmmm

[Serg]

Hi, dobrichev!

I expected different continuation of your last work - estimation of some upper limit of patterns capable to generate minimal puzzles.

Do you mean systematic studies like "One-clue-boxes patterns"? The main my problem in this scope - I cannot see yet general concept to schedule correctly such investigations. So, I do such studies in "on demand" style, to solve some applied task like "search for 16-clue valid puzzles", etc. For example, study "One-clue-boxes patterns" was done in the scope of searching for 16-clue valid puzzles. Now I changed my plans in some extent. This is my "roadmap" now:

1. Exhaustive search for 17-clue valid puzzles.
a) Coding a program which can tell - how many patterns has given map (puzzle map). I hope, at this stage I'll be capable to determine exact number of all ED patterns for 17-clue valid puzzles.
b) Publishing a variant of universal classification of valid puzzles (my approach) to show directions of exhaustive search for 17-clue valid puzzles.
c) Coding "bulldozer" program, doing exhaustive search for given map (i.e. class of patterns). I think, I have appropriate algorithm for this program.
d) Using "bulldozer" program to combine checking out particular 17-clue maps with investigations like "One-clue-boxes patterns" to exclude families of maps, not containing valid puzzles.

2. Exhaustive search for 16-clue valid puzzles. I think it will be much simpler than doing such search "from scratch", because "composition rules" collected during 17-clue valid puzzles should significally reduce search space for 16-clue valid puzzles. (It turns out that my "composition rules" collected during proof of non-existence of 11-clue valid puzzles allowed me to reduce 6 times search space for 17-clue valid puzzles.)

3. Exhaustive search for symmetric 18-clue valid puzzles.

Results posted in this thread were obtain in the scope of 1a point. Surely I cannot say right now when all these tasks will be done or can they be done at all.

Is it possible to reduce further the 51881 ED patterns adding minimality constraint like max 8 givens in a row/box?

I don't see a way to do it working with one band only.

Next, is it too complex to combine in 9 boxes the 3 boxes of these 51881 one-band patterns? Are there some logical simplifications?

Yes, it is too complex. I said about it for completeness only.

Thanks, Serg
[Edited: I corrected some typos]

[Serg]

Hi, coloin!

What about trying to estimate the number of patterns with n clues [n is 17-39]

Now I have maps generator for n-clue valid puzzles. In some time I expect to have patterns generator for given map. Then it will be possible to compute number of patterns for ED n-clue puzzles exactly.

According to my estimates there are much more possible patterns for 39-clue puzzles than for low-clue puzzles (17-clue, 18-clue puzzles). So, I think, exhaustive search for minimal 39-clue valid puzzles is much more complicated than exhaustive search for 17-clue valid puzzles.

Serg

[Red Ed]

Number of all essentially different sudoku grid patterns cannot be less than 2^81/3359232 = 6 x 10^17 (approx.)

It would be interesting to know exact number of all essentially different sudoku grid patterns.

I don't know why that's interesting, but I make it 746186061249180790. Could be wrong: the code's not well-tested.

[Serg]

Hi, Red Ed!

Number of all essentially different sudoku grid patterns cannot be less than 2^81/3359232 = 6 x 10^17 (approx.)

It would be interesting to know exact number of all essentially different sudoku grid patterns.

I don't know why that's interesting, but I make it 746186061249180790. Could be wrong: the code's not well-tested.

I don't know why, but it is interesting for me .

You published impressive result! Please, describe your method.

Serg

[Red Ed]

Please, describe your method.

Just like in the counting of essentially-different solution grids, one can use Burnside's Lemma: the number of e-d configurations is the average, over all elements of the symmetry group, of the number of configurations fixed by that element. (If every group element except the identity changed every grid configuration then that average would be 2^81 / 3359232, which is your 6e17 lower bound.)

The number of configurations fixed by a permutation (i.e. an element of the symmetry group) is equal to 2^C where C is the number of cycles in the permutation, because all cells within any cycle must have the same filled-vs.-unfilled status.

That 2^C trick saves a lot of time so that no further optimisations (like looping over the 275 conjugacy classes rather than the whole group of 3359232 elements) are necessary. The algorithm runs in reasonable time even when implemented in Python:

Code: Select all

from itertools import permutations,product
from math import factorial

BANDS,ROWS,STACKS,COLS = 3,3,3,3   ### you can edit this

DO_TRANSPOSE = ( (BANDS,ROWS) == (STACKS,COLS) )

def Wreath(x,y):
    def Wr2(x,y):
        if x == 0: yield []
        else:
            for yp in permutations(range(y)):
                for w in Wr2(x-1,y):
                    yield [yp] + w
    for xp in permutations(range(x)):
        for yp in Wr2(x,y):
            yield (xp,yp)

def wrop(bprp,b,r):
    return (bprp[0][b],bprp[1][b][r])

def cycles(bprp,spcp,transpose):
    todo = set()
    for b,r in product(range(BANDS),range(ROWS)):
        for s,c in product(range(STACKS),range(COLS)):
            todo.add( (b,r,s,c) )
    ncyc = 0
    while todo:
        ncyc += 1
        b,r,s,c = todo.pop()
        b2,r2,s2,c2,start = b,r,s,c,True
        while start or (b2,r2,s2,c2) != (b,r,s,c):
            if not start: todo.remove( (b2,r2,s2,c2) )
            if transpose: s2,c2,b2,r2 = wrop(bprp,b2,r2) + wrop(spcp,s2,c2)
            else:         b2,r2,s2,c2 = wrop(bprp,b2,r2) + wrop(spcp,s2,c2)
            start = False
    return ncyc

total = 0
for bprp in Wreath(BANDS,ROWS):
    print bprp   ### some sort of progress indicator
    for spcp in Wreath(STACKS,COLS):
        total += 1 << cycles(bprp,spcp,False)
        if DO_TRANSPOSE:
            total += 1 << cycles(bprp,spcp,True)

ed  = total / (1+DO_TRANSPOSE)
ed /= factorial(BANDS)
ed /= pow(factorial(ROWS),BANDS)
ed /= factorial(STACKS)
ed /= pow(factorial(COLS),STACKS)

print ed

[Serg]

Hi, Red Ed!

The number of configurations fixed by a permutation (i.e. an element of the symmetry group) is equal to 2^C where C is the number of cycles in the permutation, because all cells within any cycle must have the same filled-vs.-unfilled status.

That 2^C trick saves a lot of time so that no further optimisations (like looping over the 275 conjugacy classes rather than the whole group of 3359232 elements) are necessary.

Nice idea! I need some time to ponder your algorithm.

Serg

P.S. I'll have no access to Internet till April, 15.

[Serg]

Hi, Red Ed!
Though I don't understand Python programming language, but I see you publish the universal program being capable of all essentially different patterns calculation for grid having any formfactor (for example, 8x8, 4x4, etc.). Great! Program itself is elegant and short.

I certainly saw the way of counting all e-d patterns by Burnside's Lemma, but I couldn't find a way of counting number of patterns fixed by given isomorphic transformation. So, I thought this task can be done for several months, but you could do it for several days. Congratulations! I've never seen before that such complicated task can be solved so fast.

I'll try to cross-check your result using C program.

Serg

[Edited: I corrected a typo.]

[JPF]

We can also simply use the results given by Red Ed here:

n=0
For each of the 275 conjugacy classes:
n= n+ size*2^C*2^S
Next
n=n/3359232

Then we get the expected result n = 746186061249180790

size is the size of the conjugacy class
C is the number of cycles of the permutation
S is the number of cells not present in the cycles of the permutation.

Btw, Serg, I don't understand the value you gave for 2^81 / 3359232
Isn't it 7.2e17 instead of 6e17 ?

JPF

[Serg]

Hi, JPF!

We can also simply use the results given by Red Ed here:

n=0
For each of the 275 conjugacy classes:
n= n+ size*2^C*2^S
Next
n=n/3359232

Then we get the expected result n = 746186061249180790

size is the size of the conjugacy class
C is the number of cycles of the permutation
S is the number of cells not present in the cycles of the permutation.

I am glad that you cross-checked Red Ed's result. I think similar technique (using VPT conjugacy classes) can be used to determine numbers of e-d patterns for N-clue patterns (say, for 17-clue patterns).

Btw, Serg, I don't understand the value you gave for 2^81 / 3359232
Isn't it 7.2e17 instead of 6e17 ?

The cause is bad approximation. "1000" is good approximation for "2^10", but "10^24" is not good approximation for "2^80", because 1.024^8 = 1.2 (approx.).
So, right you are, 2^81 / 3359232 = 7.2e17.
Thanks for this correction.

Serg

[Serg]

Hi, people!
I've independently checked the number of essentially different one-band patterns. Following Red Ed's method described above in this thread, I counted number of of essentially different one-band patterns, using Burnside's Lemma. I got 51912 essentially different patterns (patterns having 2 empty rows (columns) in a band (stack) were not filtered out), that matches my previous result gotten by another method. CPU time < 1 sec.

Serg

[Edited: my conjugacy classes calculation procedure has a bug, so I recalculated essentially different one-band patterns still using Burnside's Lemma, but directly, without usage conjugacy classes.]