sudoku solver in Python ...

[Boris Borcic]

Shawn Milochik wrote:
> On Jan 23, 2008, at 10:02 PM, Derek Marshall wrote:
> 
>> 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

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)