Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #41979
| 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> (permalink) |
| 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 |
Show key headers only | View raw
I downloaded the following program from somewhere 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.
Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread
Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-26 22:44 -0700
Re: Sudoku Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2013-03-27 08:58 +0100
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-27 20:00 -0700
Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-28 00:36 -0400
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 15:11 -0700
Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-28 19:28 -0400
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 22:07 -0700
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 22:07 -0700
Re: Sudoku Chris Angelico <rosuav@gmail.com> - 2013-03-29 09:45 +1100
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-29 14:47 -0700
Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-29 18:11 -0400
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-30 15:06 -0700
Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-30 19:15 -0400
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:03 -0700
Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-31 18:34 -0400
Re: Sudoku Arnaud Delobelle <arnodel@gmail.com> - 2013-03-31 23:59 +0100
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:03 -0700
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:27 -0700
Re: Sudoku Chris Angelico <rosuav@gmail.com> - 2013-04-01 09:35 +1100
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 20:58 -0700
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:27 -0700
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-30 15:06 -0700
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-29 14:47 -0700
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 15:11 -0700
Re: Sudoku Damien Wyart <damien.wyart@free.fr> - 2013-03-27 09:49 +0100
Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-27 05:38 -0400
Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-27 19:49 -0700
csiph-web