"Frank Millman" <fr...@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 -- https://mail.python.org/mailman/listinfo/python-list
