sudoku solver in Python ...
Derek Marshall
I haven't had the pleasure of posting anything here in many years ...
http://derek.marshall.googlepages.com/pythonsudokusolver
Appreciate any feedback anyone who takes the time to have a look would
want to give ...
Yours with-too-much-time-to-kill-on-the-train'ly,
Derek
Shawn Milochik
> --
> http://mail.python.org/mailman/listinfo/python-list
For those interested in this topic, here's another (much shorter) one:
I'm not making any judgements here, though. If anyone takes the time
to actually review them, I'd be interested in hearing any educated
comparisons.
Shawn
Tim Roberts
>This is just for fun, in case someone would be interested and because
>I haven't had the pleasure of posting anything here in many years ...
>
> http://derek.marshall.googlepages.com/pythonsudokusolver
>
>Appreciate any feedback anyone who takes the time to have a look would
>want to give ...
In my view, the canonical Python sudoku solver is located here:
http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
This is from David Eppstein, a professor of Computer Science at the
University of California at Irvine.
More than just solving the puzzles, his script actually prints out the
individual steps that lead to the solution, one by one, in readable
English. I've used it several times just to get a hint at the next step in
a solution. It can also create new puzzles.
His website contains a large collection of interesting public domain Python
scripts for numerical analysis and linear programming problems and puzzles.
http://www.ics.uci.edu/~eppstein/
--
Tim Roberts, ti...@probo.com
Providenza & Boekelheide, Inc.
Boris Borcic
> On Jan 23, 2008, at 10:02 PM, Derek Marshall wrote:
>
>> http://mail.python.org/mailman/listinfo/python-list
>
> For those interested in this topic, here's another (much shorter) one:
>
> http://norvig.com/sudoku.html
>
> I'm not making any judgements here, though. If anyone takes the time
> to actually review them, I'd be interested in hearing any educated
> comparisons.
>
> Shawn
So would I. Below is the "winner" of my hacking for an as fast as possible 110%
pure python (no imports at all!) comprehensive sudoku solver under 50 LOCs, back
in 2006. Performance is comparable to the solver you advertize - numbers are
slightly better, but platform differences could easily absorb that - eg (not
counting module initialization and not using psyco) it takes 9.3 ms average on
the "AI escargot" problem linked to in Norwig's page, 5.6 ms/problem on some
standard "top1465" list of hard problems, and 3.4 ms/problem on the first 1000
on some other "top50000" list of relatively hard problems. This on my 2GHz Intel
Centrino '05 laptop. Psyco reduces times by about 50%. Dropping performance
requirements by half allows reducing LOC count in proportion.
OTOH, the code although short is nearly unreadable, sorry; should probably
feature/comment it on some web page, like the two already proposed in the
thread. Will do if/for reviewer. Interface is calling sudoku99(problem) with
'problem' a standard 81 character string with '0' or '.' placeholder for
unknowns. Returns same with values filled in.
Beware that although in practice it solved all well-formed human-solvable
problems I could find, it is not guaranteed to deal properly (or even
terminate?) for underdetermined problems or determined problems that would
require exploring choicepoints with more than 2 possibilities (if such exist).
Cheers, Boris
w2q = [[n/9,n/81*9+n%9+243,n%81+162,n%9*9+n/243*3+n/27%3+81]
for n in range(729)]
q2w = (z[1] for z in sorted((x,y) for y,s in enumerate(w2q) for x in s))
q2w = map(set,zip(*9*[q2w]))
w2q2w = [set(w for q in qL for w in q2w[q] if w!=w0) for w0,qL in enumerate(w2q)]
empty = set(range(729)).copy
def sudoku99(problem) :
givens = set(9*j+int(k)-1 for j,k in enumerate(problem) if '0'<k)
ws=search(givens,[9]*len(q2w),empty())
return ''.join(str(w%9+1) for w in sorted(ws))
def search(w0s,q2nw,free) :
while 1 :
while w0s:
w0 = w0s.pop()
for q in w2q[w0] : q2nw[q]=100
wz = w2q2w[w0]&free
free-=wz
for w in wz :
for q in w2q[w] :
n = q2nw[q] = q2nw[q]-1
if n<2 :
ww,=q2w[q]&free
w0s.add(ww)
if len(free)==81 : return free
thres = int((len(free)+52.85)/27.5)
ix,vmax = -1,0
try :
while 1 :
ix=q2nw.index(2,ix+1)
for w0 in (q2w[ix]&free)-w0s :
v = len(w2q2w[w0]&free)
if v > vmax :
ixmax = ix
if v >=thres : break
vmax = v
w0s.add(w0)
else : continue
break
except : pass
w0,w1 = q2w[ixmax]&free
try :
w0s.clear()
w0s.add(w0)
return search(w0s,q2nw[:],free.copy())
except ValueError :
w0s.clear()
w0s.add(w1)
Thomas Thiel
Neither fast nor user friendly, but very concise:
options = set([str(i) for i in range(1, 10)])
def solve(puzzle):
i = puzzle.find('0')
if i < 0:
print puzzle
return
exclude = set(
puzzle[j] if i//9 == j//9 or i%9 == j%9
or i//27 == j//27 and (i%9)//3 == (j%9)//3
else '0'
for j in range(81)
)
for option in options - exclude:
solve(puzzle[:i] + option + puzzle[i+1:])
solve('200375169639218457571964382152496873348752916796831245900100500800007600400089001')
solve('054300070001620000900000315600250401003408900208061007386000009000097100070006240')
solve('206089500900500000038060900090001003700090008100600090001050840000007001009140207')
solve('000100005007048002020900007030002900500000004006800010800001040600280500100004000')
solve('000897000009000001006010090030000020000574000010000060080020700500000900000763000')
solve('500010900730200005000060070000500800800000003004007000010080000200001069006070004')
solve('070040063002009040500000800000070300900806007008050000007000002010400700690020030')
solve('570090180030000004080000600002405000000000000000609500005000090300000020091030075')
solve('070040063002009040500000800000070300900806007008050000007000002010400700690020030')
solve('180000400000800000009034500040960000520080076000053010002510700000002000007000092')
solve('060030000045900028008000730000090050900806007080050000036000900420009380000020010')
solve('001400000000078601000050900080000023013000560950000070005040000309180000000007300')
solve('705020003003500000400700006000030820000000000062090000300008009000004100100070302')
solve('001007400000020096600300000057008900930000051006900270000006005820070000005200800')
solve('007300200300000001800620000073400005000000000500008490000067004200000006009004300')
I can't take credit for it, though.
It's an adaptation of a one-liner in Groovy, that comes with the
ducumentation:
def r(a){def i=a.indexOf(48);if(i<0)print a
else(('1'..'9')-(0..80).collect{j->
g={(int)it(i)==(int)it(j)};g{it/9}|g{it%9}|g{it/27}&g{it%9/3}?a[j]:'0'}).each{
r(a[0..<i]+it+a[i+1..-1])}}
Although this one-liner is buggy, the underlying idea is good,
so I pilfered ;-)
OT:
If you're interested in a slightly more readable (and working) version:
def r(a){
def i = a.indexOf(48)
if( i < 0 ){ println a; return }
( ('1'..'9') -
( 0 .. 80).collect{ j->
i.intdiv(9) == j.intdiv(9) || i%9 == j%9 ||
i.intdiv(27) == j.intdiv(27) && (i%9).intdiv(3) == (j%9).intdiv(3)
? a[j] : '0'
}
).each{
r(a[0..<i] + it + (i==80 ? "" : a[i+1..-1]))
}
}
Thomas
pataphor
Thomas Thiel <thomas....@freenet.de> wrote:
> Neither fast nor user friendly, but very concise:
This is a bit faster:
options = set([str(i) for i in range(1, 10)])
def allow(puzzle,i):
exclude = set(x if i//9 == j//9 or i%9 == j%9
or i//27 == j//27 and (i%9)//3 == (j%9)//3
else '0' for j,x in enumerate(puzzle))
return options-exclude
def solve(puzzle):
zeros = [i for i,x in enumerate(puzzle) if x == '0']
if not zeros:
print puzzle
else:
i,R = min(((j,allow(puzzle,j)) for j in zeros),
key=lambda x: len(x[1]))
for option in R:
solve(puzzle[:i] + option + puzzle[i+1:])
P.
Boris Borcic
>> http://norvig.com/sudoku.html
(...)
> Below is the "winner" of my hacking for an as fast as
> possible 110% pure python (no imports at all!) comprehensive sudoku
> solver under 50 LOCs, back in 2006. Performance is comparable to the
> solver you advertize - numbers are slightly better, but platform
> differences could easily absorb that -
More precise comparisons, after noting that on Norvig's pages there were
contradictory performance numbers (obviously some 0 inserted or deleted).
Running on my machine on the "top95" list of hard problems given on Norvig's
page, my code takes about 7.5 ms/problem while Norvig's takes 42 ms/problem.
So that's a 82% reduction of running time.
Psyco.full() reduces the running time of my code to just about 4 ms/problem
while it grows Norvig's to 47 ms/problem.
BB
> eg (not counting module
> initialization and not using psyco) it takes 9.3 ms average on the "AI
> escargot" problem linked to in Norvig's page, 5.6 ms/problem on some