Tue, 19 Jul 2005 10:22:15 -0400 Michael Kleber <michael.kleber@gmail.com> Michael B Greenwald wrote:
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.
Wow. How many times in a row can you flip Heads? Better yet, want to come pick lottery numbers for me? :-) Certainly you've just been getting lucky. The published puzzles are guaranteed to have only one solution, so every time you arbitrarily choose one of two possible values for a square, you should have a 50-50 chance of reaching an impossible position. The choices last night didn't show up in published puzzles, they were in ones my kids made for me. Last night no choices had showed up in the 4 or 5 "evil" examples from the web site, or in the 3 examples from math-fun. I tried again for a few minutes this morning, and got a backtracking case. However, it seems that the categories "evil" is not hard in the sense of forcing this algorithm to backtrack --- in my very small sample, a relatively small fraction of evil puzzles have any backtracking (just 1 out of 7). Again, this could be luck.
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").
Here's an example of a line of reasoning that you'll miss: add two more empty boxes to the above example, like so: {1,2,8,9}, {1,8,9}, {1,8}, {1,9}, {2,3,4}, {2,3,4} It's still the case that the first box must contain the 2, because the boxes {1,8,9}, {1,8}, {1,9} certainly account for all of the 1,8,9 among them in some order. Yes, this line of reasoning could lead to something the program will miss, but this particular example doesn't work because of the rule that says "choose the square with fewest options first". There are extended discussions of computer solving techniques -- start at the giant user forum at sudoku.com and follow links from there, I think. Thanks. I will look there, although I'm not looking for computer solving techniques, I was trying to understand what you meant when you mentioned "logic" vs. "guess-and-check". Another question: does anyone know the minimal number of squares needed to uniquely determine a solution?