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

### 2. 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.choices = defaultdict(set)
for i in self.constraints:
for j in self.constraints[i]:

# The set of constraints which are currently unsatisfied.
self.unsatisfied = set(self.choices)

# The partial solution currently under consideration,
# implemented as a stack of choices.
self.solution = []

# Make all the initial choices.
try:
for i in initial:
self._choose(i)
self.it = self._solve()
except KeyError:
# Initial choices were contradictory, so there are no solutions.
self.it = iter(())

def __next__(self):
return next(self.it)

next = __next__             # for compatibility with Python 2

def _solve(self):
if not self.unsatisfied:
# No remaining unsatisfied constraints.
yield list(self.solution)
return

# Find the constraint with the fewest remaining choices.
best = min(self.unsatisfied, key=lambda j:len(self.choices[j]))
choices = list(self.choices[best])
if self.random:
shuffle(choices)

# Try each choice in turn and recurse.
for i in choices:
self._choose(i)
for solution in self._solve():
yield solution
self._unchoose(i)

def _choose(self, i):
"""Make choice i; mark constraints satisfied; and remove any
choices that clash with it.

"""
self.solution.append(i)
for j in self.constraints[i]:
self.unsatisfied.remove(j)
for k in self.choices[j]:
for l in self.constraints[k]:
if l != j:
self.choices[l].remove(k)

def _unchoose(self, i):
"""Unmake choice i; restore constraints and choices."""
self.solution.pop()
for j in self.constraints[i]:
for k in self.choices[j]:
for l in self.constraints[k]:
if l != j:


### 3. sudoku.py

from collections import Iterator
from copy import deepcopy
from exactcover import ExactCover
from itertools import islice, product
from math import ceil, sqrt
from random import shuffle
from string import ascii_lowercase, ascii_uppercase

DIGITS = '123456789' + ascii_uppercase + ascii_lowercase

def make_grid(n):
"""Return a Sudoku grid of size n x n."""
return [[-1] * n for _ in range(n)]

def puzzle_to_grid(puzzle):
"""Convert printed representation of a Sudoku puzzle into grid
representation (a list of lists of numbers, or -1 if unknown).

"""
puzzle = puzzle.split()
grid = make_grid(len(puzzle))
for y, row in enumerate(puzzle):
for x, d in enumerate(row):
grid[y][x] = DIGITS.find(d)
return grid

def grid_to_puzzle(grid):
"""Convert grid representation of a Sudoku puzzle (a list of lists of
numbers, or -1 if unknown) into printed representation.

"""
return '\n'.join(''.join('.' if d == -1 else DIGITS[d] for d in row)
for row in grid)

