Sudoku solver

[Marko Rauhamaa]

"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?

(Question: Are computers good at blindfold chess?)

> To the extent possible, we strive to keep the same ethic in our
> automated solver, by mimicking human rule-based reasoning, rather than
> resorting to brute force backtracking search."

That's cool...

> A neat feature is that, having printed the solution, it then lists
> every step it took in its reasoning process to arrive at the solution.
>
> 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 brought up sudoku solving as a "real-world" example of the usefulness
of exhaustive recursion. The concerns on astronomical execution times
must be considered but at the same time, one should realize things
aren't as bad as they would seem: exhaustion is a practical way to solve
sudoku puzzles and analogous programming challenges.

The compactness of a working sudoku solver should demonstrate something
about (1) the usefulness of recursion and (2) the expressive power of
Python.


Marko