The New Sudoku Players' Forum

[Bert Rackett]

Dear forum:

I am a recently retired engineer, and I've been using some of my new-found idle time writing a sudoku solving program. It should be straightforward, and will allow me to find further methods for manual solving.

I've read many of the #puzzles entries. I've probably missed it in my haste, but I found little about the many obvious symmetries in sudoku.

In any puzzle a 1 --> 8 constant may be added, mod 9, to every cell, resulting in perfectly valid unique versions of the puzzle. In the postings I see every cell being varied. Why not count the puzzles with (row 0 col 0) = 1, with perfect confidence that the total number will be precisely nine times that value?

Taking it one step further, fix the value of R0C2 = 1. May we not assume that the total number will be 9 * 8 = 72 times the total we calculate?

My greatest strength as an engineer was the highly successful use of my intuition in developing complex algorithms. And of course some of my worst mistakes resulted from relying too much on that same intuition. So, let me be the hero or the goat...

How far will symmetry allow us to go? If we arbitrarily set the upper left cells of every 3x3 block to the numbers 1 --> 9
R0C0 = 1 R0C3 = 2 R0C6 = 3
R3C0 = 4 R3C3 = 5 R3C6 = 6
R6C0 = 7 R6C3 = 8 R6C6 = 9
will the number of valid sudoku puzzles be precisely 9 * 9! = 3,265,920 times the number of valid puzzles with the nine given cell values? If my suppositions are correct this should save quite a few PC minutes.

One more suggestion. Every valid sudoku puzzle becomes another valid puzzle if it is flipped horizontally or vertically. I don't have the programming or mathematical expertise of many of the other participants, but it should be feasible to quickly identify such reflections, reducing the analysis by another factor of precisely four.

[frazer]

To Bert: since there are 330 posts in this thread, you can be excused for missing much of the earlier discussion in your haste! In fact, we have calculated the number of valid sudoku grids already. We do simplify the calculation by assuming that the top left 3x3 box is in fixed form (reducing the calculation by 9! -- not 9*9!) as you suggest, and then go on to apply more symmetries (in fact, a lot more than you list) in the calculation. See the 138th post in the thread for the final answer; the posts around there give further details. There is also a short article at http://www.shef.ac.uk/~pm1afj/sudoku/sudoku.pdf with fairly complete details (although part of it will soon be rewritten to make it more readable!). The number of "essentially different" grids is also known (also on this thread); I hope that another short article will possibly soon be available too. Good luck with your program!

[Moschopulus]

This thread is already too long so I hesitate to post here - perhaps it should be allowed to die.

Anyway, someone estimated how many puzzles a given (completed) grid has. I can't find the post

My question is, could a grid have just one puzzle with a particular number of clues? For example, could a grid have just one puzzle with 17 clues ? (I mean up to symmetries of the grid - obviously you can perform a symmetry of the grid to get another 17er)

Or is it the case that if a grid has one 17 clue puzzle, then it has lots.

[dukuso]

I assume that a grid usually has only one 17-suduko
(if it has at least one)

[coloin]

Someone asked for their money back a while back because they thought there were not enough solutions in the sudoku progrm they had purchased. Note it is a program which generates symetrical puzzles.

I think the words of Animator ring true.

I made a casual guess at the number of puzzles which is probably inaccurate !

http://forum.enjoysudoku.com/viewtopic.php?t=533


On the topic of the 17s - Experience must have shown Guenter and Gfroyle that eventually if you try hard enough there is a 17 in every/many sudoku grids - is this correct ? [Canonical grid excepted]

But no 16...........that is the other forum

[dukuso]

Gordon has 7611 17-clue sudokus from 7543 classes.
So I estimate there are about 500000 sudoku-grid-classes
which admit a 17-sudoku. (out of 5e9)
A 1:10000 chance that a random grid has a 17.

[frazer]

As one partly responsible for the length of this thread, I agree that its length begins to make it very difficult to navigate...!

But anyway, I also made a guess at the number of puzzles. Based on the observation that a random subset of 23 squares of the 81 is enough information-theoretically to define the solution uniquely (although it is easy to come up with plenty of examples with 23 squares with more solutions than just the given one), I'd guess that many subsets of the 81 squares actually define the grid uniquely. Subsets with fewer than 23 elements aren't likely to work, and many of those with 23 or more won't work either, but it seems to me that subsets that don't work could even be in a minority in general. It seems reasonable to me to guess that the number of puzzles giving a specified sudoku grid as solution is is about half (and surely within an order of magnitude!) of all the 2^81 possible subsets. (Of course, this is only my gut feeling, for which I have no evidence whatsoever.) So this would suggest about 6.67e21 * 2^80, between 1e45 and 1e46. Symmetric puzzles would be dealt with similarly, except now there are just 2^41 symmetrical subsets, and 6.67e21*2^40 is a little under 1e34.

