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!)

^{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

^{4}=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!)

^{9}/(2^4x4), which is 1.705x10

^{48}. So yes, much bigger than something on the order of 10

^{12}.

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 solutionsSo somehow I don't think I would have figured it out tonight on my piece of paper, and neither do I think that (9!)

^{3}is a helpful number in coming to this conclusion.

By the way, that number is 6.67x10

^{18}, which is more than Suzie's number (as she said) and less than mine (as I said).

## 1 comment:

Want to have a go at working out how many Samurai Sudoku puzzles there are?

Post a Comment