Sudoku using 'exact cover' solver

1. Introduction

This is a solution to Weekend Challenge #3: a Sudoku solver in Python. It works by translating a Sudoku puzzle into an exact cover problem, and then solving the exact cover problem using Donald Knuth's "Algorithm X". The code should be self-explanatory (assuming you've read and understood the Knuth paper), so I won't say more than that.

All comments welcome.

1. exactcover.py

```
from collections import Iterator, defaultdict
from random import shuffle

class ExactCover(Iterator):
"""An iterator that yields solutions to an EXACT COVER problem.

An EXACT COVER problem consists of a set of "choices". Each choice
satisfies one or more "constraints". Choices and constraints may
be represented by any hashable Python objects, with the proviso
that all choices must be distinct, as must all constraints.

A solution is a list of choices such that each constraint is
satisfied by exactly one of the choices in the solution.

The constructor takes three arguments:

constraints A map from each choice to an iterable of constraints
satisfied by that choice.
initial An iterable of choices that must appear in every
solution. (Default: no choices.)
random Generate solutions in random order? (Default: False.)

For example:

>>> next(ExactCover(dict(A = [1, 4, 7],
... B = [1, 4],
... C = [4, 5, 7],
... D = [3, 5, 6],
... E = [2, 3, 6, 7],
... F = [2, 7])))
['B', 'D', 'F']

"""
# This implements Donald Knuth's "Algorithm X"
# http://lanl.arxiv.org/pdf/cs/0011047.pdf

def __init__(self, constraints, initial=(), random=False):
self.random = random
self.constraints = constraints

# A map from constraint to the set of choices that satisfy
# that constraint.
self.choice

I have only a minor comment:

In ExactCover.__init__, I would use iteritems rather than iterating over the keys of constraints:

for choice, constraintsList in self.constraints.iteritems():
    for constraint in constraintsList:
        self.choices[choice].add(constraint)

You have written good code, factored into nice, small functions with clear purpose. Well done!

StackExchange Code Review Q#37415, answer score: 5