The New Sudoku Players' Forum

[maarten.j.meijer]

Insight 1: MOAS (Mother Of All Sudoku)

Some terminology first:

Code: Select all

<-triplet->        <-triplet->        <-triplet->
1    2    3        4    5    6        7    8    9 <row>
4    5    6        7    8    9        1    2    3
7    8    9        1    2    3        4    5    6

2    3    4        5    6    7        8    9    1
5    6    7        8    9    1        2    3    4
8    9    1        2    3    4        5    6    7

3    4    5        6    7    8        9    1    2
6    7    8        9    1    2        3    4    5
9    1    2        3    4    5        6    7    8


This is the very simple and valid base SUDOKU from which we can create ALL other sudoku puzzles. (hunch, but no proof at this moment)

Insight 2: Allowed transformations that keep it valid:

1) any two columns within a vertical triplet may be exchanged

2) any two rows within a horizontal triplet may be exchanged

3) any two vertical triplets may be exchanged

4) any two horizontal triplets may be exchanged

5) at any time the whole 9x9 thing can be rotated 90 degrees left or right
(Though I think this operation can be made up from a sequence the above)

6) at anytime the whole 9x9 thing can be mirrored along vertical, diagonal, or horizontal center line
(Though I think this operation too can be made up from a sequence the above)

7) as mentioned above, as the numbers are nominal (unlike in magic squares) any two numbers can be exchanged throughout the grid
(Though I think this operation yet again can be made up from a sequence the above)

Applying these transformations leads to a large, but not infinite number of SUDOKU.

Insight 3: Hiding = Compression

The next step after randomizing the layout is to HIDE certain numbers without making the thing insolvable. This is where I need to brush up on my information theory, but I think you can reduce it to a minimum number of digits which is determined by Huffman's theory...

Basically the SUDOKU validity rules allow compressing the total grid.
So HIDING numbers is like compressing the information in the completed SUDOKU. To have a SUDOKU with a single solution, you need lossless compression, so limited by huffman's theory. In layman's terms: the minimum possible number of digits to be shown depends entirely on their position as this is part of the compression scheme.

Insight 4: multiple solutions = lossy compression

If you remove more digits than the limit, you get multiple solutions. This follows also from logic: if you hide all numbers you can fill in any valid sudoku!

Insight 5: compression and transformation are commutative

Just another hunch: if you find the maximum numbers you can hide in the MOAS, applying all the transformations still leaves you with a solvable SUDOKU. This is useful for SUDOKU generator writers: you can have base: easy, medium, hard and generate from there.

So all have a nice weekend!

Maarten Meijer

[dukuso]

@patmaxDaddy:
--------------------

Your description was hard to read and understand, so let me describe
how I would do it using that B12347-method, which I think is
inferior to the B123-method.
Maybe you can confirm that this is essentially what you did:



