Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.081 X-Spam-Evidence: '*H*': 0.84; '*S*': 0.00; 'second.': 0.09; 'solution,': 0.09; 'docstring': 0.16; 'program?': 0.16; 'python- based': 0.16; 'solver': 0.16; 'url:ics': 0.16; 'url:py': 0.16; 'wrote:': 0.18; 'otherwise,': 0.22; 'logical': 0.24; 'question': 0.24; 'sort': 0.25; '>': 0.26; 'holds': 0.26; 'second': 0.26; 'url:edu': 0.26; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; 'statement': 0.30; 'message-id:@mail.gmail.com': 0.30; 'usually': 0.31; 'another': 0.32; 'could': 0.34; 'one,': 0.35; 'received:google.com': 0.35; 'described': 0.36; 'returning': 0.36; 'sequence': 0.36; 'possible': 0.36; 'should': 0.36; 'error.': 0.37; 'being': 0.38; 'to:addr:python-list': 0.38; 'skip:& 20': 0.39; 'to:addr:python.org': 0.39; 'solve': 0.60; 'reach': 0.63; 'here': 0.66; 'between': 0.67; 'mar': 0.68; '26,': 0.68; 'presented': 0.69; 'trial': 0.83; '2015': 0.84; 'water.': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=8njKDmHdy7k/RqNP7pTZXgluUPb1gJbkWxMmj0QTV08=; b=0me6tsv9YBoFbyxYX/e1mv9HsdVrT6RDi146/8ODgKlxVdt1OaloHxQ4bm4HziX3MP 8HXn+I0sXdddMxI0c5aUxLtqYCnDxYzh50NCkObE+Sxj6knnv7vFtWt0fHc7gdOHP9py RW2UYdv6Jc2vdrjxluqjguYVGFn39e6+mYU9EV/2t9Ge6fCo+UUnQtwTOSjKMBrRKTE3 +PTIiPK73TQ1JiQsipdoFwg1vRGUMnesdbMfcBZI29dxwoN6xYxkV3SDs/O6kSpODNlK fY8aUfJcg3IWLP6JdaBfUgLq73xowIyP6dYP9rGT9O6MQyPQTlTLhjy0Zn9YxHsdT4aX qr7w== MIME-Version: 1.0 X-Received: by 10.66.65.234 with SMTP id a10mr27248683pat.120.1427375755257; Thu, 26 Mar 2015 06:15:55 -0700 (PDT) In-Reply-To: <87fv8sndw1.fsf@elektro.pacujo.net> References: <87r3sdnw5t.fsf@elektro.pacujo.net> <87fv8sndw1.fsf@elektro.pacujo.net> Date: Thu, 26 Mar 2015 07:15:55 -0600 Subject: Re: Sudoku solver From: Ian Kelly To: Python Content-Type: multipart/alternative; boundary=001a11363698da754a051230d000 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.19 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 62 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1427375759 news.xs4all.nl 2859 [2001:888:2000:d::a6]:59304 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:88050 --001a11363698da754a051230d000 Content-Type: text/plain; charset=UTF-8 On Mar 26, 2015 6:31 AM, "Marko Rauhamaa" wrote: > > "Frank Millman" : > > > 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? It's an accurate characterization of the sort of puzzles that are typically presented as sudoku. I don't think that I have used trial and error, in my head or otherwise, in any sudoku I have ever solved. > > 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. Perhaps this is why that puzzle was described as being so difficult: it required steps that human solvers don't usually take. --001a11363698da754a051230d000 Content-Type: text/html; charset=UTF-8

On Mar 26, 2015 6:31 AM, "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?

It's an accurate characterization of the sort of puzzles that are typically presented as sudoku. I don't think that I have used trial and error, in my head or otherwise, in any sudoku I have ever solved.

> > 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.

Perhaps this is why that puzzle was described as being so difficult: it required steps that human solvers don't usually take.

--001a11363698da754a051230d000--