Sudoku solver using simple deductions and brute-force guessing

Here's my attempt at Weekend Challenge #3.

Key characteristics of this Python entry are:

• The strategy is to alternate between "auto-complete" (making simple deductions such as naked singles and hidden singles) and recursive guessing.
• The puzzle state is stored in a Sudoku object, which has a mutable 2D array. Unknowns are represented as None.
• When .solutions() finds a solution, it yields a copy of the Sudoku object. That is the only time the object and its 2D array is copied; most of the time it mutates the array entries directly, using a Transaction to help roll back to the previous state after each guess.

Concerns include:

1. Brute-force guessing is uninspiring. Furthermore, the data structures don't really pave the way to more clever analysis techniques.
2. I feel like I should be able to accomplish this task with less code. In particular, code to handle rows and code to handle columns are repetitive.
3. If there are multiple solutions, the code would enumerate each solution multiple times; the .solutions() method deliberately de-duplicates results. That's wasteful.
4. Both the main .solutions() method and its helper .guess_from() call .autocomplete(). The code there could probably be less redundant.

The code works in Python 2.7. It breaks in Python 3, apparently due to PEP 3113 — Removal of Tuple Parameter Unpacking. Suggestions for rectifying that would be appreciated.

Anyway, the more I try to prettify the code, the slower it gets, so it's time for me to stop working on it, and let Code Review have a shot at it.

Some preliminaries: imports, an exception class, and the Transaction class…

from collections import Set
from copy import deepcopy
from itertools import chain
from math import sqrt

class InconsistentBoardException(Exception):
def __init__(self, r=None, c=None):
self.r, self.c = r, c

######################################################################

class Transaction:
def __init__(self, sudoku):
self.sudoku = sudoku

def __enter__(self):
return self.commit()

def __exit__(self, type, value, traceback):
return self.rollback()

def commit(self):
self._count = len(self.sudoku.undo_list)
return self

def rollback(self):
self.sudoku.undo(self._count)
return self

def move_count(self):
return len(self.sudoku.undo_list) - self._count

def __nonzero__(self):
return self.move_count()

The main code:

class Sudoku:
@classmethod
def parse(cls, string, box_h=None, box_w=None, symbols=None):
return Sudoku([[None if v == '.' else int(v) for v in line]
for line in filter(None, string.split('\n'))],
box_h, box_w, symbols)

def __init__(self, array, box_h=None, box_w=None, symbols=None):
self.array = array
self.symbols = symbols or set(range(1, 1 + int(sqrt(len(array) * len(array)))))
self.box_h = box_h or int(sqrt(len(self.symbols)))
self.box_w = box_w or int(sqrt(len(self.symbols)))
self.undo_list = []

def dup(self):
return Sudoku(deepcopy(self.array), self.box_h, self.box_w, self.symbols)

def __repr__(self):
return '\n'.join(
''.join(
str(n) if n is not None else '.' for n in row
) for row in self.array
)

def __eq__(self, other):
return self.array == other.array and \
self.symbols == other.symbols and \
self.box_h == other.box_h and \
self.box_w == other.box_w

def __hash__(self):
return sum(map(lambda row: sum([v or 0 for v in row]), self.array)) ^ \
sum(self.symbols) ^ self.box_h ^ self.box_w

def is_solved(self):
"""
Checks whether all cells are filled in (without checking for
consistency).
"""
return all(all(row) for row in self.array)

def row_cell_iter(self, r):
for c in range(len(self.array[r])):
yield (r, c)

def col_cell_iter(self, c):
for r in range(len(self.array)):
yield (r, c)

def box_cell_iter(self, r, c):
box_row_lb = r // self.box_h * self.box_h
box_row_ub = box_row_lb + self.box_h
box_col_lb = c // self.box_w * self.box_w
box_col_ub = box_col_lb + self.box_w
for r in range(box_row_lb, box_row_ub):
for c in range(box_col_lb, box_col_ub):
yield (r, c)

def _to_set(self, cells, r=None, c=None):
a = filter(None, [self.array[r][c] for r, c in cells])
s = set(a)
if len(a) != len(s):
raise InconsistentBoardException(r, c)
return s

def row_excl(self, r):
"""
Returns the set of impossible symbols for row r due to
repetition with other cells in row r.
"""
return self._to_set(self.row_cell_iter(r), r, None)

def col_excl(self, c):
"""
Returns the set of impossible symbols for column c due to
repetition with other cells in column c.
"""
return self._to_set(self.col_cell_iter(c), None, c)

def box_excl(self, r, c):
"""
Returns the set of impossible symbols for cell (r, c) due to
repetition with other cells in the box that contains (r, c).
"""
return self._to_set(self.box_cell_iter(r, c), r, c)

