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.."))