Sudoku solving algorithm - Revision needed 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[1]][x[0]]==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 =&gt; 0,0 and for 3,8=&gt;1,3
        shifts=dict(zip(range(9),[0]*3+[3]*3+[6]*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])
This is far too complicated:

for x,y in itertools.ifilter(lambda x: sudoku[x[1]][x[0]]==False, itertools.product(*[range(9)]*2)):


It is equivalent to this:

[(x, y) for x in range(9) for y in range(9) if not sudoku[y][x]]


More generally, this code feels like it is trying too hard to be clever at the expense of both clarity and potentially accuracy.

Edit:

To answer the question of speed posed by the op:

$ python -m timeit 'sudoku_str="""003020600900305001001806400008102900700000008006708200002609500800203009005010300""";sudoku = [[int(i) for i in sudoku_str[j:j+9]] for j in range(0, 81, 9)];b = [(x, y) for x in range(9) for y in range(9) if not sudoku[y][x]];'
10000 loops, best of 3: 68.1 usec per loop

$ python -m timeit 'import itertools; sudoku_str="""003020600900305001001806400008102900700000008006708200002609500800203009005010300""";sudoku = [[int(i) for i in sudoku_str[j:j+9]] for j in range(0, 81, 9)];a =[(x, y) for x, y in itertools.ifilter(lambda x: sudoku[x[1]][x[0]]==False, itertools.product(*[range(9)]*2))];'
10000 loops, best of 3: 91.9 usec per loop


A simple list comprehension is both clearer and faster.

Here's another example of unnecessary cleverness:

&gt;&gt;&gt; shifts=dict(zip(range(9),[0]*3+[3]*3+[6]*3))
&gt;&gt;&gt; shifts
{0: 0, 1: 0, 2: 0, 3: 3, 4: 3, 5: 3, 6: 6, 7: 6, 8: 6}
&gt;&gt;&gt; clear_shifts = {x:(x/3)*3 for x in range(9)}
&gt;&gt;&gt; clear_shifts
{0: 0, 1: 0, 2: 0, 3: 3, 4: 3, 5: 3, 6: 6, 7: 6, 8: 6}