Sudoku solver using simple deductions and brute-force guessing

Question

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[0])))))
        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)[0]

    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):
                            placements.discard(c)
                    if not placements:
                        raise InconsistentBoardException(r, c)
                    elif 1 == len(placements):
                        yield (r, list(placements)[0]), v

            # Hidden single in col
            for c in range(len(self.array[0])):
                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):
                            placements.discard(r)
                    if not placements:
                        raise InconsistentBoardException(r, c)
                    elif 1 == len(placements):
                        yield (list(placements)[0], 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)

Answer 1

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

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:
           solutions.add(r)
           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[0])))))
   

   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
    

Answer 2

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[9] cells
    Set possibles    // may be able to achieve some shortcuts by tracking here too

Board:
    Cell[9][9] cells
    Group[9] 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.