there are essentially 2802 different ways to form a valid
B12347-subsudoku.
This is a sudoku-grid where the 36 entries in blocks 5,6,8,9 are set to zero.
(I do remember that 2802 is the magic number of
this method, still I couldn't find it in your message.)


Two such B12347-subsudokus are "essentially the same" ,
if the 4*3 sets of symbols in the minicolumns of B2,B3 and in the minirows
of B4,B7 are equivalent.

Equivalent, that is modulo :
permuting minirows in B4 or B7,
permuting minicolumns in B2,B3,
swapping B2 with B3,
swapping B4 with B7,
transposing (=mirroring on the main diagonal),
permuting symbols

As I said, then we get only 2802 classes.
Now, for each of these 2802 compute the number of different
B12347s in the class and the number of solutions of the puzzle
formed by the 45 entries of B12347 and the 36 blanks in B5689.
By design this solution number is an invariant
of our equivalence-class.

Now add these 2802 products of those 2 numbers to get the well known 6.67e21

-Guenter.

[Red Ed]

"Not yet mentioned" ? I disagree. Much of this has been covered already.

Insight 1: MOAS (Mother Of All Sudoku)
...
Insight 2: Allowed transformations that keep it valid:
...
Applying these transformations leads to a large, but not infinite number of SUDOKU.

There's no such thing as a MOAS, at least not using the transformations you described. Your transformations form a group of 9! x 3359232 elements, as described on Frazer's web page. These ops partition the set of 6.67e21 sudokus into 5472730538 classes. So there's not one Mother of All Sudokus, but 5472730538 Mothers of Some Sudokus.

Insight 3: Hiding = Compression
...
Insight 4: multiple solutions = lossy compression
...

I don't think information theory is going to help us. A simple counting argument says that if every clue divides the space of solutions by 8ish then you need ~log(6.67e21)/log(8) = 24ish clues on average. But we don't want the average, we want the minimum. For an idea of the spread, see Guenter's stats.

Insight 5: compression and transformation are commutative

Just another hunch: if you find the maximum numbers you can hide in the MOAS, applying all the transformations still leaves you with a solvable SUDOKU. This is useful for SUDOKU generator writers: you can have base: easy, medium, hard and generate from there.

Mmm... yes, but it's nice to have a range of attractive clue positions and you can't get the full set just from the transformations you listed. That said, it might be "fun" to apply nauty to an archive of newspaper puzzles to see if any publisher has been as devious as you suggest.

[PatmaxDaddy]

... Maybe you can confirm that this is essentially what you did...

First, thanks for reading and commenting, and sorry for any difficulty in understanding.

I definitely used a B12347 method, to use your terminology, and I definitely take advantage of all of the equivalences that you mentioned, but I don't use 2802 classes. From your messages it's not clear whether the B12347 / 2802 method was suggested but abandoned when a better method was found, or whether it was actually run and found to yield the 6.67e21 result.

Since I am a latecomer to the game, I think it's my responsibility to study the prior methods more carefully and comment on how mine compares, rather than expecting the pioneers to do the work for me. So I'm going to consider the 2802 number more carefully, try some ideas that your comments have inspired, and have a closer look at the prior methods. I'll post answers as I get them. Thanks again.

-- Bill (PatmaxDaddy)
Weston, MA, USA

[dukuso]

Bill,

it could be in the math-thread or in the minimum-clues-thread.
It should be on about 6th August

We did the B12347 - method after we had already found and confirmed
the 6.7e21 number with better methods.
The purpose was not to verify that number again (hmm, what was
the purpose ?)
It seems somehow reasonable that I verified the 2802-result by
recalculating the 6.7e21, but I don't remember exactly.
Maybe I can lookup my old files.


OK, here is a link:
http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=318

seems that I didn't use it to recalculate the 6.7e21.
Too difficult to keep track of the members in each of the 2802 classes

[dukuso]

let T be the set of all 12-tuples (x(1),x(2),..,x(12))
of 3-subsets of {1,2,3,4,5,6,7,8,9}
such that x(3*i)+x(3*i-1)+x(3*i-2)={1,2,3,4,5,6,7,8,9} for i=1..4
(+:set-union)

(Interpreted as sets of digits in the minicolumns of B2,B3
and the sets of digits in the minirows of B4,B7 )

T has 1680^4 elements.

Define an equivalence relation on T generated by these 11
permutations on the x(i): (in cycle-notation)

(1,2,3),(1,2),(4,5,6),(4,5),(7,8,9),(7,8),(10,11,12),(10,11),
(1,4)(2,5)(3,6),(7,10)(8,11)(9,12),(1,7)(2,8)(3,9)(4,10)(5,11)(6,12)

and by permuting the digits 1..9 in all the x(i) simultaneously.


This gives 2865 equivalence classes c(1),..,c(2865).

Lets s(i) be the size of class c(i) and let
A(i) be a B12347 grid compatible with c(i) and B(i) be a
B5689 puzzle compatible with the complement of c(i).
So, if c(i)=(x(1),..,x(12)) then A(i) is zero on B5689
and the elements in column c are the sets x(c-3) and the
elements in row r are the sets x(r+3) r,c=4..9.
B(i) is zero on B12347 and the elements in column c are
the sets {1,2,3,4,5,6,7,8,9}-x(c-3) and the elements in
row r are the sets {1,2,3,4,5,6,7,8,9}-x(r+3) r,c=4..9.


Then the total number of sudoku grids is the sum over all
the 2865 classes c(i) of

s(i)*S(A(i))*S(B(i))

where S(P) is the number of (sudoku-)solutions of puzzle P.

S(A(i)) is 2708 in average
S(B(i)) is 315464 in average

1680^4*2708*315464 = 6.81e21 gives a good estimate already.
But 1680^4 are too many summands, so we group them according
to the classes c(i).

We have a goup G=G1*G2 acting on T, G1 has 6^4*8
transformations and G2 is the permutation group of size 9!.
The s(i) could be computed by converting the c(i) into a graph
( 61 vertices for cells,symbols,columns,blocks)
with same automorphismgroup as the isotropy group
of c(i) and then using Nauty to compute its size a(i).
We have s(i)=6^4*8*9!/a(i).
A direct backtracking program found 11015200
3*12 arrays with numbers from {1,2,..,9} with
no same digits in any of the 4 blocks,
with the first block being sorted as 123456789
with the 3 entries in all 12 columns sorted
the 3 columns in all 4 blocks sorted,
block3 <= block4

These 11015200 were filtered and nonminimal members
in a T-class were removed in several steps until 2865
minimal ones remained. This process took 20-30 min.

Calculating the S(A(i)) and S(B(i)) took another 20 min.
with Aart's program.
The correct sum of 6670903752021072936960 was obtained,
so it should be correct this time, correcting the earlier calculation
with 2802 classes.

A file with one B2347 puzzle (B1 is forced) from each class is at
http://magictour.free.fr/2865.gz

-Guenter

[Ocean]

Surprisingly I have not been able to find discussions of these two open problems:


1. What is the number of UNIQUE VALID SUBGRIDS?
2. What is the number of unique valid subgrids with N clues?

(Where a "Unique Valid Subgrid" means a puzzle with one and exactly one solution).




Some trivial numbers:

The total number of subgrids with zero, one or many solutions, is 10^81 - covering all from 0 to 81 clues.

For each valid grid, we can find 2^81 (=2.4e24) subgrids where that particular grid is a solution (mostly among other solutions).

For each valid grid, we can find "81 over N" subgrids with N clues, where that particular grid is among the solutions.


(81 over 15) = 8.1e+15
(81 over 16) = 3.3e+16
(81 over 17) = 1.2e+17
(81 over 18) = 4.5e+17
(81 over 19) = 1.5e+18
(81 over 20) = 4.6e+18
(81 over 21) = 1.3e+19
(81 over 22) = 3.7e+19
(81 over 23) = 9.5e+19
(81 over 24) = 2.3e+20
(81 over 25) = 5.2e+20


Since there are 6670903752021072936960 valid sudokugrids (from 5472730538 equivalence classes), we have the upper bounds:

the number of valid subgrids is less than 2^81 * 6670903752021072936960 (=1.61e46).

(and also: the number of essentially different valid subgrids is less than 2^81 * 5472730538 [=1.3e34]).

The number of unique valid subgrids is probably a lot lower than these upper bounds, but still a huge number.


In the 'Minimum number of clues' thread there is an interesting debate over whether the number of unique valid subgrids with 16 clues is greater than zero or not, and also estimates (guesses?/calculations?) of the number of unique valid subgrids with 17 clues. But I have not seen the general problem discussed - how many (nonequivalent) puzzles are possible. Any pointers to such discussions will be appreciated!

[dukuso]

sudokugrids:1e22 from 1e10 classes
sudokus:1e47 from 1e35 classes (1-solution)
minimal sudokus:1e37 from 1e25 classes (no superfluous clues)

[PatmaxDaddy]

Guenter,

Thanks for the explanation of the 2802 method. This is NOT the method I used, so I think my method represents a truly independent confirmation (both an independent program and an independent method).

I do not handle permuting the digits 1..9 (what I call "renaming the symbols") as an equivalence relation on B2347. Instead I just pick one particular permutation of the symbols for B1, and let B2347 follow from that.

Your x(1),x(2),x(3) is what I call a column triplet of B2; x(7),x(8),x(9) is a row triplet of B4; and likewise for the other x's. For the permutations of the minicolumns of B2 and B3, or the minirows of B4 and B7, I pick one permutation of the six using my S function to make a row/column class.

The 1680^4 combinations of B2347 are reduced to 280^4 by using my classes instead of triplets. B1 constrains this to 252^4. Using my "straight hand" analysis further reduces this to about (252 * 176.6)^2 combinations. Symmetries resulting from swapping B2/B3, B4/B7, or B23/B47 (equivalent to the second line of your 11 permutations) further reduces this to about (252 * 176.6)^2 / 7.95, just under 250,000,000 combinarions. I analyze every one of these; there is no further reduction in equivalence classes. It's a lot of work, but the bookkeeping is managable.

For each of the 250,000,000 combinations of B2347, I need to count the number of B5689 subgrids that lead to a solution. Using my "cross hand" analysis, I need to generate and test about 50 * 50 * (9/70) * 64 B5689 subgrids, about 21,000, for each B2347 combination. In total I generate and test about 250,000,000 * 21,000, around 5.23e12, grids. This is a very large number, but well within reach of my 2 GHz Pentium 4. With careful design of the data structures and hand coding in assembler, I get good data cache performance and a 5-instruction inner loop. On average it takes only about 7.6 clock ticks to generate and test each of the 5.23e21 grids. At 2GHz this is around 5.5 hours.

I have some ideas for reducing the 250,000,000 combinations of B2347 to a few thousand equivalence classes (but not the 2802 method), which would speed things up by a huge factor. But I felt that any added complexity would increase the odds of making an algorithmic or programming mistake, so the 5.5 hours seemed well worth the wait. Now that I know what the right answer is, I can explore more efficient methods without peril, and I hope to do so.

--Bill

[dukuso]

>Thanks for the explanation of the 2802 method.
>This is NOT the method I used, so I think my method represents
>a truly independent confirmation (both an independent program
>and an independent method).
>
>I do not handle permuting the digits 1..9 (what I call "renaming
>the symbols") as an equivalence relation on B2347.
>Instead I just pick one particular permutation of the symbols
>for B1, and let B2347 follow from that.
>
>Your x(1),x(2),x(3) is what I call a column triplet of B2; x(7),
>x(8),x(9) is a row triplet of B4; and likewise for the other x's.
>For the permutations of the minicolumns of B2 and B3, or the
>minirows of B4 and B7, I pick one permutation of the six using
>my S function to make a row/column class.
>
>The 1680^4 combinations of B2347 are reduced to 280^4 by using
>my classes instead of triplets. B1 constrains this to 252^4.
>Using my "straight hand" analysis further reduces this to about
>(252 * 176.6)^2 combinations. Symmetries resulting from swapping
>B2/B3, B4/B7, or B23/B47 (equivalent to the second line of your
>11 permutations) further reduces this to about (252 * 176.6)^2 / 7.95,
>just under 250,000,000 combinarions. I analyze every one of these;
>there is no further reduction in equivalence classes.
>It's a lot of work, but the bookkeeping is managable.
>
>For each of the 250,000,000 combinations of B2347, I need to count
>the number of B5689 subgrids that lead to a solution.

that's 3e8 calculations with 3e3 solutions in average.
I can't see how to manage this.
OK, you use some tricks for the B5689, but when you just
count them for -say- a million B2347s chosen randomly out of
these 2.5e8 how many different counts do you get ?
Should be 1035.

>Using my "cross hand" analysis, I need to generate and test
>about 50 * 50 * (9/70) * 64 B5689 subgrids, about 21,000,
>for each B2347 combination. In total I generate and test
>about 250,000,000 * 21,000, around 5.23e12, grids.
>This is a very large number, but well within reach of my
>2 GHz Pentium 4. With careful design of the data structures
>and hand coding in assembler, I get good data cache performance
>and a 5-instruction inner loop. On average it takes only about
>7.6 clock ticks to generate and test each of the 5.23e21 grids.
>At 2GHz this is around 5.5 hours.
>
>I have some ideas for reducing the 250,000,000 combinations
>of B2347 to a few thousand equivalence classes (but not the
>2802 method),

why not ? Sounds to me as if it were essentially the same then.

>which would speed things up by a huge factor.
>But I felt that any added complexity would increase the odds
>of making an algorithmic or programming mistake, so the 5.5 hours
>seemed well worth the wait. Now that I know what the right answer is,
>I can explore more efficient methods without peril, and I hope to do so.

even when these methods are more perilous for you, the later
result and description will hopefully be easier to explain
and more satisfying.

[Ocean]

sudokugrids:1e22 from 1e10 classes
sudokus:1e47 from 1e35 classes (1-solution)
minimal sudokus:1e37 from 1e25 classes (no superfluous clues)

Thank you for the numbers!

It immediately surprised me that the number of sudokus "equals" my rough upper bounds, but the explanation is simple: the vast majority of sudokus have 30-50 clues, and in this range the fraction of puzzles with more than one solution is very small. For small number of clues, the opposite is true (the fraction with exactly one solution is small).

I don't quite see how you get the numbers for minimal sudokus, but they seem "reasonable". Good to know there are plenty enough ...

[PatmaxDaddy]

that's 3e8 calculations with 3e3 solutions in average.
I can't see how to manage this.

I'm a better programmer than I am a mathematician. I've been writing code for 34 years.

OK, you use some tricks for the B5689, but when you just count them for -say- a million B2347s chosen randomly out of
these 2.5e8 how many different counts do you get ?
Should be 1035.

I actually did this for all of the 2.5e8 B2347s, due to the same curiosity that you have. Just one more 5.5 hour run, easy to do. Got exactly 1059 different counts. I have high confidence in this number.

why not ? Sounds to me as if it were essentially the same then.

I think the difference is in how we define the equivalence classes. 2802 includes the 9! symbol renaming in the classes for B2347, with B1 allowed to take on any consistent state. My version does the 9! by fixing B1, and does not include it in B2347. But I do wonder whether if I look hard enough I will find the 2802 lurking in my version. I am definitely looking for it, and for other equivalences I can exploit to reduce the 2.5e8 to a few thousand.

even when these methods are more perilous for you, the later result and description will hopefully be easier to explain
and more satisfying.

More satisfying certainly, but I don't think easier to explain. Exploiting more symmerties should make things more complex, not simpler. Pure brute force, for example, would be trivial to explain but would take 1e20 times longer than the universe has been around to run. Getting it within range of our machines is what makes it hard.

As another example, I still don't really understand the 2802 method. I understood the explanation you wrote, but you left out a lot of details. I think to truly understand 2802 would be an investment of time, and I imagine you had to be rather clever to come up with it.

[coloin]

I persuaded G to to the B12347 calc.

there are essentially 2802 different B2B3B4B7 sudokugrids
with 1035 different nonzero solution-counts for the remaining
6*6 square plus 3*3 square of blocks B5B6B8B9 and B1.
Zero solutions only occur, when block1 can't be filled.
Otherwise maximum is:6280 solutions,minimum is 1960.

When OTOH you fill a 6*6 square then there are typically
~300000 solutions for the rest.
A file with 2802 representatives is uploaded to
http://magictour.free.fr/b12347.p

essentially different means, that these 2802 cannot be transfered into
one another by our 9!*6^8*2 sudoku-transformations
nor by permuting the 3 entries in some minirows or minicolumns.


Guenter.



and here is the first sudoku with only 2 clues in a 6*6 square
which I found in Nr.39 of the 2802:


Code:

...169347
...248159
...357268
2145.....
357......
869......
135......
728......
946.8....

I hope this helps.It is on page 22.

It was done in an effort to pick a tight grid - to get a minimal clue puzzle.
It didnt work - even the grids with a 1960 solutions didnt reveal any joy.

...249183
...367459
...158726
213......
745......
869......
971......
582......
436......

with 1960 solutions. It also has only 199296 solutions when you solve the
complement 6*6.

G and I didnt think it was worth repeating the enumeratiuon of N[Bertram]

The 1035/1059 issue will be resolved !

I had thought at the time that I got a grid with more solutions than 6280 - but this is the canonical grid - but I accepted G's word at the time.

I hope this explains it a bit more.
C

[dukuso]

I updated the post:
http://forum.enjoysudoku.com/viewtopic.php?p=12563#p12563

some more classes were found, it's 2865, not 2802.
This should be correct now, since I got N(Bertram)
when summing the values. 1059 is also confirmed.
One class which I had missed has 11664 solutions for the B5689 -
square (!) and 165888 for B12347 :

Code: Select all

...148367
...269158
...357249
321......
645......
879......
213......
456......
987......


looks like mc (most canonical)

and here is the new recordholder with only 1152 solutions:
(complement:313344solutions)

Code: Select all


...159268
...368147
...247359
124......
387......
965......
241......
738......
659......



[PatmaxDaddy]

Guenter & Coloin,

I can confirm the 1152 and 11664 solution counts. They are in my list of 1059.

Thanks for the additional explanation on the method. I wonder if I can remember any of the group theory I learned in college.

--Bill