Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 26 Mar 2015 10:14:33 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Sudoku solver
References: <87r3sdnw5t.fsf@elektro.pacujo.net> <mailman.188.1427358005.10327.python-list@python.org> <87fv8sndw1.fsf@elektro.pacujo.net> <CAPTjJmrq4+W7vgVmZZKnOCFtTy5R27vinD1mFUTEyhaUKA+BuQ@mail.gmail.com>
In-Reply-To: <CAPTjJmrq4+W7vgVmZZKnOCFtTy5R27vinD1mFUTEyhaUKA+BuQ@mail.gmail.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.202.1427379292.10327.python-list@python.org>
Lines: 67
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:88055

On 03/26/2015 08:37 AM, Chris Angelico wrote:
> On Thu, Mar 26, 2015 at 11:26 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> "Frank Millman" <frank@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