I was preparing myself for an interview at a well known .com firm. One of the question that they often ask is an algorithm to solve sudokus (that have one solution). Here is what came to my mind. Any hints criticisms or suggestions to tune it up?
import itertools sudoku_str="""003020600 900305001 001806400 008102900 700000008 006708200 002609500 800203009 005010300""" sudoku=[[int(i) for i in j] for j in sudoku_str.splitlines()] while not any([0 in line for line in sudoku]): for x,y in itertools.ifilter(lambda x: sudoku[x][x]==False, itertools.product(*[range(9)]*2)): #Find the elements in the line line=set([i for i in sudoku[y] if i]) #Find the elements in the column column=set([xline[x] for xline in sudoku if xline[x]]) #Create some shifts to get the start (x,y) position for the area computation e.g. for 1,1 => 0,0 and for 3,8=>1,3 shifts=dict(zip(range(9),*3+*3+*3)) #Find the elements in the area area=filter(None,reduce(lambda x,y: x.add(y), sudoku[shifts[y]:shifts[y]+3], set())) #What could be in that position? outcomes=set(range(1,10))-line-column-area if len(outcomes)==1: #One outcome? replace the zero sudoku[y][x]=outcomes.pop() print "\n".join([" | ".join(str(k) for k in i) for i in sudoku])