X-Received: by 10.224.18.132 with SMTP id w4mr10775734qaa.1.1364363068579; Tue, 26 Mar 2013 22:44:28 -0700 (PDT)
X-Received: by 10.50.109.228 with SMTP id hv4mr749322igb.2.1364363068433; Tue, 26 Mar 2013 22:44:28 -0700 (PDT)
Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!t2no20890922qal.0!news-out.google.com!k8ni11100qas.0!nntp.google.com!ca1no11425935qab.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.python
Date: Tue, 26 Mar 2013 22:44:28 -0700 (PDT)
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=122.151.64.71; posting-account=JzVE4wkAAADCSo8EXJLK0dGqAu47aMvq
NNTP-Posting-Host: 122.151.64.71
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e45b8b75-ff89-4ee1-9ada-bfda3d06d05d@googlegroups.com>
Subject: Sudoku
From: Eric Parry <joan4eric@gmail.com>
Injection-Date: Wed, 27 Mar 2013 05:44:28 +0000
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Xref: csiph.com comp.lang.python:41979

I downloaded the following program from somewhere using a link from Wikiped=
ia and inserted the =E2=80=9Cmost difficult Sudoku puzzle ever=E2=80=9D str=
ing into it and ran it. It worked fine and solved the puzzle in about 4 sec=
onds. However I cannot understand how it works. It seems to go backwards an=
d forwards at random. Can anyone explain how it works in simple terms?
Eric.


def same_row(i,j): return (i/9 =3D=3D j/9)
def same_col(i,j): return (i-j) % 9 =3D=3D 0
def same_block(i,j): return (i/27 =3D=3D j/27 and i%9/3 =3D=3D j%9/3)

def r(a):
  i =3D a.find('0')
  if i =3D=3D -1:
    print a
    exit(a)

  excluded_numbers =3D 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 l=
et's place it and recurse
      r(a[:i]+m+a[i+1:])

r('800000000003600000070090200050007000000045700000100030001000068008500010=
090000400')
Sudoku solver where the puzzle is an 81 character string representing the p=
uzzle read left-to-right, top-to-bottom, and 0 is a blank.
=E2=80=83