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. * http://c2.com/~ward/sudokant.cgi?46839572.3.24875697592.6438836.59274295746.38.4782369568.5479.395482367.37296.584 * http://c2.com/~ward/sudokant.cgi?893456.7.475..8693..6397458.395647.88467.935.57..839649.734568..6.9875348456..7.9 Hmm. Maybe random is the wrong approach. I'll be totally deterministic choosing the first available 9 in each square, then the first available 8, and so on. This blocked a lot faster. * http://c2.com/~ward/sudokant.cgi?987.........987.........98789.7.....7..89..........89...9..8........9..8..8.....9 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. * http://c2.com/~ward/sudokant.cgi?957..6..8..6958..7..87..956795.8..6..6.795.8..8.6..5975796..8.....8796..86.....79 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 * http://c2.com/~ward/sudokant.cgi?123456789456789123789123456234567891567891234891234567345678912678912345912345678 ---- Not to answer your question directly, but this: * http://c2.com/~ward/sudokant.cgi?123..........4...........4....................................................... already has no solution, and yet sudokant, which directly embodies the rules as stated, doesn't recognise that. 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: * http://c2.com/~ward/sudokant.cgi?.7.3.........6......97.8.5...6..79..7.51..........5.......6.....4.93.6.22...8.... 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. * The 3, 4 and 6 cannot go in the middle column of the middle square, so the 2, 8 and 9 must. That means that 2, 8 and 9 cannot go in the middle column of the top-middle and bottom-middle squares, even though sudokant shows them as possibilities. They're not. I don't know how you could present these clear deductions. Perhaps to do so would turn sudokant from a servant to a master, effectively solving the puzzle, and leaving you nothing to do. ---- 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 891 Notice 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