def candidates(self, r, c):
"""
Returns the set of symbols possible for cell (r, c) after eliminating
the values that appear in the same row, column, or box.
"""
return self.symbols - self.row_excl(r) \
- self.col_excl(c) \
- self.box_excl(r, c)

def set(self, r, c, value):
self.array[r][c] = value
self.undo_list.append((r, c))

def undo(self, n=-1):
"""
If n < 0, undo the last abs(n) moves.  If n >= 0, undo all but the
first n moves.
"""
for r, c in self.undo_list[n:]:
self.array[r][c] = None
self.undo_list[n:] = []

def solutions(self):
with Transaction(self):
self.autocomplete()
if self.is_solved():
yield self.dup()
return
solutions = {}              # Deduplicate solutions
for solution in self.guess_from(0, 0):
if not solution in solutions:
solutions[solution] = True
yield solution

def naked_singles(self):
"""
Enumerates all naked singles in the board.  A naked single is an empty
cell whose candidate values have been reduced to just one possibility
by their row, column, or box neighbors.
"""
for r in range(len(self.array)):
for c in range(len(self.array[r])):
if self.array[r][c] is None:
candidates = self.candidates(r, c)
if not candidates:
raise InconsistentBoardException(r, c)
if 1 == len(candidates):
yield (r, c), list(candidates)

def hidden_singles(self):
"""
Enumerates hidden singles in the board.  A hidden single is an empty
cell that must be filled in with a symbol because that symbol has
nowhere else to go in that row or column.  (It's also possible to
detect hidden singles for boxes, but the time to accomplish that is
worse than guessing.)
"""
for v in self.symbols:
# Hidden single in row
for r in range(len(self.array)):
row = self.array[r]
if not v in row:
placements = set(filter(lambda c: row[c] is None, range(len(row))))
for c in set(placements):
if not v in self.candidates(r, c):
if not placements:
raise InconsistentBoardException(r, c)
elif 1 == len(placements):
yield (r, list(placements)), v

# Hidden single in col
for c in range(len(self.array)):
col = [self.array[r][c] for r in range(len(self.array))]
if not v in col:
placements = set(filter(lambda r: col[r] is None, range(len(col))))
for r in set(placements):
if not v in self.candidates(r, c):
if not placements:
raise InconsistentBoardException(r, c)
elif 1 == len(placements):
yield (list(placements), c), v

def autocomplete(self):
"""
Fills in all naked singles and hidden singles.
"""
with Transaction(self) as transaction:
changed = True
while changed:
changed = False
for (r, c), value in chain(self.naked_singles(),
self.hidden_singles()):
self.set(r, c, value)
changed = True

self.trace_autocomplete(transaction)
transaction.commit()

def guess_from(self, init_r, init_c):
"""
At the next empty cell after (init_r, init_c), pick any of its
candidate values.  Explore the resulting possibilities by running
autocomplete, then recursively guessing again starting from the next
empty cell.  If it doesn't work out, roll back the transaction.
"""
for r in range(init_r, len(self.array)):
for c in range(init_c, len(self.array[r])):
if self.array[r][c] is None:
candidates = self.candidates(r, c)
if not candidates:
self.trace_inconsistent(r, c)
return              # No solution possible
for v in candidates:
with Transaction(self):
try:
self.set(r, c, v)
self.trace_guess(r, c, candidates)
with Transaction(self):
self.autocomplete()
if self.is_solved():
yield self.dup()
for solution in self.guess_from(r, c + 1):
yield solution
except InconsistentBoardException:
pass
finally:
self.untrace_guess()
pass
init_c = 0

There's some debugging code within the Sudoku class. Consider this to be throw-away code, not worthy of review. I'm including it just in case you find it helpful to see the inner workings. Uncomment the print in .trace() to enable debugging output.

def trace(self, message):
#print(message)
pass

level = 0
def trace_guess(self, r, c, candidates):
self.level += 1
indent = ' ' * (2 * self.level)
self.trace("%sGuessing (%d, %d) = %s (candidates %s)" % (indent, r, c, self.array[r][c], candidates))
self.trace('\n'.join(map(lambda line: indent + line, str(self).split('\n'))))

def trace_inconsistent(self, r, c):
self.trace("%sINCONSISTENT: No candidates for (%d, %d)!" % (' ' * (2 * self.level), r, c))
pass

def trace_autocomplete(self, transaction):
indent = ' ' * (2 * self.level)
if not transaction:
self.trace("%sAutocompleted 0 moves" % (indent))
return
moves = transaction.move_count()
autocompletes = self.undo_list[-moves:]
self.trace("%sAutocompleted %d moves: %s" % (indent, moves, ', '.join(map(str, autocompletes))))
after = str(self)
redo_values = map(lambda r, c: self.array[r][c], autocompletes)
for r, c in autocompletes:
self.array[r][c] = None
before = str(self)
for (r, c), value in zip(autocompletes, redo_values):
self.array[r][c] = value
if str(self) != after:
raise "Trace error"
self.trace('\n'.join(map(lambda before_line, after_line: indent + before_line + "      " + after_line, zip(before.split('\n'), after.split('\n')))))

