## How many Sudoku puzzles are there?## Some thoughts on how many possible Sudoku puzzles there actually are.Other topics in this forumInvent 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 contribute Puzzle counts (re: How many puzzles) contributed by Rob PuzzleIt 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 contribute Puzzle Numbers (re: How many puzzles) contributed by AlexanderI'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 contribute total unique puzzles is 96845 (re: Puzzle Numbers) contributed by andrewI calculated the total unique solutions as 96845. How I got there: Start with a blank grid and put an Then put another Then put an So far for Now put an upper third so it has 6 possible spots. An X then in Ee. 4 choices here. To finish the middle third put an 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 ( 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 contribute 96,845 is WAY too small (re: total unique puzzles is 96845) contributed by Ken ReekHowdy. 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: 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 contribute Almost right (156) (re: total unique puzzles is 96845) contributed by SudokuPaulAndrew'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 contribute 1,218,998,108,160 different patterns for a significant solution (re: Almost right (156)) contributed by SudokuPaulIt 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 contribute Canonical Form (re: How many puzzles) contributed by AlexanderI 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 contribute Amazing Sudoku facts (re: How many puzzles) contributed by RampageGuyUsing 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 contribute re: How many puzzles (364) (re: Amazing Sudoku facts) contributed by coloinThere 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 contribute Copyright © 2005-2014 Sudoku Dragon |