X-Received: by 10.224.18.132 with SMTP id w4mr13092152qaa.1.1364439631286; Wed, 27 Mar 2013 20:00:31 -0700 (PDT)
X-Received: by 10.50.214.36 with SMTP id nx4mr1737527igc.6.1364439631244; Wed, 27 Mar 2013 20:00:31 -0700 (PDT)
Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!ca1no13844160qab.0!news-out.google.com!v17ni9qad.0!nntp.google.com!ca1no13844157qab.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.python
Date: Wed, 27 Mar 2013 20:00:30 -0700 (PDT)
In-Reply-To: <9dla2a-kql.ln1@satorlaser.homedns.org>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=122.151.86.121; posting-account=JzVE4wkAAADCSo8EXJLK0dGqAu47aMvq
NNTP-Posting-Host: 122.151.86.121
References: <e45b8b75-ff89-4ee1-9ada-bfda3d06d05d@googlegroups.com> <9dla2a-kql.ln1@satorlaser.homedns.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <5ce10a13-be58-4548-85df-e1d865d3304e@googlegroups.com>
Subject: Re: Sudoku
From: Eric Parry <joan4eric@gmail.com>
Injection-Date: Thu, 28 Mar 2013 03:00:31 +0000
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Xref: csiph.com comp.lang.python:42075

On Wednesday, March 27, 2013 6:28:01 PM UTC+10:30, Ulrich Eckhardt wrote:
> Am 27.03.2013 06:44, schrieb Eric Parry:
>=20
> > I downloaded the following program from somewhere using a link from
>=20
> > Wikipedia and inserted the =93most difficult Sudoku puzzle ever=94 stri=
ng
>=20
> > into it and ran it. It worked fine and solved the puzzle in about 4
>=20
> > seconds. However I cannot understand how it works.
>=20
>=20
>=20
>=20
>=20
> In simple terms, it is using a depth-first search and backtracking. If=20
>=20
> you really want to understand this, get a book on algorithms and graphs=
=20
>=20
> (or locate an online source). I can try to give you an idea though.
>=20
>=20
>=20
>=20
>=20
>  > It seems to go backwards and forwards at random. Can anyone explain
>=20
>  > how it works in simple terms?
>=20
>=20
>=20
> I think your interpretation of what it does is wrong or at least flawed.=
=20
>=20
> It does try different combinations, but some don't lead to a solution.=20
>=20
> In that case, it goes back to a previous solution and tries the next one.
>=20
>=20
>=20
>=20
>=20
> I'll try to document the program to make it easier to understand...
>=20
>=20
>=20
> > def same_row(i,j): return (i/9 =3D=3D j/9)
>=20
> > def same_col(i,j): return (i-j) % 9 =3D=3D 0
>=20
> > def same_block(i,j): return (i/27 =3D=3D j/27 and i%9/3 =3D=3D j%9/3)
>=20
> >
>=20
> > def r(a):
>=20
>       # find an empty cell
>=20
>       # If no empty cells are found, we have a solution that we print
>=20
>       # and then terminate.
>=20
> >    i =3D a.find('0')
>=20
> >    if i =3D=3D -1:
>=20
> >      print a
>=20
> >      exit(a)
>=20
>=20
>=20
>       # find excluded numbers
>=20
>       # Some numbers are blocked because they are already used in
>=20
>       # the current column, row or block. This means they can't
>=20
>       # possibly be used for the current empty cell.
>=20
> >    excluded_numbers =3D set()
>=20
> >    for j in range(81):
>=20
> >      if same_row(i,j) or same_col(i,j) or same_block(i,j):
>=20
> >        excluded_numbers.add(a[j])
>=20
>=20
>=20
>       # create possible solutions
>=20
>       # Try all possibly numbers for the current empty cell in turn.
>=20
>       # With the resulting modifications to the sodoku, use
>=20
>       # recursion to find a full solution.
>=20
> >    for m in '123456789':
>=20
> >      if m not in excluded_numbers:
>=20
> >        # At this point, m is not excluded by any row, column, or block,=
 so let's place it and recurse
>=20
> >        r(a[:i]+m+a[i+1:])
>=20
>=20
>=20
>       # no solution found
>=20
>       # If we come here, there was no solution for the input data.
>=20
>       # We return to the caller (should be the recursion above),
>=20
>       # which will try a different solution instead.
>=20
>       return
>=20
>=20
>=20
>=20
>=20
> Note:
>=20
>=20
>=20
>   * The program is not ideal. It makes sense to find the cell with the=20
>=20
> least amount of possible numbers you could fill in, i.e. the most=20
>=20
> restricted cell. This is called "pruning" and should be explained in any=
=20
>=20
> good book, too.
>=20
>=20
>=20
>   * The style is a bit confusing. Instead of the excluded numbers, use a=
=20
>=20
> set with the possible numbers (starting with 1-9) and then remove those=
=20
>=20
> that are excluded. Then, iterate over the remaining elements with "for m=
=20
>=20
> in possible_numbers". This double negation and also using exit() in the=
=20
>=20
> middle isn't really nice.
>=20
>=20
>=20
>=20
>=20
> Good luck!
>=20
>=20
>=20
> Uli

Thank you for your explanation.
I noticed that in this particular puzzle when it ran out of candidates in a=
 particular cycle, it then changed the last entry to the next one in line i=
n the previous cycle. But I cannot find any code to do this.
I was hoping to understand the logic so that I could re-write it in VBA for=
 excel which would enable any puzzle to be entered directly.
Your comments are a big help especially the double negative aspect.
Eric.