sudoku solver in Python ...

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