Sudoku solver
Dave Angel
davea at davea.name
Thu Mar 26 10:14:33 EDT 2015
On 03/26/2015 08:37 AM, Chris Angelico wrote:
> On Thu, Mar 26, 2015 at 11:26 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
>> "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?
>
> 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
More information about the Python-list
mailing list