from itertools import product
from copy import deepcopy
class Contradiction(Exception):
pass
def irange(start, stop, step=1):
"""Custom range type for allowing zero step."""
if 0 == step:
stop, step = start + 1, 1
return xrange(start, stop, step)
def get_seq(start_x, start_y, inc_x):
"""Get a row or column that a particular cell is constrained by"""
nums = set(range(1, 10))
cells = set()
for x, y in product(irange(start_x, 9, inc_x), irange(start_y, 9, 1 - inc_x)):
cells.add((x, y))
return cells
def get_box(x, y):
"""Get all of the cells within a box that a specific cell is
constrained by."""
left = (x // 3) * 3
top = (y // 3) * 3
cells = set(product(xrange(0 + left, 3 + left), xrange(0 + top, 3 + top)))
return cells
# build up the constraints matrix
constraints = { }
for x, y in product(xrange(0, 9), xrange(0, 9)):
constraints[x,y] = get_seq(0, y, 1)
constraints[x,y].update(get_seq(x, 0, 0))
constraints[x,y].update(get_box(x, y))
constraints[x,y].remove((x,y))
def initialize(initial_board):
"""Create the board to reflect the initial assignments and to have all
non-assigned cells have all possible values."""
board = { }
for (x, y) in product(xrange(0, 9), xrange(0, 9)):
if (x, y) in initial_board:
board[x,y] = set()
board[x,y].add(initial_board[x,y])
else:
board[x,y] = set(range(1, 10))
return board
def eliminate(board):
"""Propagate the constraints in the style of a breadth-first
search."""
wave, next_wave, seen = set(), set(), set()
for coord, cs in board.items():
if 1 == len(cs):
next_wave.add(coord)
while 0 < len(next_wave):
seen.update(wave)
wave.clear()
wave.update(next_wave)
next_wave.clear()
# propogate
for (x, y) in wave:
for (xi, yi) in constraints[x, y]:
board[xi, yi].difference_update(board[x,y])
if 0 == len(board[xi, yi]):
raise Contradiction
# collect, after constraints have been propagated
for xi, yi in product(xrange(0, 9), xrange(0, 9)):
if 1 == len(board[xi, yi]) and (xi, yi) not in seen:
next_wave.add((xi, yi))
def parse(line):
"""Parse a line into the initial board conditions"""
initial = { }
i = 0
for (x, y) in product(xrange(0, 9), xrange(0, 9)):
if "." != line[i]:
initial[x, y] = int(line[i])
i += 1
return initial
def search(board):
"""Does a depth-first search of the solution space using the minimum
remaining values heuristic."""
min_elms = 10
min_coord = None
# go find the cell with the minimum number of remaining possibilities
for (x, y) in product(xrange(0, 9), xrange(0, 9)):
if 1 < len(board[x, y]) < min_elms:
min_coord = x, y
min_elms = len(board[x, y])
# we have solved!
if None is min_coord:
return board
# do the search
choices = board[min_coord]
for choice in choices:
try:
board[min_coord] = set([choice])
temp_board = deepcopy(board)
eliminate(temp_board)
return search(temp_board)
except Contradiction:
pass
raise Contradiction
def solve(line):
"""Solve a sudoku puzzle"""
board = initialize(parse(line))
eliminate(board)
return search(board)
def print_board(board):
print "Solved Puzzle:",
i = 0
for x in range(0, 9):
if 0 == (i % 3):
print "\n", "-" * 95
else:
print
for y in range(0, 9):
if 0 == (y % 3):
print "|",
print "%9s" % "".join(map(str, board[x,y])),
i += 1
print_board(solve("3...8.......7....51..............36...2..4....7...........6.13..452...........8.."))