Use algorithm X to solve sudoku. Credits: http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

sudokusolve.py

from collections import defaultdict
digits = "123456789"

constraints = defaultdict(set)
positions = {}

grids = {}
currentgrid = 0
squares = [a+b for a in digits for b in digits]

for rowgroup in ("123","456","789"):
    for colgroup in ("123","456","789"):
        currentgrid += 1
        for row in rowgroup:
            for col in colgroup:
                grids[row+col] = "g{}".format(currentgrid)

def makeconstraintsandpositions():
    for row in digits:
        for col in digits:
            for num in digits:
                poshash = "{}{}{}".format(row, col, num)
                rowhash = "r{}{}".format(row, num)
                colhash = "c{}{}".format(col, num)
                cellhash = "rc{}{}".format(row, col)
                gridhash = grids[row+col] + num
                
                positions[poshash] = [rowhash, colhash, gridhash, cellhash]
                constraints[rowhash].add(poshash)
                constraints[colhash].add(poshash)
                constraints[cellhash].add(poshash)
                constraints[gridhash].add(poshash)
    return constraints, positions

def solve(constraints, positions, solution=[]):
    if not constraints:
        yield list(solution)

    else:
        c = min(constraints, key=lambda x: len(constraints[x]))
        for position in constraints[c]:
            solution.append(position)
            cons = select(constraints, positions, position)
            for s in solve(constraints, positions, solution):
                yield s
            deselect(constraints, positions, position, cons)
            solution.pop()

def select(constraints, positions, position):
    cons = []
    for j in positions[position]:
        for i in constraints[j]:
            for k in positions[i]:
                if k != j:
                    constraints[k].remove(i)
        cons.append(constraints.pop(j))
    return cons

def deselect(constraints, positions, position, cons):
    for j in reversed(positions[position]):
        constraints[j] = cons.pop()
        for i in constraints[j]:
            for k in positions[i]:
                if k != j:
                    constraints[k].add(i)


def parse(string):
    solutions = []
    chars = [c for c in string if c in digits or c in "0.*"]
    constraints, positions = makeconstraintsandpositions()
    assert len(chars) == 81
    for square, value in zip(squares, chars):
        if value in digits:
            select(constraints, positions, square+value)
            solutions.append(square+value)

    return constraints, positions, solutions

def show(positions):
    sudoku = {}
    for position in positions:
        row, col, num = position
        sudoku[row+col] = num
    for row in digits:
        for col in digits:
            print sudoku[row+col],
        print

sdk="""
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0"""



for solution in solve(*parse(sdk)):
    show(solution)
    print "========="
print "done"