Sudoku solver

[Frank Millman]

"Marko Rauhamaa" <marko at pacujo.net> wrote in message 
news:87fv8sndw1.fsf at elektro.pacujo.net...
> "Frank Millman" <frank at chagford.com>:
>
>> Here is another python-based sudoku solver -
>>
>> http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
>>
>>>From its docstring -
>>
>> "A proper Sudoku puzzle must have a unique solution, and it should be
>> possible to reach that solution by a sequence of logical deductions
>> without trial and error.
>
> I don't think that statement holds water. Trial-and-error is at the
> basis of deduction (reductio ad absurdum). The human solver employs it
> in their head. The question is, what is the difference between
> pen-and-paper and in-your-head for a computer program?
>
[...]
>>
>> It solved Marko's original puzzle and Ian's puzzle in less than a
>> second. It could not solve Marko's second one, returning "impossible"
>> immediately.
>
> ... but that realization greatly reduces the value of the solver.
>

I was not happy with that conclusion, but I was not sure why. Now I think I 
can put it into words.

There seems to be disagreement over the use of the term 'trial and error'. 
How about this for a revised wording -

"It should be possible to reach that solution by a sequence of logical 
deductions. Each step in the sequence must uniquely identify the contents of 
at least one cell based on the information available. Each time a cell is 
identified, that adds to the information available which can then be used to 
identify the contents of further cells. This process continues until the 
contents of all cells have been identified."

Any puzzle that cannot be solved by this method does not qualify as a true 
Sudoku puzzle.

Frank