Sudoku Solver
# Sudoku Solver - Peter A. Norvig
digits = '123456789'
rows = 'ABCDEFGHI'
cols = digits
def cross(A, B):
return [a+b for a in A for b in B]
squares = cross(rows, cols)
# unit - collection of nine squares (col, row or box)
# peers - squares that share a unit
unitlist = ([cross(rows, c) for c in cols] + [cross(r, cols) for r in rows] \
+ [cross(rs, cs) for rs in ('ABC', 'DEF', 'GHI') for cs in ('123', '456', '789')])
units = dict((s, [u for u in unitlist if s in u]) for s in squares)
peers = dict((s, set(sum(units[s], []))-set([s])) for s in squares)
# values - a dict with squares as keys, the value of each key will be the possible digits for that squares
# grid - string format of the puzzle
def parse_grid(grid):
"""Convert grid to a dict of possible values, {square: digits}, or
return False if a contradiction is detected."""
## To start, every square can be any digit; then assign values from the grid.
values = dict((s, digits) for s in squares)
for s, d in grid_values(grid).items():
if d in digits and not assign(values, s, d):
return False
return values
def grid_values(grid):
"Convert grid into a dict of {square: char} with '0' or '.' for empties"
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
return dict(zip(squares, chars))
# Constraint propagation: use the general strategies for reducing the number of
# possible values for a square
# 1. IF a square has only one possible value, eliminate that value from the square's peers
# 2. If a unit has only one possible place for a value, then put the value there.
def assign(values, s, d):
"""Eliminate all the other values (except d) from values[s] and propagate.
Return values, except return False if a contradiction is detected."""
other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
else:
return False
def eliminate(values, s, d):
"""Eliminate d from values[s]; propagate when values or places <= 2.
Return values, except return False if a contradiction is detected."""
if d not in values[s]:
return values # Already eliminated
values[s] = values[s].replace(d, '')
## Strategy 1
if len(values[s]) == 0:
return False
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## Strategy 2
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False
elif len(dplaces) == 1:
if not assign(values, dplaces[0], d):
return False
return values
def display(values):
"Display these values as a 2-D grid."
width = 1+max(len(values[s]) for s in squares)
line = '+'.join(['-'*(width*3)]*3)
for r in rows:
print (''.join(values[r+c].center(width)+('|' if c in '36' else '')
for c in cols))
if r in 'CF': print (line)
print()
# DFS
def search(values):
if values is False:
return False
if all(len(values[s]) == 1 for s in squares):
return values
n, s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d)) for d in values[s])
def solve(grid):
return search(parse_grid(grid))
def some(seq):
for e in seq:
if e:
return e
return False
grid = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
display(parse_grid(grid))