From SuDoku.
The Yahoo robot, Slurp, has been playing a lot of sudoku on my site of late. That got me wondering if it ever solved a puzzle?
Normally one tries to avoid guessing. My sudoku assistant, sudokant, helps in this process by applying the two most obvious rules for me as I play. Using it, like Slurp, I thought I'd play some sudoku while only guessing. For fun I started from the blank puzzle.
I guessed where all the 9s would be, then the 8s, and so on until I got stuck just short of 1s. A second try came almost as close. Imagine that.
I tried again using reading order but rotating the puzzle in my head so that I started each number with the board 90 degrees ccw from the previous. This made some interesting patterns along the way but still stopped early.
So I ask, is there one extra rule, beyond the two simple ones in sudokant, that will solve the blank puzzle without backtracking? -- WardCunningham
Perhaps the lack of a suggested single extra rule means that there isn't one. Indeed, no additional rules have been offered, which suggests that there isn't one. On the other hand we can quote without thinking "AbsenceOfEvidenceIsNotEvidenceOfAbsence". Or is it?
Preserving this lovely solution from the spammers (sorry I forgot the name of the contributor) That was me. I believe what I wrote before was something like, this is a solution, but Ward's question was more interesting than just "can you find a solution" and I'm not sure this helps. -- DanielKnapp
Not to answer your question directly, but this:
Your examples show the same characteristic, where the number of permitted numbers in a sub-square is not as many as the number of squares to be filled. Consider the middle-bottom sub-square of your last example. There are five places to fill, but only 1, 2, 3 and 4 to use.
Perhaps you might consider this. For each row, column and square, each number must appear. In the example I give here, the top left square cannot contain a 4, and yet this fact is not obvious from the presentation. Similarly in your last example it is not obvious that the bottom-middle square cannot contain a 5.
That's not all, though. Consider this example:
The middle square is of particular interest. It's not clear from the sudokant presentation, but the 2, 8 and 9 must go in the middle column.
I found this trivial solution to generating a validly filled Sudoku from the blank state:
123 789 456 456 123 789 789 456 123 912 678 345 345 912 678 678 345 912 891 567 234 234 891 567 567 234 891Notice that we start with an in-order 3x3 sub-block, and iterating over these 3x3 blocks first by column, then by row, we rotate the 3x3 block one row for for each 3x3 column change, and one column for each 3x3 row change. Each subblock remains in 1 to 9 order, but with a different starting point, and no 3x3 subblock is repeated. This permutation trick works using any random order of 1-9 for the initial 3x3 block, since it follows the "only once per row box and column" rules. -- LucasAckerman