Shawn said:
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)