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:

• Brute-force guessing is uninspiring. Furthermore, the data structures don't really pave the way to more clever analysis techniques.

• 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.

• If there are multiple solutions, the code would enumerate each solution multiple times; the .solutions() method deliberately de-duplicates results. That's wasteful.

• 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__(sel

-
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: () 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: () 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.

-
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

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

-
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)

-
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)

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

list(placements)[0]

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().)

-
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:
        solutions.add(r)
        yield solution

-
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.

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

```
self.symbols = symbols or set(range(1, 1 + int(sqrt(l

StackExchange Code Review Q#37343, answer score: 7