sudoku solver in Python ...

[Derek Marshall]

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 ...

Yours with-too-much-time-to-kill-on-the-train'ly,
Derek

 

[Shawn Milochik]

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 ...

Yours with-too-much-time-to-kill-on-the-train'ly,
Derek
--
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

 

[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/

 

[Boris Borcic]

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]

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 ...

Yours with-too-much-time-to-kill-on-the-train'ly,
Derek

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]

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]

(...)
> 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
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)