Exercise In Sudoku | Python Fiddle

import copy
from pprint import pprint
import time

def __main__():
    initial_board = [
        [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],
    ]

t0 = time.time()
    working_board = copy.deepcopy(initial_board)
    possibilities_board = make_all_possibilities(initial_board)
    solve_me(possibilities_board,working_board)
    t1 = time.time()
    total = t1-t0
    print "took {}".format(total)

def is_done(working_board):
    for row in working_board:
        for column in row:
            if not column:
                return False
    return True

def solve_me(possibilities_board, working_board):
    if is_done(working_board):
        pprint(working_board)
        print "SOLVED!"
        return
    else:
        i, j = 0, 0
        for y, row in enumerate(working_board):
            for x, column in enumerate(row):
                if column is 0:
                    i = y
                    j = x
                    break
            else:
                continue
            break

for possibility in possibilities_board[i][j]: #all possibilities for this spot
            if possibility_can_work(working_board, possibility, i, j):
                working_board[i][j] = possibility
                solve_me(possibilities_board, working_board)
        #Got here because for this spot no possibilities worked backtrack it
        working_board[i][j] = 0

def possibility_can_work(working_board, possibility, row, column):
    return possibility not in row_to_array(working_board, row) \
           and possibility not in block_to_array(working_board, row, column) \
           and possibility not in column_to_array(working_board, column)

def make_all_possibilities(initial_board):
    all_possibilities = [[0 for x in range(9)] for y in range(9)]
    for y, row in enumerate(initial_board):
        for x, column in enumerate(row):
            if column:
                all_possibilities[y][x] = [column]
            else:
                collisions = []
                collisions.extend(row_to_array(initial_board, y))
                collisions.extend(block_to_array(initial_board, y, x))
                collisions.extend(column_to_array(initial_board, x))
                all_possibilities[y][x] = list(set([1,2,3,4,5,6,7,8,9])-set(collisions))
    return all_possibilities

def row_to_array(initial_board, y):
    row_array = []
    for column in initial_board[y]:
        if column:
            row_array.append(column)
    return row_array

def block_to_array(initial_board, y, x):
    i, j = y/3, x/3
    block_array = []
    for row in range(i*3, (i*3)+3):
        for column in range((j*3), (j*3)+3):
            block_array.append(initial_board[row][column])
    return block_array

def column_to_array(initial_board, x):
    column_array = []
    for row in initial_board:
        column_array.append(row[x])
    return column_array

__main__()

Python Fiddle

Python Cloud IDE