How many Sudoku puzzles are there?
Some thoughts on how many possible Sudoku puzzles there actually are.
Invent a new Helper puzzle Hardest Puzzles Pretty Puzzles Books about Sudoku On the web site the history page http://www.sudokudragon.com/sudoku.htm gives the total number of different Sudoku puzzles as 6,670,903,752,021,072,936,96.
Can someone with better mathematics than me explain how this is calculated?
I thought of this a bit and wondered if the number takes into account all symmetric possibilities. Any puzzle has at least three simple variations - just by rotating the puzzle through 90, 180 and 270 degrees.
Any comments ? Click here to contributeIt may be that this is just a count of the total number of puzzles that obey the Sudoku rules and does not account for the number of symmetric variants of the same puzzle. Also I wonder if the figure takes account of the symbol replacements. In any puzzle you can always swap all occurrences of one number by another, try this for yourself, replace all '1's with '2's and all the '2's with '1's it is always a valid Sudoku puzzle... but for te purpose of counting the number of possible games should they both be considered the same puzzle ??
Any comments ? Click here to contributeI've seen the 6,670,903,752,021,072,936,96 number of sudoku puzzles 'explained' in the following way.
First start with the 9! (factorial) the number of ways that 9 symbols can be permutated that is 362880. Now that is just one 'group' (row or column) so naievly you might expect 9! to the power 9 as that combines each possible permutation with each possible permuation for the remaining rows. However that does not account for the rules of Sudoku - lots of those possibilities are excluded. The permutation of the rows and columns restricts this to 72 ways 3! x 3! x 2! for the remaining six rows and columns. That gives 9! x 72 x 72. This leaves the remaining factor 128 x 27,704,267,971 which as far as I know was deduced by going through all the possibilities by computer. So we have 9! x 72 x 72 x 128 x 27,704,267,967 which should give the total number of unique sudoku puzzles.
So it does take account of swaps of rows and columns.
Any comments ? Click here to contributeI calculated the total unique solutions as 96845.
How I got there:
Start with a blank grid and put an X in Aa. 1 of 9.
Then put another X in Bd. 1 of 6.
Then put an X in Cg. 1 of 3.
So far for X, 9*6*3=162.
Now put an X in Db. There are already 3 places taken by Xs in the
upper third so it has 6 possible spots.
An X then in Ee. 4 choices here.
To finish the middle third put an X in Fh. One of only 2 possibilities.
So, for the middle third, 6*4*2.
Repeat this for the bottom third and the possibilities are 3*2*1.
For one number in a blank grid the total possibilities are: 9*6*3*6*4*2*3*2*1=46656
I proceeded to fill in the rest of the grid and counted the possiblie placements of succesive letters (yes, I used letters to avoid confusion.)
My totals are: A (X, as listed above)46656; B 23040; C 1260; D 17280; E 6400; F 384; G 1728; H 96; I 1.
This yeids a puny total of 96845 unique solutions for a 9x9 grid.
I am not a trained mathematician, and I smoke a lot of crack, so I could be wrong.
While filling my grid I noticed that the placement of letters could result in different, lower possibilities. I chose the solution that yielded the most possibilities.
Any comments ? Click here to contributeHowdy. While developing documentation for my product, SudoKoach, I had it generate well over half a million puzzles (I'm still generating them). I only count puzzles that have a unique solution.
My idea was to use a probability argument to estimate the total number of Sudoku solutions: 'How large must the solution space be in order to get X% duplications when generating 500,000 puzzles randomly?'. The only problem I've encountered so far in this endeavor is that I've not gotten ANY duplicates at all!
This is an existence proof of the falsity of the claim that there are only 96,845 distinct puzzles.
Granted, I'm not filtering out variations. You can reasonably claim that a puzzle it no different from what you'd get if you took the same puzzle and:
* rotated it 90 degrees
* rotated it 180 degrees
* rotated it 270 degrees
* mirrored it horizontally
* mirrored it vertically
* cut it in thirds vertically and permuted the columns-of-3
* cut it in thirds horizontally and permuted the rows-of-3
* performed any combination of the above on a puzzle
Nevertheless, the fact that I've gotten NO duplicates in a set of 622,381 randomly generated puzzles suggests that the total solution space is way larger than the 96,845 suggested by the previous contributor.
- Ken
PS: With the solving strategies I've implemented so far, my program can solve 99.5% of all the Sudoku puzzles I've generated using logic alone--no guesswork. My theorem is that ALL Sudoku puzzles can be solved by logic alone, but I can't prove that yet: there are more strategies to implement!
Any comments ? Click here to contributeAndrew's reasoning isn't bad, except after he's figured frequencies for each pattern of symbols he should be multiplying them rather than adding.
So Andrew is really saying that there are 46654 x 23040 x 1260 x 17280 x 6400 x 384 x 1728 x 96 x 1 patterns.
I get 9,541,802,647,869,271,415,193,600,000 or about 1.5 million times more than the claim of about 6.6 x 10^21!
Not bad for a crack-head. He's probably just counting a few duplicates.
Any comments ? Click here to contributeIt can be observed that any two rows can be switched without breaking a sudoku, as long as the rows are within the same block. So there are 6 combinations for the top three rows, six for the next three, and six combinations for the bottom three rows. Now the block-rows themselves can also be re-arranged, move the middle three-rows to the top and bump the top three rows down. Obviously, you can also do the same for the columns. And of course there is also symbol substituion.
You could also rotate all of those 90 degrees. Rotations of 180 and 270 can be duplicated by as row-swapping and column swapping combinations.
so,
6x6x6x6 combinations of row swappings
x6x6x6x6 combinations of column swappings
x9x8x7x6x5x4x3x2x1 combinations of symbol swappings
x2 for a 90 degree rotation
= 1,218,998,108,160 combinations per 'significant' sudoku.
There are actually only about 5 billion 'significant' sudokus.
Any comments ? Click here to contributeAll of the solutions on here are wrong, but SudokuPaul is closest. It helps to have a background in cryptology. This is a traditional, but trivial p vrs. np situation. There are indeed 6 to the eight power of combinations for valid rows and columns. There are indeed 9 pictorial combinations of symbol swapping. But, there is no deed for rotation. This can be seem by taking a valid Sudoku and rotating clockwise. Top row now becomes the far right column. Using the far right column to derive a symbol combination map. The entire new Sudoku can be correctly filled in by using the substitution. The final combinations are 6 to the power of 8 times 9 factorial. The final step is to subtract 1 because the row and column swaps share an initial starting configurations.
Any comments ? Click here to contributeAs an aside to this discussion I have a hypothesis I don't think is mathematically solvable. I propose that if any single row or column is filled in a blank Sudoku square in any position there is one and only one possible solution. The brute force approach, as used in cryptography, is to generate all possible puzzles and then search for valid puzzles that contain that one row or column in that exact position. There must be a more elegant approach. Any thoughts?
Any comments ? Click here to contributeI do think you need to ignore duplicates, that is Sudoku puzzles that are simply a re-arrangement of another puzzle. I mean if you have just swapped one symbol for another that should not count as a new one. Also if another puzzle is just a rotation through 90º or 180º that should not count either.
It suggests there is a canonical form for a puzzle that all these variants would be just examples of. How many Sudoko puzzles should be just the total number of possible canonical forms.
Any comments ? Click here to contributeUsing the number of six and a half thousand billion billion possible Sudokus I produced some amazing facts. If you printed all of them on 6x6inch newsprint paper and stacked them up, not end to end but flat on top of each other they would reach pluto which is 3.7 billion miles away, a staggering 55 thousand times.
Put another way you could covered the entire USA in them half a mile deep!!
If you layed them around the equator over land and sea around the world you could build a wall out of them as high as a comercial jet might fly (35000 feet). Oh yes, and the wall would be 10 miles thick!!!!!!!!!!!
Don't even bother trying though as there are not enough trees on the planet to print them all on anyway.
Any comments ? Click here to contributeThere are an awful lot of puzzles.
To clarify.
The first post is sort of correct.
This is the total number of SOLUTION GRIDS [6x10^21]
This can be almost reduced by the clue substitution [9!] and a lot of row-swapping [6^8] and a diagonal [2] to 5x10^9.
Each one of those different solution grids has at least approx 10^14 different [minimal] puzzles.
So roughly there are 5x10^23 different minimal puzzles
This is 50000 billion billion.
Which is ten times larger than RampageGuys number - but the overallmessage is the same - we wont run out of puzzles any time soon !
C
Any comments ? Click here to contributeCopyright © 2005-2024 Sudoku Dragon