A partial analysis?

kw: analysis, puzzles

I have played Sudoku for years without really considering just how many such puzzles can be formed. I did a quick search and found quite a variety of "answers" to the question, "how many Sudoku puzzles?". They range from a few trillion to about 10⁵⁰, all confidently asserted. So here is my 2¢ worth. I don't have all the analytical tools to do a complete statistical analysis, but I'll do what I can.

There are three constraints:

1. All the digits from 1-9 must appear in each row. This implies that no digit can be repeated in any row.
2. The same goes for any column.
3. All the digits from 1-9 must appear in each of nine blocks formed by breaking up the 9x9 grid into a tic-tac-toe board. This also implies that no digit may be repeated in a block.

The following block of digits is the trivial Sudoku solution:

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Now let us constrain the solution. First, there are 9! ways, or 362,880, to make a single row of nine digits. If we were totally free to make the rows, without constraints 2 and 3, the total number of arrangements would be (9!)⁹ or 1.09x10⁵⁰.

We are not so totally free, however. Given any particular top row, the second row is constrained, so that the number of possibilities is 8x7x6x5x4x3x2x1x1 = 8!. Looking at the other end of the problem, we find that once eight rows are completed, the ninth has a unique solution, so the number of its possibilities is 1 or 1!. If there are two rows left, they can come in either order, but are otherwise completely constrained, so the number of possibilities for the seventh row is 2 or 2!. Thus I infer that the number of row-column solutions, not constrained by the blocks, is 9!x8!x7!...1! = 1.84x10²¹.

The block constraint will further limit the total number. My stab at it is to reason thus: The solution given above is a rearrangement of:

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

This is a row-column solution, but not a block solution. This particular collection of rows can be rearranged 9! ways, but not all of them are block solutions. The true solution given previously can be considered as three sets of three rows. Each such set can be rearranged 3! or 6 ways, and the three sets can be rearranged 3! or 6 ways, giving (3!)⁴ ways in total, or 1,296. Thus we take the number of row-column solutions, divide by 9! and multiply by 1,296, which yields:

6.55x10¹⁸

I do believe that is the total number of Sudoku puzzles. If I have left something out, I am sure I will hear from someone…