dailysudoku.com

[Guest]

Exactly how many solutions to Sudoku puzzles are there.

I note that firstly there are only 504 combinations of 3 digits that can be used. Once one of these is used in the first column, first row, there are only 120 remaining possibilities for the first row, second column. After that, there are only six remaining combinations that can be used in the final column of three digits.

Before I blow my mind on this one, I need some help.

[segmental]

I'm guessing from the lack of discussion on this thread that the exact answer is probably somewhat difficult to come by. I sure hope so, 'cause I've put a fair amount of thought into it and haven't managed to get an exact number, yet.

This is what I've come up with, so far:

1. The top left block can be filled in any of 9! ways -- that's 362,880.

2. With the top left filled, the top center block can be filled in 12,096 ways. Very careful analysis (which I don't have the energy to type in, right now) shows that there are 56 ways to choose which numbers go in which row of the top center block, once the top left block is established. Each row of the top center can then be ordered in any of 3! (6) ways, giving a total count of 56*6*6*6 = 12,096 possibilities.

3. With the top left and top center blocks established, the top right block can be filled in 216 ways. By this time, there's only one way to fit all of the digits into the three rows of the top right block, but there are still 3! ways to order each of the rows, for 6*6*6=216 possibilities.

4. The left center block can be filled in 12,096 ways, using the exact same analysis applied to the top center block (item 2), essentially interchanging "row" and "column."

5. The bottom left block can be filled in 216 ways. Use the analysis from item 3, again xx the horizontal and the vertical.

To this point, we've determined that there are 362,880*12,096*216*12,096*216 = 2,477,160,187,538,964,480 (assuming my calculator is giving me all 19 digits of that product correctly) ways to fill these five of the nine blocks. In other notations, that's 2.477*10^18 or about 2 1/2 quintillion.

That's the end of the easy part, because now we have to look at blocks that are restricted in two directions. From this point, all I can offer at this time are upper bounds.

6. With the top center and left center blocks filled, there are at most 448 ways to fill the center block. Going from the left center to the center, we again have 56 ways to separate the center block's digits into rows. For each of those rows, it turns out that there are at most 2 ways to order its digits without violating the basic Sudoku conditions. That gives us 56*2*2*2 = 448 possibilities, but again that's at most, because some of those won't actually be valid. I haven't yet managed to wrap my head around how to determine how many will be valid, but it's not the same for all combinations of left center and top center blocks.

7. With the left center, center, and top right blocks filled, there are at most 56 ways to fill the right center block. In this case, there are 56 ways to separate the right center block's digits into columns. With both the left center and center blocks full, there is at most a single way to order those columns, for a total of at most 56 ways to fill the block.

8. Similarly, with the top center, center, and bottom left blocks filled, there are at most 56 ways to fill the bottom center block.

9. With everything but the bottom right block filled, there is now at most a single way to fill the bottom right block.

OK, so for each of the possibilities for filling the upper and leftmost 5 blocks, we find that there are at most 448*56*56*1 = 1,404,928 ways to fill the remaining 4 blocks. I strongly suspect that the actual number will always be less than that, but certainly cannot prove anything at present.

The two sections of this analysis, then, tell us that there are at most 362,880*12,096*216*12,096*216*448*56*56*1 = 3,480,231,707,958,742,288,957,440 possible Sudoku solutions. In other notations, that's about 3.480*10^24, or about 3 1/2 heptillion.

I'm still trying to figure out an exact number, but I'm not the best probability/statistician in the world. Obviously, the numbers involved are too large to admit a brute-force solution, but I'm still working on ways to prune things down to a point where I can, at the very least, substitute a good statistical estimate for the upper bound on the last 4 blocks.

Oy.

[David Bryant]

According to the Wikipedia article there are exactly 6,670,903,752,021,072,936,960 distinct possibilities for the 9x9 Sudoku grid.

I forget exactly where I ran across it, but the discussion between Felgenhauer and Jarvis is still posted on the web somewhere... try running a Google search on "Felgenhauer" if you're interested in the details. dcb