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

Jeremy Dunck 17 years, 5 months ago
 Created by Moe Aboulkheir on Thu, 20 Apr 2006 (PSF)