This popular Japanese number puzzle has just one easy rule:
In every Row, every Column and every 3x3 sub-grid, all the numbers from 1 to 9 should appear, but only once in each row, column and sub-grid.
+------+-------+------+
| 0 0 0 | 7 0 0 | 4 0 0 |
| 0 3 0 | 0 9 0 | 0 2 0 |
| 4 0 0 | 0 0 5 | 0 0 0 |
+------+-------+------+
| 0 0 8 | 0 0 0 | 0 0 5 |
| 0 9 0 | 0 3 0 | 0 7 0 |
| 6 0 0 | 0 0 0 | 3 0 0 |
+------+-------+------+
| 0 0 0 | 4 0 0 | 0 0 6 |
| 0 7 0 | 0 2 0 | 0 9 0 |
| 0 0 5 | 0 0 8 | 0 0 0 |
+------+-------+------+
Replace the 0's with the digits required to satisfy the rule.
(In reply to
Program execution in less than a minute by Penny)
No, I meant what I said--that it runs in 1.03 seconds.. just over 1 second. You should be able to run my program yourself, right? You have VB.Net...just cut and paste the code from my earlier post (comment 18). Your mileage may vary depending on your machine speed, but I bet it will easily run in under 10 seconds.
I thought the same thing though--it's too fast--is it really searching all possibilities? That's why I tried the more difficult variation by changing the first 7 in the puzzle to a 0, creating many more possible solutions. I wanted to be sure it was doing a full search. There are 82 solutions this way, and it finds them all in about 10 seconds. Charlie verified this result with his program (see comment 19).
=================
I was just playing with it again. If I exchange the rows and columns in the grid as follows, the program gives the same solution (rows & columns exchanged, of course) but it runs almost 3 times faster (in 0.344 seconds):
Dim board As Integer(,) = { _
{0, 0, 4, 0, 0, 6, 0, 0, 0}, _
{0, 3, 0, 0, 9, 0, 0, 7, 0}, _
{0, 0, 0, 8, 0, 0, 0, 0, 5}, _
{7, 0, 0, 0, 0, 0, 4, 0, 0}, _
{0, 9, 0, 0, 3, 0, 0, 2, 0}, _
{0, 0, 5, 0, 0, 0, 0, 0, 8}, _
{4, 0, 0, 0, 0, 3, 0, 0, 0}, _
{0, 2, 0, 0, 7, 0, 0, 9, 0}, _
{0, 0, 0, 5, 0, 0, 6, 0, 0} _
}
Don't ask me why--apparently the search paths are shorter this way. If I change that 7 to a 0, it finds the 82 solutions in 2.688 seconds.
I also found that if I leave the 7 as is, but change the 4 in the first row to a zero (in the original puzzle), there's only one solution (the same as the original solution), but it takes 6.86 seconds to find it. If I transform that grid (columns & rows) it only takes 0.625 seconds to find the solution.
Again, in all these cases, the program keeps looking for more solutions until it's exhausted all possibilities. I think it's amazing how much variance there is in these different scenarios.
Edited on June 4, 2005, 5:08 pm
Edited on June 4, 2005, 5:09 pm
re: Program execution in less than a minute
