## One-band patterns

Everything about Sudoku that doesn't fit in one of the other sections

### One-band patterns

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 Invalid0 0 0     1      0      10 0 1     1      0      10 0 2     3      0      30 0 3     6      0      60 0 4     7      4      30 0 5     7      6      10 0 6     6      6      00 0 7     3      3      00 0 8     1      1      00 0 9     1      1      00 1 1     2      1      10 1 2     6      5      10 1 3    12     11      10 1 4    16     16      00 1 5    16     16      00 1 6    12     12      00 1 7     6      6      00 1 8     2      2      00 1 9     1      1      00 2 2    12     11      10 2 3    36     35      10 2 4    48     48      00 2 5    48     48      00 2 6    36     36      00 2 7    18     18      00 2 8     6      6      00 2 9     3      3      00 3 3    45     44      10 3 4   100    100      00 3 5   100    100      00 3 6    76     76      00 3 7    36     36      00 3 8    12     12      00 3 9     6      6      00 4 4    76     76      00 4 5   134    134      00 4 6   100    100      00 4 7    48     48      00 4 8    16     16      00 4 9     7      7      00 5 5    76     76      00 5 6   100    100      00 5 7    48     48      00 5 8    16     16      00 5 9     7      7      00 6 6    45     45      00 6 7    36     36      00 6 8    12     12      00 6 9     6      6      00 7 7    12     12      00 7 8     6      6      00 7 9     3      3      00 8 8     2      2      00 8 9     1      1      00 9 9     1      1      01 1 1     3      2      11 1 2    12     11      11 1 3    24     23      11 1 4    32     32      01 1 5    32     32      01 1 6    24     24      01 1 7    12     12      01 1 8     4      4      01 1 9     2      2      01 2 2    27     26      11 2 3    96     95      11 2 4   129    129      01 2 5   129    129      01 2 6    96     96      01 2 7    45     45      01 2 8    15     15      01 2 9     6      6      01 3 3   114    113      11 3 4   280    280      01 3 5   280    280      01 3 6   208    208      01 3 7    96     96      01 3 8    32     32      01 3 9    12     12      01 4 4   202    202      01 4 5   377    377      01 4 6   280    280      01 4 7   129    129      01 4 8    43     43      01 4 9    16     16      01 5 5   202    202      01 5 6   280    280      01 5 7   129    129      01 5 8    43     43      01 5 9    16     16      01 6 6   114    114      01 6 7    96     96      01 6 8    32     32      01 6 9    12     12      01 7 7    27     27      01 7 8    15     15      01 7 9     6      6      01 8 8     4      4      01 8 9     2      2      01 9 9     1      1      02 2 2    38     37      12 2 3   168    167      12 2 4   225    225      02 2 5   225    225      02 2 6   168    168      02 2 7    81     81      02 2 8    27     27      02 2 9    12     12      02 3 3   342    341      12 3 4   840    840      02 3 5   840    840      02 3 6   624    624      02 3 7   288    288      02 3 8    96     96      02 3 9    36     36      02 4 4   606    606      02 4 5  1131   1131      02 4 6   840    840      02 4 7   387    387      02 4 8   129    129      02 4 9    48     48      02 5 5   606    606      02 5 6   840    840      02 5 7   387    387      02 5 8   129    129      02 5 9    48     48      02 6 6   342    342      02 6 7   288    288      02 6 8    96     96      02 6 9    36     36      02 7 7    81     81      02 7 8    45     45      02 7 9    18     18      02 8 8    12     12      02 8 9     6      6      02 9 9     3      3      03 3 3   286    285      13 3 4   990    990      03 3 5   990    990      03 3 6   738    738      03 3 7   342    342      03 3 8   114    114      03 3 9    45     45      03 4 4  1312   1312      03 4 5  2480   2480      03 4 6  1840   1840      03 4 7   840    840      03 4 8   280    280      03 4 9   100    100      03 5 5  1312   1312      03 5 6  1840   1840      03 5 7   840    840      03 5 8   280    280      03 5 9   100    100      03 6 6   738    738      03 6 7   624    624      03 6 8   208    208      03 6 9    76     76      03 7 7   168    168      03 7 8    96     96      03 7 9    36     36      03 8 8    24     24      03 8 9    12     12      03 9 9     6      6      04 4 4   657    657      04 4 5  1766   1766      04 4 6  1312   1312      04 4 7   606    606      04 4 8   202    202      04 4 9    76     76      04 5 5  1766   1766      04 5 6  2480   2480      04 5 7  1131   1131      04 5 8   377    377      04 5 9   134    134      04 6 6   990    990      04 6 7   840    840      04 6 8   280    280      04 6 9   100    100      04 7 7   225    225      04 7 8   129    129      04 7 9    48     48      04 8 8    32     32      04 8 9    16     16      04 9 9     7      7      05 5 5   657    657      05 5 6  1312   1312      05 5 7   606    606      05 5 8   202    202      05 5 9    76     76      05 6 6   990    990      05 6 7   840    840      05 6 8   280    280      05 6 9   100    100      05 7 7   225    225      05 7 8   129    129      05 7 9    48     48      05 8 8    32     32      05 8 9    16     16      05 9 9     7      7      06 6 6   286    286      06 6 7   342    342      06 6 8   114    114      06 6 9    45     45      06 7 7   168    168      06 7 8    96     96      06 7 9    36     36      06 8 8    24     24      06 8 9    12     12      06 9 9     6      6      07 7 7    38     38      07 7 8    27     27      07 7 9    12     12      07 8 8    12     12      07 8 9     6      6      07 9 9     3      3      08 8 8     3      3      08 8 9     2      2      08 9 9     1      1      09 9 9     1      1      0Totally processed 220 bandsPatterns in total: 51912Valid patterns:    51881Invalid 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
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

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
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

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
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

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
dobrichev
2016 Supporter

Posts: 1621
Joined: 24 May 2010

### Re: One-band patterns

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
coloin

Posts: 1737
Joined: 05 May 2005

### Re: One-band patterns

Hi, dobrichev!
dobrichev wrote: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.
dobrichev wrote: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.
dobrichev wrote: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]
Last edited by Serg on Thu Apr 05, 2012 3:49 pm, edited 1 time in total.
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

Hi, coloin!
coloin wrote: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
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

Serg wrote: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.
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: One-band patterns

Hi, Red Ed!
Red Ed wrote:
Serg wrote: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 .

Serg
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

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,productfrom math import factorialBANDS,ROWS,STACKS,COLS = 3,3,3,3   ### you can edit thisDO_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 ncyctotal = 0for 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`
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: One-band patterns

Hi, Red Ed!
Red Ed wrote: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

Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

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.]
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

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
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

### Re: One-band patterns

Hi, JPF!
JPF wrote: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).
JPF wrote: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
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: One-band patterns

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.]
Last edited by Serg on Fri Jun 15, 2012 7:21 am, edited 1 time in total.
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

Next