« March 2005 | Main | January 2006 »
September 28, 2005
Sudoku Heuristics
Ever play that number puzzle named "Sudoku"? I figured I'd list out the heuristics I use to help solve puzzles. I'm missing at least one though.
For this discussion, "box" refers to a single box in the puzzle, in which one number fits. "Square" refers to a 3x3 group of boxes; and there are nine squares in a puzzle. Also, 9-tuple refers to any set of nine boxes belonging to the same row, column, or square, in which no two boxes contain the same numeral.
1. Trivial case: One missing digit in row, column, or square. Identify the missing number and place it in the box.
2. Missing third of a triplet (one number in each of three rows or columns) along three consecutive squares. This narrows the possibilities to three or fewer boxes. Examine the perpendicular row or column to see whether the numeral exists there, and if so, then this narrows the possibilities to two or one. If one, then place the numeral in the box.
3. Duplicate possible solution sets in row, column, or square. This is when 'x' boxes within the n-tuple share the identical set of 'x' possible solutions. For example, when two boxes in the same square can each be either "4" or "5" based on the currently known boxes in the puzzle. In this case, these numerals should be removed from possible solutions to other boxes in the n-tuple. This heuristic is not intuitive, though its degenerate case of "once you know a box's solution, that numeral cannot appear in any other boxes belonging to any n-tuple in which the solved box is a member"...that is to say, the basic premise of the puzzle.
I think there's a key heuristic missing from this list, and I'm trying to figure out what it is.
Posted by Pat at 01:50 PM