Welcome, guest | Sign In | My Account | Store | Cart

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.

Python, 90 lines
 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.

1 comment