Welcome, guest | Sign In | My Account | Store | Cart
```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

for vars in indices:
# 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:

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