def untrace_guess(self):
self.level -= 1

Test cases:

four = Sudoku.parse("""
2...
.13.
3..1
.24.
""")

four_inconsistent = Sudoku.parse("""
22..
....
....
....
""")
four_2 = Sudoku.parse("""
22..
....
....
....
""")
six_easy = Sudoku.parse("""
3....4
..43..
.3..6.
.4..1.
..21..
1....2
""", 2, 3)

six_hard = Sudoku.parse("""
....2.
2.3..1
.5....
.3.1.5
.2..3.
.4....
""", 2, 3)

nine_easy = Sudoku.parse("""
.931.564.
7.......5
5.12.9387
2.......3
.369.752.
9.......1
3.24.81.9
6.......4
.473.285.
""")

nine_hard = Sudoku.parse("""
.5...6...
2...7...1
.19....8.
.9.6..8..
..2...6..
..3..9.7.
.3....71.
9...2...3
...4...6.
""")

nine_inconsistent = Sudoku.parse("""
..624..3.
.3.....9.
2......7.
5..6...2.
..1...6..
.2...3..7
.5......3
.9.....8.
.1..625..
""")

for puzzle in [four, four_inconsistent, six_easy, six_hard, nine_easy, nine_hard, nine_inconsistent]:
print(puzzle)
try:
for solution in puzzle.solutions():
print("\nSolution:\n%s" % (solution))
except InconsistentBoardException:
print("\nNo solution possible!")
print('-' * 72)

1. It doesn't work! First problem:

>>> list(Sudoku.parse(puzzle).solutions())
Traceback (most recent call last):
...
File "cr37343.py", line 278, in trace_autocomplete
redo_values = map(lambda r, c: self.array[r][c], autocompletes)
TypeError: <lambda>() takes exactly 2 arguments (1 given)

So I changed this line to:

redo_values = [self.array[r][c] for r, c in autocompletes]

Second problem:

Traceback (most recent call last):
...
File "cr37343.py", line 286, in trace_autocomplete
self.trace('\n'.join(map(lambda before_line, after_line: indent + before_line + "      " + after_line, zip(before.split('\n'), after.split('\n')))))
TypeError: <lambda>() takes exactly 2 arguments (1 given)

So I changed this line to:

self.trace('\n'.join(indent + b + "      " + a for b, a in zip(before.split('\n'), after.split('\n'))))

And then it worked.

2. The code is not portable to Python 3, but the reason is nothing to do with PEP 3113. The problem is here, in Sudoku._to_set:

a = filter(None, [self.array[r][c] for r, c in cells])
s = set(a)
if len(a) != len(s):

In Python 3, filter returns an iterator rather than a list, and this causes len(a) to raise TypeError. The problem with filter is easily fixed:

a = list(filter(None, (self.array[r][c] for r, c in cells)))

but why didn't you see the TypeError? That's because it was suppressed by your Transaction class. Transaction.__exit__ always returns self. In Python 2 this gets converted to a bool via the __nonzero__ method. But Python 3 doesn't support the __nonzero__ method (the Python 3 equivalent is __bool__), so self is always True, and so all exceptions are suppressed.

The way to fix this portably would be to use __len__ instead of __nonzero__. But can it really be right for you to suppress exceptions? Surely what you want is something like this:

def __exit__(self, exc_type, exc_val, exc_tb):
if exc_type is None:
self.rollback()
return False

3. There's no documentation for the Transaction and Sudoku classes. How am I supposed to use these classes?

4. To expand on point #1, code of the form:

map(lambda args: expression, iterable)

is nearly always better written as a list comprehension:

[expression for args in iterable]

(if you really do want to allocate a list) or as a generator expression:

(expression for args in iterable)