Update on my previous post: I've rewritten the article, but Bertram seems to be away at the moment -- I'll post it when Bertram says it's OK.

I'm also writing up the calculation with Ed on the number of essentially different grids - see http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html - these results are still not independently verified, so if you feel that you'd like to help check them, feel free!

[JDLawlis]

Congratulations on determining the number of combinations that exist on a blank 9x9 grid! I apologize if I missed this already, but I would be interested in seeing the maximum number of combinations if 1,2,3 etc. random boxes are filled in (up until 16 or 17, whatever the minimum number for a unique solution is). Is this problem solvable?

Jeff

[Moschopulus]

- these results are still not independently verified, so if you feel that you'd like to help check them, feel free!

I'd like to check it but I'm a terrible programmer. Maybe I could use magma or something. Probably better to use a different program anyway. Ideally I'd like to have a different method. I'm thinking about one.


I don't suppose you have a file of the 5e10 inequivalent grids anywhere.....

[Karyobin]

I'm not going to offer anything to this thread, coz I'll just be silly.

[dukuso]

Congratulations on determining the number of combinations that exist on a blank 9x9 grid! I apologize if I missed this already, but I would be interested in seeing the maximum number of combinations if 1,2,3 etc. random boxes are filled in (up until 16 or 17, whatever the minimum number for a unique solution is). Is this problem solvable?

Jeff

boxes = cells ?
the maximum is probably reached, when you group the clues together
so they "neutralize" their own posed constraints.
For a 3*3 block filled with 9 cells it should be possible
to deduce the number of solutions ...I'm too lazy to think about it.
Then we could ask for 2 filled blocks. For maximum solutions
they should be adjacent. Just compute the number of
ways to extend them to a full chute of 3 blocks and multiply
by the known numbers how to extend to a full grid.
Maybe I'll try it later.

[coloin]

Gordon has 7611 17-clue sudokus from 7543 classes.
So I estimate there are about 500000 sudoku-grid-classes
which admit a 17-sudoku. (out of 5e9)
A 1:10000 chance that a random grid has a 17.

This would explain why its looking less likley that there is a 16.

If there is a 16 it will have 65 [81-16] inherent 17s in it - and we hanvt found one of those yet.


Can I ask what proportion of your random grids were 18s and higher ?

[Dusty Chalk]

Is there a way for me to print out this entire thread, so that I can read it at my leisure, and make sure the point I would like to make has not already been brought up?

[coloin]

I don't suppose you have a file of the 5e10 inequivalent grids anywhere.....

I would quite like this too........but in the mean time.................which of these grid patterns effectivly reduces the solutions down approaching 5E10 [5,472,730,538 ?] the best ? Bear in mind......

Red Ed solved your question within the last month -- it's quite a tricky calculation, and the answer turns out to be 5,472,730,538. Your guess that it is the total number of puzzles divided by the number of variations (9!*6^8*2) is pretty close (that would give 5,472,447,994.271...); the discrepancy comes about because there are some transformations which in general take a valid solution grid to a different one, but which take some special grids to themselves.

123 xxx xxx
456 1xx xxx
789 xxx 1xx

x1x xxx xxx
xxx x1x xxx
xxx xxx x1x

xx1 xxx xxx
xxx xx1 xxx
xxx xxx xx1 ......= 9!* 3^6*2^6 ??

123 456 789
4xx xxx xxx
xxx xxx x4x

x4x xxx xxx
xxx x4x xxx
xxx xxx 4xx

xx4 xxx xxx
xxx xx4 xxx
xxx xxx xx4 ........= 9! * ?

Can anyone improve on these

[dukuso]

we can partition the ~5e9 classes into
about ~1.5e6 classes, when we consider grids
equivalent which differ only by permutations inside the minicolumns,
and if we don't allow transposition (mirroring at a diagonal).


For each representative from these ~1.5mio classes you could quickly
calculate all representatives from the ~5e9 classes - just by permuting
minicolumns and checking the transpose.
So it's possible to write a program which prints ~5e9 grids, one
from each class in reasonable time.
Storing them could be a small problem, I can't generate files
larger than 4GB here.
Also ~5e9 grids take ~400Gbytes uncompressed. Walking through this
list takes some time, so it could be more practical to
generate them every time on the fly, when you need them.

Actually I don't yet have a file with these ~1.5e6 representatives,
just ~3.8e6, some of which are from the same classes.
When I generate their graphs to discover equivalences with Nauty,
this takes ~50GB...

edit: it seems to be much less than 1.5e6, maybe 300000
are sufficient to generate one representative from all 5e9
RedEd-classes by permuting inside minicolumns.