Diez B. Roggisch wrote: > As everyone posts his, I'll do the same :) It uses some constraint based > solving techniques - but not too complicated ones. When stuck, it > backtracks. So far it never failed me, but I haven't tested it too > thouroughly.
Thanks to all for sharing. I like to program sudoku and review such code. So below here is my current file, I think it uses some techniques not yet posted here. It also has a difficult 16x16 puzzle which I know to be solvable (barring typing mistakes) but which my file can't solve before I get tired of waiting, this might draw some heavyweights in the ring :-) I have also read the sudoku wiki page: http://en.wikipedia.org/wiki/Sudoku which was very helpfull and interesting (especially the link to Knuths paper about dancing links was nice, even though I think (but maybe wrongly so) that we don't need dancing links now that we've got sets, but it's still a very very interesting paper) I think the first important step is to realize that some variations have fewer values so that it is possible to reduce the search space early. Currently I'm exploring ideas about contigengies as explained in the wiki above which seems promising, but I haven't found a nice way to implement them yet. Maybe an easy optimization would be to find values that don't come up often and choose variations containing those. And maybe I should switch to an approach that has possibility values inside the cells instead of computing them on the fly each time, that could make contigency elimination easier. Anton from __future__ import generators from sets import Set as set problem1 = ['063000700','000690008','900007002', '002010080','050806090','090070200', '600100003','700045000','009000140'] problem2 = ['030009007','010080000','000100090', '004905006','020000010','500607400', '050001000','000040020','700500030'] problem3 = ['030500810','000760090','400000000', '043905006','010000070','600801930', '000000009','090086000','061002080'] problem4 = ['004530080','060009000','900000005', '000800350','000000000','027006000', '800000007','000300040','090072600'] X =[' 1 0 0 0 0 12 0 10 11 7 6 0 0 4 0 0', ' 0 7 0 0 15 13 0 0 0 0 2 0 0 8 0 0', ' 3 0 0 0 4 0 0 0 0 5 0 12 0 16 0 0', ' 0 0 14 2 0 9 0 0 0 0 1 0 0 0 0 0', '10 15 0 1 0 0 0 2 0 16 0 0 3 0 0 0', '12 0 0 3 0 0 15 0 0 13 0 4 0 1 9 5', ' 5 0 11 0 7 0 8 0 0 0 0 0 0 15 0 0', ' 7 13 0 16 0 0 0 6 0 0 0 14 0 10 0 0', ' 0 0 13 0 11 0 0 0 10 0 0 0 1 0 12 0', ' 0 0 7 0 0 0 0 0 0 3 0 16 0 14 0 13', '16 8 0 0 14 0 5 0 0 15 0 0 4 0 0 6', ' 0 0 0 9 0 0 4 0 1 0 0 0 2 0 0 7', ' 0 0 0 0 0 16 0 0 0 0 8 0 10 5 0 0', ' 0 0 4 0 12 0 6 0 0 0 16 7 0 0 0 14', ' 0 0 6 0 0 1 0 0 0 0 12 13 0 0 11 0', ' 0 0 15 0 0 8 11 3 2 0 9 0 0 0 0 1'] problem5 = [row.split() for row in X] class State: def __init__(self,solved,unsolved): self.solved = solved self.unsolved = unsolved self.size = int((len(solved)+len(unsolved))**.25) def choiceset(self,x,y): "the set of possible choices for an empty cell" sz = self.size res = set(range(1,sz*sz+1)) r,c = x/sz*sz,y/sz*sz for (i,j),v in self.solved.iteritems(): if x == i or y == j or (r<=i<r+sz and c<=j<c+sz): res.discard(v) return res def celldict(self): """dictionary of (cellcoords,choiceset) for each empty cell if *any* empty cell cannot be filled return an empty dict to signal an illegal position """ res = {} for x,y in self.unsolved: c = self.choiceset(x,y) if not c: return {} res[x,y] = c return res class Node: def __init__(self,state): self.state = state self.issolved = not bool(state.unsolved) def children(self): state = self.state cd = state.celldict() if cd: #position is still legal ml = min([len(x) for x in cd.itervalues()]) #select empty cells which have the minimum number of choices items = [(k,v) for k,v in cd.iteritems() if len(v) == ml] (x,y),S = min(items) #arbitrary choice of cell here for v in S: solved,unsolved = dict(state.solved),dict(state.unsolved) solved[x,y] = v del unsolved[x,y] yield Node(State(solved,unsolved)) def __repr__(self): R = range(self.state.size**2) res = [["__" for i in R] for j in R]+[''] for (i,j),v in self.state.solved.iteritems(): res[i][j] = "%02i" %v return '\n'.join(map(' '.join,res)) def solutions(N): if N.issolved: yield N else: for child in N.children(): for g in solutions(child): yield g def todicts(P): M = [map(int,row) for row in P] solved = {} unsolved = {} for i,row in enumerate(M): for j,x in enumerate(row): if x: solved[i,j] = x else: unsolved[i,j] = x return solved,unsolved def test(): solved,unsolved = todicts(problem4) N = Node(State(solved,unsolved)) print N for S in solutions(N): print S if __name__=='__main__': test() -- http://mail.python.org/mailman/listinfo/python-list
