>> 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) > -- http://mail.python.org/mailman/listinfo/python-list
