Mon, 18 Jul 2005 09:26:25 -0400 Michael Kleber <michael.kleber@gmail.com> A central tenet of sudoku puzzles is that they should be solvable "by logic alone", which is to say, without any trial-and-error. This sparks religious battles within the sudoku-solving community, as people argue over whether certain techniques are legitimate logic or just glorified guess-and-check. Of course, what techniques you recognize as legitimate dictates how you rate the difficulty (or even the solvability) of various puzzles. OK, it's cheating, but I wrote a quick program to solve sudoku puzzles. I tried it out on the examples that were sent in mail to math-fun, as well as a bunch of "evil" ones from websudoku.com Using only 2 simple rules it never had to backtrack (I guess backtracking would be equivalent to "guess-and-check"). To be perfectly clear, there were times (rare) when there was no square with a unique choice, but choosing randomly at that point never ended up getting me into a dead end. I didn't do anything clever, just coded up the technique I would use if I were trying to solve it by hand (on paper). That is, I kept a list of possible numbers for each given square. Rule 1 was that if you added a number n to a square at row r, column c, then you remove n from the allowed numbers for all squares in row r, in column c, and in the 3x3 box to with r,c belongs. Rule 2 says that at any point, if there is only one square in a row, or a column, or a 3x3 box that contains some number n as a possible value (e.g. if a row has 4 open squares which could be, respectively (1,2,8 or 9), (1,8, or 9), (1 or 8) and (1 or 9), then the first square would take on the value "2"). At each step in time you choose the square with the fewest allowable values, choose one of them, and then update the constraints using rules 1 and 2. The code also will backtrack if you ever get to a point where a square has no allowed values. But I never got to such a deadend in my, admittedly small, sample. Is this true of all sudoku puzzles? Or have I just gotten lucky? [I haven't performed the obvious test of going back after success and choosing the *other* value in the cases where there were multiple choices.] I suspect that I've just gotten some lucky examples --- can someone give me an example of a "controversial" puzzle where one would have to backtrack?