Sudoku solving algorithm - Revision needed

Question

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 => 0,0 and for 3,8=>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])

Answer 1

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:

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

Answer 2

The biggest problem with the algorithm that I can see, is that it doesn't solve all possible solvable sudoku puzzles, instead (possibly) solving only those that can be filled without guesses, i.e. without backtracking. You can consult wikipedia article on sudoku algorithms for more information.

The biggest problem your .com employer will see with your approach, is the point-free compact style of writing your program. When you show off your ability, don't pretend that knowing compact python syntax is better than being able to clearly express your ideas and consequently be a better team player. Strive for abstracts like self-documenting code, descriptive variable names and simplicity.

Answer 3

I have to say I am really impressed (not being a Python programmer) by what can be written in Python. However, it doesn't solve all sudokus, even worse, it cycles infinitely on the "wrong" ones. These may even be solvable w/o guessing, there exist other rules that you can follow when solving sudoku (for one thing, if you have eg. in a line a triple of places, which only have (together) three candidate numbers to them, these numbers cannot occur in other than these three).

BTW why don't you use something like int((x-1)/3)*3 instead of your shifts array?

Answer 4

you can try the tree and recursive based approach! In that you use the typical recursive down algorithm and cut off if not possible (pruning). For yours, you could throw in some heuristics also, i suggest google with that regard.