[Haskell-cafe] Re: Code Review: Sudoku solver

[Aaron Denney]

On 2006-04-03, Daniel Fischer <daniel.is.fischer at web.de> wrote:
> does anybody know whether in a uniquly solvable sudoku-puzzle guessing is 
> never necessary, i.e. by proper reasoning ('if I put 6 here, then there must 
> be a 3 and thus the 4 must go there...' is what I call guessing) there is 
> always at least one entry determined?

No, it sometimes is, (well, depending on your set of base inference
rules -- throwing all possible solutions in and doing pattern matching
technically allows no-backtracking solutions).

Most people use "eliminate all impossible numbers in a given box
(that is, that number occurs in same row, column, or square)", combined
with "if there is only one place in this {row, column, square} a number
can be, place it."

But there are additional common patterns such as "if there are N boxes
in a {row, column, square}, each with a subset of N numbers, then
eliminate those numbers in the other squares.  For example if two boxes
in a row both only allow 2 and 3, then 2 and 3 can be eliminated from
all the other boxes in that row.  These are often worth implementing as
they can radically reduce guessing.  Also worth doing may be chains of
reasoning that can restrict a number to be in a given row or column of
a square (or square of a row or column), which can then eliminate it
from other places.

-- 
Aaron Denney
-><-