""" This code is placed in the public domain. The author can be reached at anton.vredegoor@gmail.com Last edit: Anton Vredegoor, 22-02-2006 A sudoku problem is represented by a binary cube, the x and y coordinates are the rows and columns of the original sudoku, the z-coordinate is the value (the "height") of a point in the sudoku grid. We wipe away points until there are n**4 (81 if we start with parameter n=3) binary points left in the cube, which do not share points in the same x,y,or z "sight line" or nxn,z block. The sudoku17 file that is read from is a list of sudoku problems with 17 givens and can be found at: http://www.csse.uwa.edu.au/~gordon/sudokumin.php Thanks Gordon, for making this list available. In each line there are 81 digits in range(10) and a linefeed. Here is the first line (0 means "unknown"): 000000010400000000020000000\ 000050407008000300001090000\ 300400200050100000000806000 I used vpython while developing the code in order to visualize what was going on in the cube (some simple differently colored spheres in 3d space helped a lot), but the final script doesn't need it. Still, I am awed by vpythons 3D stereo mode which the "crosseyed" visualization trick. Keep up the good work. Uncomment this line in function "test" to see the sudoku grid output: for sol in sols: print sol """ n = 3 n2 = n*n n4 = n2*n2 B = range(n) R = range(n2) class Node: def __init__(self,possibles): S = self.possibles = possibles #set of possible points (3-tuples) all = self.all = self.clean() #list of all *lists* of points valid = self.isvalid = len(S)>=n4 and len(all)==n4*4 self.issolved = valid and len(S)==n4 and max(map(len,all))==1 def clean(self): #eliminate points until stable S = self.possibles while True: L = {},{},{},{} for x,y,z in S: r,c = x//n,y//n for Q,T in zip(L,((x,y),(x,z),(y,z),(r,c,z))): Q[T] = Q.get(T,[]) +[(x,y,z)] all = [] for Q in L: all.extend(Q.values()) ns = len(S) for x in all: if len(x) == 1: S -= friends(x[0]) if ns == len(S): break return all def children(self): if self.isvalid and not self.issolved: #heuristic: choose shortest list of points pts = min((len(x),x) for x in self.all if len(x)>1)[1] for p in pts: yield Node(self.possibles-friends(p)) def __repr__(self): S = self.possibles M = [['_' for i in R] for j in R] for i,j,k in S: if not S&friends((i,j,k)): M[i][j] = str(k+1) return '\n'+'\n'.join(map(''.join,M)) def friends(point, memo = {}): #points in the same sight line or nxnxz block try: return memo[point] except KeyError: x,y,z = point res = set() for i in R: res.update([(i,y,z),(x,i,z),(x,y,i)]) a,b = x//n*n,y//n*n res |= set((a+i,b+j,z) for i in B for j in B) res.discard((x,y,z)) memo[point] = res return res def solutions(N): #depth first search if N.issolved: yield N else: for child in N.children(): for g in solutions(child): yield g def readstring(s): Z = zip([(i,j) for i in R for j in R],map(int,s)) givens = set((i,j,k-1) for (i,j),k in Z if k) possibles = set((i,j,k) for i in R for j in R for k in R) for p in givens: possibles -= friends(p) return possibles def test(): for i,line in enumerate(file('sudoku17')): N = Node(readstring(line.strip())) sols = list(solutions(N)) if i%10==0: print print i, #for sol in sols: print sol if len(sols) > 1: print 'more than one solution' break if __name__=='__main__': test()