Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Wed, 27 Mar 2013 05:38:48 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130308 Thunderbird/17.0.4
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Sudoku
References: <e45b8b75-ff89-4ee1-9ada-bfda3d06d05d@googlegroups.com>
In-Reply-To: <e45b8b75-ff89-4ee1-9ada-bfda3d06d05d@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.3802.1364377147.2939.python-list@python.org>
Lines: 50
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:41999

On 03/27/2013 01:44 AM, Eric Parry wrote:
> I downloaded the following program from somewhere

It'd be good to show where you found it, and credit the apparent author. 
  Bill Barksdale posted this in 2008 at:
 
http://stackoverflow.com/questions/201461/shortest-sudoku-solver-in-python-how-does-it-work

I don't know if there are older ones somewhere, but I didn't find any. 
I did find places that quoted his code without attribution.

Another thing worth pointing out is that it's only valid for Python 2.x 
  (naturally, since I don't think Python 3 was out at that point)

using a link from Wikipedia and inserted the “most difficult Sudoku 
puzzle ever” string into it and ran it. It worked fine and solved the 
puzzle in about 4 seconds. However I cannot understand how it works. It 
seems to go backwards and forwards at random. Can anyone explain how it 
works in simple terms?
> Eric.
>
>
> def same_row(i,j): return (i/9 == j/9)
> def same_col(i,j): return (i-j) % 9 == 0
> def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
>
> def r(a):
>    i = a.find('0')
>    if i == -1:
>      print a
>      exit(a)
>
>    excluded_numbers = set()
>    for j in range(81):
>      if same_row(i,j) or same_col(i,j) or same_block(i,j):
>        excluded_numbers.add(a[j])
>
>    for m in '123456789':
>      if m not in excluded_numbers:
>        # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
>        r(a[:i]+m+a[i+1:])
>
> r('800000000003600000070090200050007000000045700000100030001000068008500010090000400')
> Sudoku solver where the puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank.
>  
>


-- 
DaveA