dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

How Many

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion
View previous topic :: View next topic  
Author Message
Guest
Guest





PostPosted: Fri Aug 05, 2005 10:44 am    Post subject: How Many Reply with quote

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. Question
Back to top
segmental
Guest





PostPosted: Wed Sep 14, 2005 2:47 pm    Post subject: Reply with quote

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 switching 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.
Back to top
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Wed Sep 14, 2005 8:45 pm    Post subject: Number of different Sudoku patterns Reply with quote

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
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group