How many Sudoku games?
Monday, July 21st, 2008A quick way to estimate the number of sudoku solutions:
First, defining terminology:
A sudoku grid is a 9×9 grid broken up into 9 3×3 grids. Let A, B, C, D, E, F, G, H, J be 3×3 grids then
A B C
D E F
G H J
is a sudoku board. Letter each grid the same using lower case letters. Thus Aa is the top left corner of the sudoku board and Jj is the bottom right corner.
Now, some assumptions that reduce the number of solutions to be calculated:
- If A, B, C, D, G are known, there are 4 solutions since there are 4 unfilled grids.
- Assume that the top row begins 1, 2, 3, 4 and that within a grid, the entries of the top row ascend in value.
- Assume that grid A is filled 1…9 in order moving left to right, top to bottom.
As it turns out, this underestimates the real number by less than 4% (because the first assumption isn’t true). Here’s the calculation:
Number of ways to choose grid B given the above assumptions:
- Choose 4, 5, 6 for Ba, Bb, Bc. This forces the rest of the rows of grids B and C.
- Choose 4 for Ba and any other legal choices for Bb and Bc. This leads to 3 distinct ways of filling the rows of grids B and C. There are 9 such choices (5 choose 2 - 1), so this leads to 27 row possibilities.
3 * 9 = 27 + 1 = 28
Now, the top three rows have been partitioned. Permitting permutations of the second and third row of grids B and C gives 6 * 6 * 6 * 6 = 1296 orderings for each of the 28 partitionings. This gives 28 * 1296 = 36,288 different possibilities for grids A, B, C. Taking advantage of the symmetry of the sudoku board, there are also 36,288 possibilities for A, B, G. Crossing the two, gives 36288 * 36288 = 1,316,818,944 possibilities for the corner grids. It was assumed that each of these would lead to four solutions:
1,316,818,944 * 4 = 5,267,275,776 solutions.
Ed Russel and Frazer Jarvis worked out the actual number as 5,472,730,538. You can see how here.