The Number of Possible Sudoku PuzzlesDate: 03/04/2006 at 14:14:55 From: Neville Subject: The Number of Possible Sudoku Puzzles As you know, Sudoku is a current craze, although its best days may have already passed. I assume you are familiar with the game. I have been thinking about how many possible variations there are. By my reckoning the number is factorial nine times six to the sixth power, i.e., 16,930,529,280. My decision to write to you was triggered by a recent newspaper article on Benjamin Franklin’s Squares giving the number of possible solutions to Franklin's puzzle as about one million plus. The article also states that there are about 6 sextillion Sudoku solutions, where a sextillion is either 10 to the 21(American) or 10 to the 36 (British). Either way the number is much larger than mine. My reasoning goes as follows: 1) Given a properly completed solution another can be generated by a one-to-one mapping of the numbers 1 to 9, e.g., Original: 1 2 3 4 5 6 7 8 9 Mapped: 2 8 7 3 9 1 4 6 5 2) There are 9! such mappings, producing a Basic Set [Defined Term] of 362,880 solutions. 3) Within each solution in the Basic Set it is possible to permute the rows and columns of each minor (3x3) square. For example, rows 1,2 and 3 can be permuted six ways, as can columns 1,2 and 3. Similarly, the other two sets of rows and the other two sets of columns can be commuted in the same way. These permutations can be combined in 6 to the power 6, i.e., 46,656 ways. I believe, but cannot prove, that any such combination will not match any other such combination or any member of the Basic Set. 4) Hence I reckon there 362,880 x 46,656, i.e., 16,930,529,280 unique Sudoku puzzles. Neville Date: 03/05/2006 at 17:16:59 From: Doctor Vogler Subject: Re: The Number of Possible Sudoku Puzzles Hi Neville, Thanks for writing to Dr. Math. Let's look at your work: >1) Given a properly completed solution another can be generated by a >one-to-one mapping of the numbers 1 to 9, e.g., > >Original: 1 2 3 4 5 6 7 8 9 >Mapped: 2 8 7 3 9 1 4 6 5 > >2) There are 9! such mappings, producing a Basic Set [Defined Term] >of 362,880 solutions. You are right so far. >3) Within each solution in the Basic Set it is possible to permute >the rows and columns of each minor (3x3) square. For example, rows >1,2 and 3 can be permuted six ways, as can columns 1,2 and 3. >Similarly, the other two sets of rows and the other two sets of >columns can be commuted in the same way. Right again. >These permutations can be combined in 6 to the power 6, i.e., 46,656 >ways. I believe, but cannot prove, that any such combination will >not match any other such combination or any member of the Basic Set. I'm not so sure that I would believe that. In fact, I would bet that there are some solutions that could be permuted in one of those 6^6 ways to get the same now solution as if you permuted the numbers in one of those 9! ways. But I think that there are some solutions where this could not happen. >4) Hence I reckon there 362,880 x 46,656, i.e., 16,930,529,280 unique >Sudoku puzzles. And here is where you have underestimated the most. You are assuming that every Sudoku puzzle can be permuted in one of your 9!*6^6 ways into a single solution. In fact, there are many different solutions that cannot be permuted to one another. But it takes a lot of work to find even one solution in each collection of 9!*6^6. You can find some papers that have been written on this subject at http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf and http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html The first paper says that there are about 6.6709 * 10^21 valid Sudoku grids. Much of the work of computing this number was done on the computer, although the computer certainly can't list off that many grids; it would take forever. But it did a lot of the checking before complete determinations could be made. The second paper says that two grids are "essentially different" if they cannot be mapped to one another by one of the transformations you described, as well as four others (permuting the three blocks of three rows, permuting the three blocks of three columns, reflecting, and rotating). It finds that there are 5,472,730,538 essentially different Sudoku grids. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 03/05/2006 at 21:16:00 From: Neville Subject: Thank you (The Number of Possible Sudoku Puzzles) Dear Dr. Vogler, I wish to thank you very much for your prompt reply and constructive criticism of my attempt to count the number of possible Sudoku puzzles. You pointed out that I had neglected to consider the possibility of permuting the rows and columns in groups of three. Actually, this thought occured to me after I had submitted my question. The net effect would have been to inflate my estimate by a factor of 36 and apparently it was already too large. Thank you for the help. Sincerely, Neville P.S. By the way I am probably a little older than the average correspondent to Dr. Math, as I'll be 75 next month. I take these on to preserve gray matter. Thanks again! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/