Sudoku

Someone found my blog searching Google blog search for combinatorics, so I looked at the results and found someone discussing the number of sudoku puzzles. It doesn't appear on the results anymore, but what I saw was this post which a female math teacher named Suzie apparently wrote yesterday, which said, "Without figuring out the exact number of Sudoku puzzles, I know for sure that there are more than (9!)^3 of them. Rounding down, that’s over 4.778 x 10^16 puzzles." She goes on to calculate how long it would take you to do all of them if you did a hundred per second and compares this to the length of time humans have existed.

This all seems like a bit of a daft misadventure to me, because although I am not sure how she came up with her number, I'm sure that the real number is indeed larger than that -- much, much larger than that. One thing you will never be able to say about my writing is that you don't know how I came up with my answer, so now I'm going to tell you.

Sudoku is a 3x3 grid of squares wherein each square contains a smaller 3x3 grid of squares, each of which contains each number from 1 through 9 exactly once. In each of the nine large squares, there are nine small squares in which the number of possible arrangements is 9! (9x8x...x2x1. So for each of nine big squares, there are 9! ways to arrange the numbers in the small squares, i.e. (9!)⁹.

Of course we have to factor in all of the symmetries; there are horizontal, vertical, and two diagonal directions of reflection, so we divide by 2⁴=16. Furthermore you can rotate four ways, so we divide by four. These are all essentially the same sudoku puzzle, except rotated or reflected, so we'll eliminate the copies.

Now we have (9!)⁹/(2^4x4), which is 1.705x10⁴⁸. So yes, much bigger than something on the order of 10¹².

Is this reasoning sound? Am I missing something?

Yes, of course I'm missing something. As stated, I'm right. But the crucial thing about sudoku is that each row and column in the global grid also has to contain the numbers 1 through 9 each exactly once. So this eliminates a lot -- really, a lot -- of the possibilities.

In fact, the problem is significantly more complicated than at first meets the eye. Wikipedia has this to say about it:

the number of valid Sudoku solution grids for the standard 9x9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960. ... This number is equal to 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions

So somehow I don't think I would have figured it out tonight on my piece of paper, and neither do I think that (9!)³ is a helpful number in coming to this conclusion.

By the way, that number is 6.67x10¹⁸, which is more than Suzie's number (as she said) and less than mine (as I said).