(if you don't). By getting rid of the lambda you avoid a function call for each item, and function calls are moderately costly in Python.

In particular:

sum(map(lambda row: sum([v or 0 for v in row]), self.array))

could be rewritten like this:

sum(sum(v or 0 for v in row) for row in self.array)

5. Similarly for filter(lambda: ...). Code of the pattern:

filter(lambda args: expression, iterable)

can be written:

(args for args in iterable if expression)

This avoids a function call for each item. In particular, your code:

placements = set(filter(lambda c: row[c] is None, range(len(row))))

can be written:

placements = set(i for i, cell in enumerate(row) if cell is None)

6. When you want to return the only item of the set placements, you write:

list(placements)

but it would be better to write:

next(iter(placements))

as this avoids having to convert the whole set to a list. (If you don't care about modifying the set, you can write placements.pop().)

7. The __hash__ method does not seem very robust: since you just add up the numbers in the array, then any permutation of the array yields the same hash!

But hang on a second, why are you writing a hash function at all? If you read the documentation for the __hash__ method, you'll see that it says:

If a class defines mutable objects and implements a __cmp__() or __eq__() method, it should not implement __hash__(), since hashable collection implementations require that a object’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket).

Your Sudoku objects are mutable: they can be changed by the set and undo methods. This makes them unsuitable for storing in sets or using as dictionary keys.

So if they mustn't be hashed, how do you deduplicate solutions? Well, you could use their printed representation instead:

solutions = set()              # Deduplicate solutions
for solution in self.guess_from(0, 0):
r = repr(solution)
if r not in solutions:
yield solution

8. Transaction and Sudoku are old-style classes. Old-style classes don't support the super built-in, and that means that you can't straightforwardly use multiple inheritance. It is nearly always be better to write:

class Transaction(object):

to ensure that you get a new-style class.

9. In Sudoku.__init__, this line seems strange to me:

self.symbols = symbols or set(range(1, 1 + int(sqrt(len(array) * len(array)))))

as it suggests the possibility that the width and height of the array might be different. But Sudoku puzzles must be square, so surely this can't happen?

Similarly, it seems wrong for the box width and height to have the same default values:

self.box_h = box_h or int(sqrt(len(self.symbols)))
self.box_w = box_w or int(sqrt(len(self.symbols)))

Surely having chosen the height, the width is then determined? I think it would be better to write something like this:

n = len(array)
self.symbols = symbols or set(range(1, n))
self.box_h = box_h or int(sqrt(n))
self.box_w = box_w or n // self.box_h
assert(self.box_h * self.box_w == n)

10. Your solver is very slow when it has to make a lot of guesses. For example, this puzzle takes more than a minute to solve on my computer:

>>> from timeit import timeit
>>> puzzle = '''....79...
...             7.4.1....
...             .6.2....9
...             4.3..75..
...             2.......4
...             ..64..8.3
...             6....3.9.
...             ....6.4.2
...             ...79....'''
>>> timeit(lambda:next(Sudoku.parse(puzzle).solutions()), number=1)
66.50877224095166

And this one takes even longer, but I didn't have the patience to wait for it to complete:

>>> puzzle = '''8........
...             ..36.....
...             .7..9.2..
...             .5...7...
...             ....457..
...             ...1...3.
...             ..1....68
...             ..85...1.
...             .9....4..'''
>>> timeit(lambda:next(Sudoku.parse(puzzle).solutions()), number=1)
^C

Looping over the rows and columns in naked_singles and hidden_singles is costing a lot of time. You can achieve those effects more efficiently by tracking the possible values available to each cell, row, column, and box. The last three can be modeled using a Group collection class that knows the cells it contains while each cell knows which groups it belongs to.

Cell:
Group row, col, box    // probably don't even need to name the three groups
Set possibles
int known

Group:
Cell cells
Set possibles    // may be able to achieve some shortcuts by tracking here too

Board:
Cell cells
Group rows, cols, boxes    // same here

While this will require more code, it will be pretty straight-forward and allow you to make moves without iterating over the same possible numbers again and again.

• When you place a number N in a cell C (e.g. when initializing the board from input), N from the set of possibles of all other cells belonging to the row, column, and box containing C.
• When a set of possibles for a cell C is reduced to a single number N, set that cell to N as above.

The next step which I didn't implement in my Scala version is to model the intersections between every pair of groups. For example, imagine the only known numbers are 1 through 6 on the first row starting from the left.

1 2 3 4 5 6 x x x
. . . . . . y y y
. . . . . . z z z

Obviously, the three x cells at the end of that row must contain 7, 8 and 9 in some order. This allows you to eliminate them from the y and z mini-groups. I haven't thought through yet how you'd make use of this, but it may enable more complex rules.

• I agree, maintaining a persistent set of candidates for each cell would help efficiency. However, when the algorithm relies heavily on guesswork, the bookkeeping might be rather intense. I'd either have to put more effort into supporting rollbacks when guesses fail, or copy all the data structures defensively before each guess. Or maybe just reconstruct the candidate sets when backtracking. What would you do? – 200_success Dec 14 '13 at 11:10
• For guessing I made a copy of the board state. Since you pick a cell and then iterate over all possibles, you only need to make one copy per cell. While it would be more work to implement full transaction support, it would also be an interesting challenge. A couple implementations of the Command pattern should be sufficient: RemovePossible(cells, value) and SetKnown(cell, value). The tricky part is probably dealing with the cascade effect of setting values and removing possibles. – David Harkness Dec 14 '13 at 18:59