Like many others, I've written a solver for Su Doku puzzles:

http://www.blott-online.com/sudoku/index.html

However, my interest here is not actually in solving puzzles, but rather in understanding the underlying rules at play.

Specifically, a solver might be called complete if, for any grid for which a unique solution exists, the solver will find that unique solution.

1) Does a set of heuristics exist such that a solver based on repeatedly applying those heuristics is complete?

2) I know that my own solver is not complete. Perhaps it is the case that no purely logic based solver can be complete. If that is the case, what is a canonical example of a puzzle with a unique solution which logic-based solvers cannot solve?

I'm not interested in solvers based on guessing; enumerating all possibilities is not elegant - even if heuristics are used to reduce the search space.

Please follow up if you have any insight into the completeness of logic-based solvers and their completeness or limitations.

Thanks,

Steve[/url]