On 03/26/2015 08:37 AM, Chris Angelico wrote:
On Thu, Mar 26, 2015 at 11:26 PM, Marko Rauhamaa <ma...@pacujo.net> wrote:
"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?
Nothing. And solving a Sudoku puzzle - or any other puzzle - should
require no guessing. It should be possible to solve purely by logic.
Same goes for every other kind of puzzle out there; it's highly
unsatisfying to play Minesweeper and get to the end with a block of
four squares in a corner, two mines left, and no way of knowing which
diagonal has the mines and which is clear.
No trial-and-error, thanks.
I think you're making an unwarranted assumption here. Your Minesweeper
example has two solutions, so there's no way of telling which is the
"correct" one. But I'd claim that there are puzzles which have exactly
one solution, but which need trial and error at some point to find that
solution.
I'm not sure how to prove it, since somebody could claim that I just
haven't tried all the non-trial-and-error rules.
I did write a Sudoku-solver many years ago, in C++, and it solved the
typical Sudoku I fed it in about 2ms. But it was deliberately written
to apply only rules that humans could readily apply. No backtracking.
I did not at that time have any electronic source for puzzles, and I got
bored with manually entering them in from puzzle books. So I never
actually encountered a puzzle it couldn't solve. I mostly used it to
determine that a puzzle I couldn't manually solve was in fact uniquely
solvable, and that I'd just messed up somehow.
I wish I still had that source code, as it probably sounds like I'm
blowing smoke here.
The general approach I used was to make objects of each of the cells,
which tracked its neighbors to decide whether its value was determined.
And when it was determined, it notified its other neighbors. In turn,
if that decided a value for any of the neighbors, that cell notified its
neighbors. Likewise each row or column or box kept track of its state
and notified the appropriate cells whenever something interesting was
discovered. Then the outer loop just tickled each cell in turn, and the
solution rippled out.
Maybe I'm misinterpreting your phrase "No trial and error, thanks".
Perhaps you're saying that puzzles that require trial and error are no
fun to solve for humans. And that's a different matter entirely. I do
the daily KenKen puzzles in my local paper, and they're just hard enough
to be fun, seldom taking longer than I'm willing to take in the mornings.
--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list
