Su-Doku's maths
Coloin's number
by coloin » Mon May 23, 2005 4:27 pm
ldel
Last edited by coloin on Wed Jul 27, 2005 5:39 am, edited 1 time in total.
- coloin
- Posts: 2493
- Joined: 05 May 2005
- Location: Devon
from where ?
by coloin » Mon May 23, 2005 4:51 pm
If x1 is 432
and x2 just happens to be 140
then x1*x2 = 140*432 = 9*8*7*6*5*4 which is neat
= 9!^4 / 6
= 2 890 020 218 795 458 560 000
If x1 is 432
and x2 just happens to be 280
then x1*x2 = 140*432 = 9*8*7*6*5*4*2 which is neat too
= 9!^4 / 3
= 5 780 040 437 590 917 120 000
If one of these is it - it is amazing.
and x2 just happens to be 140
then x1*x2 = 140*432 = 9*8*7*6*5*4 which is neat
= 9!^4 / 6
= 2 890 020 218 795 458 560 000
If x1 is 432
and x2 just happens to be 280
then x1*x2 = 140*432 = 9*8*7*6*5*4*2 which is neat too
= 9!^4 / 3
= 5 780 040 437 590 917 120 000
If one of these is it - it is amazing.
- coloin
- Posts: 2493
- Joined: 05 May 2005
- Location: Devon
Re: from where ?
by Animator » Mon May 23, 2005 5:08 pm
That's the main problem... you can do all the calculation you want but you have no real way to verify the number... as in, what do you compare it with? the result you get from another technique? that can be incorrect aswell... (even when it would result in the same number)
Also note that you have a small error in your explenation:
Obivously that has to be 280 * 432
Also note that you have a small error in your explenation:
coloin wrote:If x1 is 432
and x2 just happens to be 280
then x1*x2 = 140*432 ...
Obivously that has to be 280 * 432
- Animator
- Posts: 469
- Joined: 08 April 2005
by Guest » Mon May 23, 2005 6:28 pm
Bertram wrote:Thanks to a hint by afj I could speed up the process by another factor of 33, so you can expect an exact number later today or tomorrow.
Using some more ideas of afj I could reduce the time by another factor of 3.3. Had I applied them properly, this factor would've been close to 6, but the program I used for the reduction missed a few opportunities.
The result of the computation is
6,670,903,752,021,072,936,960 = 2^15 * 3^8 * 5*7 * 27,704,267,971 = 9! * 72^2 * 2^7 * 27,704,267,971
I wonder some of the factors of 2 can be explained by symmetries.
The calculation used about 6 hours of computation on two PCs.
- Guest
by Guest » Mon May 23, 2005 6:46 pm
Hi all-- Take a look at the following (partial) computation, and try to poke as many holes in it as you can
I've ruthlessly stolen some of the ideas in the first few pages, and redone the calculations so that they should be more correct: I found a few flaws in reasoning, some of which were emperically pointed out.
I'll start with the 5 block: 9! choices of numbers, to reordering
123
456
789
Then attack the 4 and 6 blocks:
We'll start (as before) with 4,5, and 6.
There are two main cases: 456 all in the same row, and 456 spread across the two rows.
Case 1) There are 2 choices of rows, and (3!)^2 reorderings within each row.
Ex.
546123___
___456___
___789645
Then the row-position of all the remaining numbers are fixed.
There are 3! ways to reorder the 4 remaining rows. Column doesn't matter here, because we can't duplicate numbers within boxes.
Total for case 1) 2*(3!)^6 = 2*6^6
Case 2) This one is more work.
There are 2 ways to choose which row (the upper or lower) will contain only one of 4,5,6 in box 4.
Then there are 3 ways to choose which of 4,5,6 is alone in that row.
There are 3 choices of position for that number in each of those 2 rows.
Similarly, there are 3! ways to position to the remaining two numbers in each of the 2 remaining rows.
Subtotal: 2*3*3^2*(3!)^2
Ex.
45_123_6_
___456___
6__7895_4
Now we have 3! ways to arrange 123 in the bottom row, and another 3! ways to arrange the 789 in the top row.
Ex.
457123968
___456___
631789524
The remaining 3 numbers in each block is determined. There are 3! ways to order the numbers in each of those blocks.
Total, Case 2) 2*3*3^2*(3!)^2 * (3!)^4 = 9 * 6^7
Total number of ways to arrange the 4 and 6 blocks:
9 * 6^7 + 2 * 6^6
We start to lose exactness if we try to say
"Similarly, there are 9 * 6^7 + 2 * 6^6 ways to arrange blocks 2 and 8" because there could (and will) be indirect constraints. If our goal, however, is to bound the solution, then we can make such a claim.
Total at this point: 9! (9 * 6^7 + 2 * 6^6)^2 = 3*10^17ish
Since we're committed to bounding at this point, let's look forward to the 1359 blocks.
There are 8 ways to place all the remaining 1's.
There are four allowable spots in each block, and there are only two configurations that work for each spot:
1# ## /// 1# ##
## 1# /// ## #1
#1 ## /// ## 1#
## #1 /// #1 ##
Thus the absolute maximum (though it should be much smaller) number of ways to fill the remaining blocks is 8^8. This bound can probably be reduced by a couple orders of magnitude with some cleverness. For instance, I want to say that once 6 numbers are filled in, the other 3 are determined, or else there is no solution: this would reduce this bound by a factor of 64.
= 4.16 * 10^24
I'd put money on the final answer being in the 10^20-10^21 range...
I've ruthlessly stolen some of the ideas in the first few pages, and redone the calculations so that they should be more correct: I found a few flaws in reasoning, some of which were emperically pointed out.
I'll start with the 5 block: 9! choices of numbers, to reordering
123
456
789
Then attack the 4 and 6 blocks:
We'll start (as before) with 4,5, and 6.
There are two main cases: 456 all in the same row, and 456 spread across the two rows.
Case 1) There are 2 choices of rows, and (3!)^2 reorderings within each row.
Ex.
546123___
___456___
___789645
Then the row-position of all the remaining numbers are fixed.
There are 3! ways to reorder the 4 remaining rows. Column doesn't matter here, because we can't duplicate numbers within boxes.
Total for case 1) 2*(3!)^6 = 2*6^6
Case 2) This one is more work.
There are 2 ways to choose which row (the upper or lower) will contain only one of 4,5,6 in box 4.
Then there are 3 ways to choose which of 4,5,6 is alone in that row.
There are 3 choices of position for that number in each of those 2 rows.
Similarly, there are 3! ways to position to the remaining two numbers in each of the 2 remaining rows.
Subtotal: 2*3*3^2*(3!)^2
Ex.
45_123_6_
___456___
6__7895_4
Now we have 3! ways to arrange 123 in the bottom row, and another 3! ways to arrange the 789 in the top row.
Ex.
457123968
___456___
631789524
The remaining 3 numbers in each block is determined. There are 3! ways to order the numbers in each of those blocks.
Total, Case 2) 2*3*3^2*(3!)^2 * (3!)^4 = 9 * 6^7
Total number of ways to arrange the 4 and 6 blocks:
9 * 6^7 + 2 * 6^6
We start to lose exactness if we try to say
"Similarly, there are 9 * 6^7 + 2 * 6^6 ways to arrange blocks 2 and 8" because there could (and will) be indirect constraints. If our goal, however, is to bound the solution, then we can make such a claim.
Total at this point: 9! (9 * 6^7 + 2 * 6^6)^2 = 3*10^17ish
Since we're committed to bounding at this point, let's look forward to the 1359 blocks.
There are 8 ways to place all the remaining 1's.
There are four allowable spots in each block, and there are only two configurations that work for each spot:
1# ## /// 1# ##
## 1# /// ## #1
#1 ## /// ## 1#
## #1 /// #1 ##
Thus the absolute maximum (though it should be much smaller) number of ways to fill the remaining blocks is 8^8. This bound can probably be reduced by a couple orders of magnitude with some cleverness. For instance, I want to say that once 6 numbers are filled in, the other 3 are determined, or else there is no solution: this would reduce this bound by a factor of 64.
= 4.16 * 10^24
I'd put money on the final answer being in the 10^20-10^21 range...
- Guest
- Posts: 312
- Joined: 25 November 2005
B6
by coloin » Mon May 23, 2005 10:55 pm
Anonymous wrote:The breakdown of filling B5: given B1,B2,B4
9!*6084 * 48 * 48 have 384 solutions
9!*12204 * 48 * 48 have 392 solutions
9!*36756 * 48 * 48 have 400 solutions
9!*224 * 48 * 48 have 432 solutions
9!*8236 * 48 * 48 have 448 solutions
Not sure if this might help in extending other solutions or not.
Tim.
Tim please could you do a form of this calculation for the filling of B6: given any B5 or B9. I have reason to think they are not the same.
I would be very grateful if any one else can show me how to do it.
Thankyou
- coloin
- Posts: 2493
- Joined: 05 May 2005
- Location: Devon
no answers
by coloin » Tue May 24, 2005 8:42 am
Yes Iam guessing !
Last edited by coloin on Tue May 24, 2005 9:27 am, edited 1 time in total.
- coloin
- Posts: 2493
- Joined: 05 May 2005
- Location: Devon
by Guest » Tue May 24, 2005 11:08 am
Perhaps it is worth adding a few words to Bertram's announcement of the computation of the exact value of the number of Sudokus. After all, how did a brute force search which originally looked like it would take years end up being completed in 6 hours?
It started with the computations I tried doing over the last couple of weeks. The strategy was to fill blocks 1-3, and then do a brute force search over the rest. After relabelling block 1, there are still 2612736 possibilities for blocks 2 and 3, as noted previously in these disucssions. But it is clear that it shouldn't be necessary to work out how many ways all of these can be completed to a full grid. For example, interchanging block 2 and block 3 will give a new configuration which can be filled in the same number of ways as the original. Similarly, permuting the three columns of block 2, and the three of block 3, also give "equivalent" configurations (in that they can be completed in the same number of ways). This reduction, by a factor of 72, takes us down to 36288 possibilities. In view of the fact that it was taking me nearly 36 hours to do a brute force search for each of these, this was still impractical, although (a) I knew my program was rubbish and could surely have been sped up enormously, (b) there was a chance I might be able to have some time on a very powerful computer, (c) the computations distribute well - so could have been spread around several people, and (d) I thought one should be able to reduce 36288 to a smaller number. I spent some time thinking of ways to cut this number down. In fact, one can improve immediately on it by observing that one can do more permutations than already mentioned. In fact, one can also permute the columns of block 1; one can permute all three of blocks 1-3; one can permute the three rows of the configuration - of course, block 1 will no longer be 123/456/789, but one can relabel again to put it back. In fact, this reduces 36288 to around 1000 [this is also partly due to Bertram], which was verging on practical, even with my program. Following a few calculations, it was clear that some equivalences were still being missed, and I realised the equivalences which I pointed out in an earlier reply to tinfoil. Unfortunately, I've been quite busy, so didn't get around to working out how much this helped. One can also group together some other grids like
123 456 789
456 789 123
789 123 456
and
123 789 456
456 123 789
789 456 123
not just because (in this example) one can permute the blocks, but because the numbers in each column in the two configurations are the same.
Following Bertram's announcement of a quick program to do the brute force calculations, I got in touch and sent him a file of these equivalences I'd been looking at. He implemented the algorithm astonishingly quickly, and programmed the equivalences, reducing the number to be checked to about 300. Since he could check each in less than 2 minutes (compared with my 36 hours!), the calculation was reduced to less than 12 hours! In fact, he has subsequently discovered further equivalences which seem to reduce the number as far as 71. (The results of the program show that there are at least 44 essentially different configurations, so maybe it is possible to reduce 71 further.) The whole calculation can now be done in a couple of hours!
Frazer
It started with the computations I tried doing over the last couple of weeks. The strategy was to fill blocks 1-3, and then do a brute force search over the rest. After relabelling block 1, there are still 2612736 possibilities for blocks 2 and 3, as noted previously in these disucssions. But it is clear that it shouldn't be necessary to work out how many ways all of these can be completed to a full grid. For example, interchanging block 2 and block 3 will give a new configuration which can be filled in the same number of ways as the original. Similarly, permuting the three columns of block 2, and the three of block 3, also give "equivalent" configurations (in that they can be completed in the same number of ways). This reduction, by a factor of 72, takes us down to 36288 possibilities. In view of the fact that it was taking me nearly 36 hours to do a brute force search for each of these, this was still impractical, although (a) I knew my program was rubbish and could surely have been sped up enormously, (b) there was a chance I might be able to have some time on a very powerful computer, (c) the computations distribute well - so could have been spread around several people, and (d) I thought one should be able to reduce 36288 to a smaller number. I spent some time thinking of ways to cut this number down. In fact, one can improve immediately on it by observing that one can do more permutations than already mentioned. In fact, one can also permute the columns of block 1; one can permute all three of blocks 1-3; one can permute the three rows of the configuration - of course, block 1 will no longer be 123/456/789, but one can relabel again to put it back. In fact, this reduces 36288 to around 1000 [this is also partly due to Bertram], which was verging on practical, even with my program. Following a few calculations, it was clear that some equivalences were still being missed, and I realised the equivalences which I pointed out in an earlier reply to tinfoil. Unfortunately, I've been quite busy, so didn't get around to working out how much this helped. One can also group together some other grids like
123 456 789
456 789 123
789 123 456
and
123 789 456
456 123 789
789 456 123
not just because (in this example) one can permute the blocks, but because the numbers in each column in the two configurations are the same.
Following Bertram's announcement of a quick program to do the brute force calculations, I got in touch and sent him a file of these equivalences I'd been looking at. He implemented the algorithm astonishingly quickly, and programmed the equivalences, reducing the number to be checked to about 300. Since he could check each in less than 2 minutes (compared with my 36 hours!), the calculation was reduced to less than 12 hours! In fact, he has subsequently discovered further equivalences which seem to reduce the number as far as 71. (The results of the program show that there are at least 44 essentially different configurations, so maybe it is possible to reduce 71 further.) The whole calculation can now be done in a couple of hours!
Frazer
- Guest
by su bloko » Tue May 24, 2005 11:54 am
Bertram wrote:The result of the computation is
6,670,903,752,021,072,936,960 = 2^15 * 3^8 * 5*7 * 27,704,267,971 = 9! * 72^2 * 2^7 * 27,704,267,971
Congratulations to Bertram for the efficient coding, and to the contributors who provided ideas to make the calculation managable. I will be able to sleep easier now that I know the number has been derived!
- su bloko
- Posts: 20
- Joined: 17 May 2005
well done
by coloin » Tue May 24, 2005 1:34 pm
Well done
I was nowhere
Yes I have been guessing - but it was in an effort to get an elegant solution - which it turns out there isnt.
I will recap
n = 9!^3*x1*x2*y1*y2
which are the possible positions of boxes
123
456
789
with options in each box of
9! x2 1
y2 9! x1
1 y1 9!
we demonstrated before [y1 = 1 = y2 ] if the sudoku turns out to be a valid one - ie doesnt fall foul of the constraints.
Some programs have worked out probable limits for n and from this we can work out average values and guess at the possible limits of x1 andx2
It is unlikly that the average "value" of x1 or x2 is an integer appealling though it was.
So we need to add up the individual x1s [448,432,400,392,384] multiplied by their respective x2s
This is not easy !
x1 is almost easy [see next line]
x2 is darn near impossible to work out as it moves round the square in two directions eventually ending back at x1 [box6]
Thats where I will stop and open my beer.
Well done again.
I was nowhere
Yes I have been guessing - but it was in an effort to get an elegant solution - which it turns out there isnt.
I will recap
n = 9!^3*x1*x2*y1*y2
which are the possible positions of boxes
123
456
789
with options in each box of
9! x2 1
y2 9! x1
1 y1 9!
we demonstrated before [y1 = 1 = y2 ] if the sudoku turns out to be a valid one - ie doesnt fall foul of the constraints.
Some programs have worked out probable limits for n and from this we can work out average values and guess at the possible limits of x1 andx2
It is unlikly that the average "value" of x1 or x2 is an integer appealling though it was.
So we need to add up the individual x1s [448,432,400,392,384] multiplied by their respective x2s
This is not easy !
x1 is almost easy [see next line]
x2 is darn near impossible to work out as it moves round the square in two directions eventually ending back at x1 [box6]
Thats where I will stop and open my beer.
Well done again.
- coloin
- Posts: 2493
- Joined: 05 May 2005
- Location: Devon
by Guest » Tue May 24, 2005 3:22 pm
su bloko wrote:Congratulations to Bertram for the efficient coding, and to the contributors who provided ideas to make the calculation managable. I will be able to sleep easier now that I know the number has been derived!
Thank you very much.
Here is a short 'history' of this effort from my perspective:
May 22, 2005: It all started with a post by a poster called Nigel in rec.puzzles (date: May 21, 2005, subject: "Sudoku combinatorics"), which stated that there is a discussion going on about how many total Sudoku configurations there are. At this point I was roughly aware what Sudoku is and I'm generally interested in combinatoric problems, so I had a look.
I skimmed the thread and saw that there were a number of estimates on the order of 6*10^21. Dividing by the obvious factor of 9!*72^2 yields 3*10^12 which is within reach of exhaustive enumeration by computers.
I then wrote a program to do that enumeration. I reused a couple of tricks from a program solving the n-queens-problem that I wrote recently; while the problems may seem dissimilar at first, both can be solved very efficiently by using bitmasks for calculating the possible values (positions) for the next place number (queen) in a backtracking search.
This turned out to produce, after some optimization, about 800k solutions per second on my PC (Athlon XP 2500+), which compared quite favourably to the numbers that I had seen posted here.
This is the program that I posted here.
Note that at this point I was not aware of the fact that this thread had been going on for over a month. If I had been aware of that, I'd probably have written a bit more about what I did and how in order to attract more attention.
May 23, 2005: Luckily, Frazer (afj) took my post seriously and contacted me about the program, with a request to modify it so it would accept a configuration of the first 3 boxes as its input and calculate the number of solutions with this initial placement. In that mail, he also mentioned that he was able to reduce the 36288 possible configurations for those boxes to 'just over 1000'. This got me thinking and I found one reduction that achieved this goal. This calculation would have taken about 20 hours of computation.
At this point I wrote my second posting in this thread.
Later that day, Frazer wrote me another mail in which he included a nice description of the other tricks for reduction that he had thought of. Using them I could reduce the 1089 configurations that I had to 306. At this point I restarted the computation (the 20 hours computation had been running for 4.5 hours) and started a new one. It is this computation where the number I posted came from.
In the meantime, I reimplemented the reduction program from scratch using a more suitable datastructure and algorithm and found that it had missed a few possibilities; had I exploited the equivalences that I knew about completely, the program would have produced only 174 configurations instead of 306.
Generalizing one of the equivalences then reduced this further to 71. I've actually redone the computation with this set of 71 configurations and re-obtained the same result.
So, thanks to Nigel, Josh (who mentioend the 6*10^21 estimate based on Monte Carlo simulation - this is the estimate that I trusted most from the whole thread), and many other contributors to this thread for convincing me that the problem was interesting, challenging but within reach of today's computers. Big thanks go to Frazer for contacting me, sharing his ideas and making me think about some not-so-obvious symmetries. The resulting improvement of a factor of more than 100 was invaluable.
Bertram
P.S. Re-reading the thread so far, the following estimate strikes me as most amazing:
tinfoil wrote:Step C: (and here is where my solution is not rigorous) What if we assume that each of these rules would constrain the number of valid solutions by exactly the same ratio? Then there would be a combined reduction ratio of R^2. So the intitial value of 1.0911*10^50 solutions would reduce by a factor of R^2, or 1.639*10^28, leaving 6.6571*10^21 valid solutions.
P.P.S. For those who are interested, the programs that I used and their output for the two calculations mentioned above can be found at http://www.inf.tu-dresden.de/~bf3/sudoku/
- Guest
by Guest » Tue May 24, 2005 4:28 pm
Bertram wrote:Bertram wrote:Thanks to a hint by afj I could speed up the process by another factor of 33, so you can expect an exact number later today or tomorrow.
Using some more ideas of afj I could reduce the time by another factor of 3.3. Had I applied them properly, this factor would've been close to 6, but the program I used for the reduction missed a few opportunities.
The result of the computation is
6,670,903,752,021,072,936,960 = 2^15 * 3^8 * 5*7 * 27,704,267,971 = 9! * 72^2 * 2^7 * 27,704,267,971
I wonder some of the factors of 2 can be explained by symmetries.
The calculation used about 6 hours of computation on two PCs.
I find it fascinating that the number 27704267971 seems to be prime!
That would seem to suggest that ANY other 'symmetrical' reduction is impossible, and yields the overall number of 'unique' solutions that cannot be obtained from another by substitution, reflection, swapping of chutes/rows,columns, etc.
- Guest
by Guest » Tue May 24, 2005 5:46 pm
I can confirm that 27704267971 is indeed prime. I was always very keen on tinfoil's heuristic argument giving 6.657 x 10^21 and believed it would be close to the final answer, probably within a couple of percent. The fact that it is within 0.2% is very pleasing.
The more I look at Bertram's programs, the more I'm impressed! While I had a reduction to about 1000 cases, I was aware that it was likely that I'd programmed it sufficiently inefficiently to be missing some of these cases (this was the point that Bertram's more efficient program reduced to 416), and planned to do something about it later. I had a couple more tricks up my sleeve, but I was really nowhere near programming these steps. Bertram's program to deal with these equivalences is just fantastic, and the program to then do the brute force calculation is about 1000 times faster than mine, which also speaks for itself... I'd still be nowhere near the answer! It's nice to feel that I've made a contribution, but I think the congratulations should mostly be aimed in Bertram's direction!
Frazer
The more I look at Bertram's programs, the more I'm impressed! While I had a reduction to about 1000 cases, I was aware that it was likely that I'd programmed it sufficiently inefficiently to be missing some of these cases (this was the point that Bertram's more efficient program reduced to 416), and planned to do something about it later. I had a couple more tricks up my sleeve, but I was really nowhere near programming these steps. Bertram's program to deal with these equivalences is just fantastic, and the program to then do the brute force calculation is about 1000 times faster than mine, which also speaks for itself... I'd still be nowhere near the answer! It's nice to feel that I've made a contribution, but I think the congratulations should mostly be aimed in Bertram's direction!
Frazer
- Guest
by su bloko » Tue May 24, 2005 6:12 pm
I have updated wikipedia's entry on sudoku to reflect Bertram's result.
http://en.wikipedia.org/wiki/Sudoku
Note that I have indicated that the result is awaiting independant validation.
http://en.wikipedia.org/wiki/Sudoku
Note that I have indicated that the result is awaiting independant validation.
- su bloko
- Posts: 20
- Joined: 17 May 2005