class Sudoku(Iterator):
"""An iterator that yields the solutions to a Sudoku problem.

The constructor takes three arguments:

puzzle   The puzzle to solve, in the form of a string of n
words, each word consisting of n characters, either a
digit or a dot indicating a blank square.
(Default: the blank puzzle.)
n        The size of the puzzle. (Default: 9.)
m        The width of the blocks. (Default: the square root of n,
rounded up.)
random   Generate solutions in random order? (Default: False.)

For example:

>>> print(next(Sudoku('''...84...9
...                      ..1.....5
...                      8...2146.
...                      7.8....9.
...                      .........
...                      .5....3.1
...                      .2491...7
...                      9.....5..
...                      3...84...''')))
632845179
471369285
895721463
748153692
163492758
259678341
524916837
986237514
317584926

"""
def __init__(self, puzzle=None, n=9, m=None, random=False):
if puzzle:
puzzle = puzzle.split()
self.n = n = len(puzzle)
initial = self._encode_puzzle(puzzle)
else:
self.n = n
initial = ()
if m is None:
m = int(ceil(sqrt(n)))
assert(0 < n <= len(DIGITS))
assert(n % m == 0)
def constraints(choice):
d, x, y = self._decode_choice(choice)
block = m * (x // m) + y // (n // m)
return [a + 4 * (b + n * c) for a, b, c in [
(0, x, y),     # Any digit at x, y.
(1, d, y),     # Digit d in row y.
(2, d, x),     # Digit d in column x.
(3, d, block), # Digit d in block.
]]
self.solver = ExactCover({i: constraints(i) for i in range(n ** 3)},
initial, random)

def __next__(self):
return self._decode_solution(next(self.solver))

next = __next__             # for compatibility with Python 2

def _encode_choice(self, d, x, y):
"""Encode the placement of d at (x, y) as a choice."""
n = self.n
assert(0 <= d < n and 0 <= x < n and 0 <= y < n)
return d + n * (x + n * y)

def _decode_choice(self, choice):
"""Decode a choice into a (digit, x, y) tuple."""
choice, digit = divmod(choice, self.n)
y, x = divmod(choice, self.n)
return digit, x, y

def _encode_puzzle(self, puzzle):
"""Encode a Sudoku puzzle and yield initial choices."""
for y, row in enumerate(puzzle):
for x, d in enumerate(row):
digit = DIGITS.find(d)
if digit != -1:
yield self._encode_choice(digit, x, y)

def _decode_solution(self, solution):
"""Decode a Sudoku solution and return it as a string."""
grid = make_grid(self.n)
for d, x, y in map(self._decode_choice, solution):
grid[y][x] = d
return grid_to_puzzle(grid)

class ImpossiblePuzzle(Exception): pass
class AmbiguousPuzzle(Exception): pass

def solve(puzzle, m=None):
"""Solve the Sudoku puzzle and return its unique solution. If the
puzzle is impossible, raise ImpossiblePuzzle. If the puzzle has
multiple solutions, raise AmbiguousPuzzle.

Optional argument m is the width of the blocks (default: the
square root of n, rounded up).

For example:

>>> print(solve('''.6.5..9..
...                ..4.....6
...                .29..3..8
...                ....32..4
...                ..61.75..
...                1..95....
...                6..4..27.
...                2.....4..
...                ..7..6.8.'''))
768514923
314829756
529763148
975632814
836147592
142958637
693481275
281375469
457296381
>>> print(solve('''...8.....
...                ..1.....5
...                8....1...
...                7.8....9.
...                ...1.....
...                .5....3.1
...                ....1...7
...                9.....5..
...                3........'''))
... # doctest: +IGNORE_EXCEPTION_DETAIL
Traceback (most recent call last):
...
ImpossiblePuzzle: no solutions

"""
solutions = list(islice(Sudoku(puzzle, m=m), 2))
if len(solutions) == 1:
return solutions[0]
elif len(solutions) == 0:
raise ImpossiblePuzzle('no solutions')
else:
raise AmbiguousPuzzle('two or more solutions')

def make_puzzle(n=9, m=None):
"""Return a random nxn Sudoku puzzle with 180-degree rotational
symmetry. The puzzle returned is minimal in the sense that no
symmetric pair of givens can be removed without making the puzzle
ambiguous.

The optional arguments are n, the size of the puzzle (default: 9)
and m, the width of the blocks (default: the square root of n,
rounded up).

"""
grid = puzzle_to_grid(next(Sudoku(n=n, m=m, random=True)))
coords = list(divmod(i, n) for i in range((n ** 2 + 1) // 2))
shuffle(coords)
for i, j in coords:
g = deepcopy(grid)
g[i][j] = g[n - i - 1][n - j - 1] = -1
try:
solve(grid_to_puzzle(g))
grid = g
except AmbiguousPuzzle:
pass
return grid_to_puzzle(grid)


### 4. Examples

>>> for puzzle in map(make_puzzle, (4, 6, 9, 12, 16)):
...     print('\n'.join('{}    {}'.format(*a) for a in zip(puzzle.split(), solve(puzzle).split())), '\n')
...3    1243
.4..    3412
..2.    4321
2...    2134

..2..4    632514
.1.2..    415236
3.4...    354162
...3.5    126345
..1.5.    241653
5..4..    563421

...3...4.    678325149
1.94.....    139476528
...98.3.7    452981367
.87....34    587612934
..4...7..    214893756
39....81.    396754812
7.5.69...    725169483
.....72.1    863547291
.4...8...    941238675

6A....7.8...    6ABC42758391
.952C.A...4.    3952C8A17B46
4..1....5...    47819B635C2A
83...1..96..    832471BA96C5
7......921.4    7B658C3921A4
.....6.4.7..    91CA2654B783
..A.3.2.....    B5A7342C1869
C.196......B    C4196A87325B
..38..1...7C    2638591BA47C
...3....6..2    1C73A54869B2
.8...3.2451.    A896B3C24517
...B.7....38    524B1796CA38

.F3D..A.......87    1F3D95AEC46BG287
.9B.63....5.F...    E9BC63D87G52FA14
457..G.1....9...    457ACG21FD8396BE
.8..5..G..AC....    F8D25E6G13AC497B
..6E.48.D..7.1.G    CB6E3489D5F7A12G
5.14D...G...68..    5314D27AGEB968FC
.A.7.FC.8.4.....    9AG71FCB82465ED3
..91...4...G25.F    BD918CE4367G25AF
7.A.G..3.CD.EB..    72A6G1F35CD4EB98
....76..A..E..G.    3C8576B2AF9E14GD
...8....E.3..G62    D4C8F917EA35BG62
...92.3C.....FE.    67592A3C4BGD8FE1
...B.8....CF.35.    21EB48GD69CF735A
AG.......7..CD4.    AGF3EB562718CD49


This is not quite right:

def _unchoose(self, i):
"""Unmake choice i; restore constraints and choices."""
self.solution.pop()


It promises to undo an arbitrary choice i but actually pops the latest one from self.solution. As you only use if for undoing the latest choice, I suggest to drop the parameter:

def _unchoose(self):
"""Unmake latest choice; restore constraints and choices."""
i = self.solution.pop()


Actually the choose-unchoose pattern feels a bit awkward to me. I'd prefer functional programming instead. Another idea that would make me feel more comfortable would be to create a context manager:

@contextlib.contextmanager
def _tentative_choice(self, i):
self._choose(i)
yield
self._unchoose(i)


use:

    for i in choices:
with self._tentative_choice(i):
for solution in self._solve():
yield solution


Another small concern is that you use a local variable choices in methods of a class that has an instance variable self.choices. This may lead to confusion; I'd use a different name.

• Good review! But can you explain the use of try: ... finally: in the context manager? If _solve raises an exception then something must have gone so badly wrong that I can't expect to be able to continue searching, so surely there's no need to worry about restoring the context in that case? – Gareth Rees Dec 16 '13 at 14:22
• @GarethRees You are right. I was reaching for a more defensive style, but I can't see an actual benefit now. – Janne Karila Dec 16 '13 at 18:51

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: