This code uses the constraint package (http://labix.org/python-constraint) to solve sudoku puzzles. It's designed to be flexible, though i've only tested it with 9x9 puzzles with 1-9 as possible values. In theory it should be able to solve puzzles of different sizes comprised of letters or symbols instead of numbers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | from itertools import islice
import constraint
def make_problem(blocks=9, block_size=3, possible_values=range(1, 10)):
indices = list(range(i*blocks, i*blocks+blocks) for i in xrange(blocks))
problem = constraint.Problem()
def ensure_unique_values(varnames):
# we don't want variable names to interfere with values,
# so we convert them to strings
problem.addConstraint(constraint.AllDifferentConstraint(), map(str, varnames))
for vars in indices:
problem.addVariables(map(str, vars), possible_values)
# ensure all values are unique per row
ensure_unique_values(vars)
for vars in zip(*indices):
# ensure all values are unique per column
ensure_unique_values(vars)
def block_indices(n):
(x, y) = divmod(n, block_size)
x *= block_size
y *= block_size
g_indices = list()
for i in xrange(block_size):
g_indices.extend(indices[x+i][y:y+block_size])
return g_indices
for i in xrange(blocks):
# ensure all values are unique per block
ensure_unique_values(block_indices(i))
return problem
class Unsolvable(Exception):
pass
def solve(matrix, problem=None):
if problem is None:
problem = make_problem()
for (varn, val) in enumerate(sum(matrix, [])):
if val is not None:
problem.addConstraint(lambda var, val=val: var==int(val), variables=(str(varn),))
soln = problem.getSolution()
if soln is None:
raise Unsolvable()
# soln is a dictionary of indices to values
values = (v for (k, v) in sorted(soln.iteritems(), key=lambda (k, v): int(k)))
cols = len(matrix)
while True:
row = list(islice(values, cols))
if not row:
break
yield row
# example
difficult = '''
X 4 X X X X X X X
X X X X X 6 5 X 4
3 6 X X 5 8 9 X X
9 8 X X X X X X X
X X X 5 7 2 X X X
X X X X X X X 4 1
X X 3 7 2 X X 5 9
2 X 5 8 X X X X X
X X X X X X X 3 X
'''
def text_puzzle_to_matrix(s, wildcard='X'):
m = list()
for line in s.split('\n'):
if len(line) == 0:
continue
line = line.split()
for (i, token) in enumerate(line):
if token == wildcard:
line[i] = None
m.append(line)
return m
for r in solve(text_puzzle_to_matrix(difficult)):
print r
|
There is a sudoku solver included with the constraint package, but it's less flexible.
Tags: algorithms
See also. http://www.jacobian.org/2006/mar/02/django-at-pycon/