# 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 => 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
#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:

>>> 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}
• Definitely cleaner. Would abandoning itertools comport any noticeable decrease in the speed? – luke14free Apr 7 '12 at 21:47
• @luke14free abandoning itertools would significantly increase the speed: see my edit. – Nolen Royalty Apr 7 '12 at 22:02
• Yes, this should be because of the lambda function. If you use ifilterfalse and put "None" instead of the lambda block itertools are about 10usec faster than simple lists. 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.ifilterfalse(None, itertools.product(*[range(9)]*2))];' – luke14free Apr 7 '12 at 22:09
• Great answer anyhow. I love criticisms. Anyhow set([i for i in sudoku[y] if i]) is used because: a) I need a set for the "set subtraction". b) I cannot accept zeros. - I don't see the reason of your struggling on it. – luke14free Apr 7 '12 at 22:17

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.

• Yes my mission for today was to solve only the 1-solutions sudoku. Ok I see your point; clean is better than complex. Even though I didn't want to show off but to speed up and use less memory with itertools that create generators. Am I wrong? – luke14free Apr 7 '12 at 21:49
• if by 1-solutions sudoku you mean sodoku with unique solution, then you often still need to backtrack to find that solution. If you mean something else, then that meaning was not clear. As for the memory argument, I'm not sure. However, there are very few corner cases where you'd want to optimize your code in a python interview. It would probably make much more sense to write this code in C, if memory was a concern. – Gleno Apr 7 '12 at 22:20
• Ok, therefore I'm finding out that the algo is wrong basically. I'll have to find out a schema requiring backtracking to exercise. Thanks a lot for pointing that out! – luke14free Apr 7 '12 at 22:31

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?

• yes, in fact I explicitly said "sudokus (that have one solution)". Good point for the shift, a part from the fact that they are re-generated at every loop (they should be outside the main loop). Anyhow you don't even need to call int as the default division is the integer one (weird behavior changed from python 3k). – luke14free Apr 7 '12 at 22:04

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.