One puzzle ('hard') makes 10 consecutive branches in the search, thus allowing 2**10 (I guess) possible outcomes. It takes around 40 seconds to beat this puzzle.

import functools import time DEBUGGER_TIMER = {} def timeit(func): @functools.wraps(func) def wrapper(*args, **kwargs): t_start = time.clock() ret = func(*args, **kwargs) t_end = time.clock() - t_start function_name = func.__name__ if function_name in DEBUGGER_TIMER: DEBUGGER_TIMER[function_name][0] += t_end DEBUGGER_TIMER[function_name][1] += 1 else: DEBUGGER_TIMER[function_name] = [t_end, 1] return ret return wrapper # index:(row,column,group,value) INDEX_TO_VALUE = {0: (0, 0, 0), 1: (0, 1, 0), 2: (0, 2, 0), 3: (0, 3, 1), 4: (0, 4, 1), 5: (0, 5, 1), 6: (0, 6, 2), 7: (0, 7, 2), 8: (0, 8, 2), 9: (1, 0, 0), 10: (1, 1, 0), 11: (1, 2, 0), 12: (1, 3, 1), 13: (1, 4, 1), 14: (1, 5, 1), 15: (1, 6, 2), 16: (1, 7, 2), 17: (1, 8, 2), 18: (2, 0, 0), 19: (2, 1, 0), 20: (2, 2, 0), 21: (2, 3, 1), 22: (2, 4, 1), 23: (2, 5, 1), 24: (2, 6, 2), 25: (2, 7, 2), 26: (2, 8, 2), 27: (3, 0, 3), 28: (3, 1, 3), 29: (3, 2, 3), 30: (3, 3, 4), 31: (3, 4, 4), 32: (3, 5, 4), 33: (3, 6, 5), 34: (3, 7, 5), 35: (3, 8, 5), 36: (4, 0, 3), 37: (4, 1, 3), 38: (4, 2, 3), 39: (4, 3, 4), 40: (4, 4, 4), 41: (4, 5, 4), 42: (4, 6, 5), 43: (4, 7, 5), 44: (4, 8, 5), 45: (5, 0, 3), 46: (5, 1, 3), 47: (5, 2, 3), 48: (5, 3, 4), 49: (5, 4, 4), 50: (5, 5, 4), 51: (5, 6, 5), 52: (5, 7, 5), 53: (5, 8, 5), 54: (6, 0, 6), 55: (6, 1, 6), 56: (6, 2, 6), 57: (6, 3, 7), 58: (6, 4, 7), 59: (6, 5, 7), 60: (6, 6, 8), 61: (6, 7, 8), 62: (6, 8, 8), 63: (7, 0, 6), 64: (7, 1, 6), 65: (7, 2, 6), 66: (7, 3, 7), 67: (7, 4, 7), 68: (7, 5, 7), 69: (7, 6, 8), 70: (7, 7, 8), 71: (7, 8, 8), 72: (8, 0, 6), 73: (8, 1, 6), 74: (8, 2, 6), 75: (8, 3, 7), 76: (8, 4, 7), 77: (8, 5, 7), 78: (8, 6, 8), 79: (8, 7, 8), 80: (8, 8, 8)} class Cell: board = [] missing_values = set('123456789') def __init__(self, row, column, group, value, index): self.row = row self.column = column self.value = value self.group = group self.index = index Cell.board.append(self) @timeit def get_missing_values(self): values = set() for cell in Cell.board: if cell.value != ".": if cell.row == self.row or cell.column == self.column or cell.group == self.group:   if cell != self:  values.add(cell.value) return Cell.missing_values.difference(values) @timeit def create_cells(puzzle): for index, value in enumerate(puzzle): row, column, group = INDEX_TO_VALUE[index] Cell(row, column, group, value, index) @timeit def get_next_moves(): try: moves = {} for cell in Cell.board: if cell.value == '.': missing_values = cell.get_missing_values() moves[cell.index] = missing_values if len(missing_values) == 1: return cell.index, moves[cell.index] for index in sorted(moves, key=lambda k: len(moves[k])): return index, moves[index] finally: Cell.board = [] # clean-up, just in case @timeit def possible_moves(puzzle): moves = get_next_moves() results = set() if moves: for move in moves[1]: index = moves[0] puzzle = puzzle[:index] + move + puzzle[index + 1:] results.add(puzzle) return results @timeit def win(puzzle): if "".join(sorted(puzzle)) == '111111111222222222333333333444444444555555555666666666777777777888888888999999999': return True return False @timeit def depth_first_search(graph, start): visited, stack = set(), [start] solutions = [] while stack: vertex = stack.pop() if '.' not in vertex: if win(vertex): solutions.append(vertex) if len(solutions) > 1: raise Exception("More than one solution") if vertex not in visited: visited.add(vertex) create_cells(vertex) graph[vertex] = possible_moves(vertex) stack.extend(graph[vertex] - visited) if solutions: return solutions else: raise Exception("No solution found") @timeit def main(min_test_time, min_runs, puzzle): easy = "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79" hard = "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.." if puzzle == 'easy': test_puzzle = easy else: test_puzzle = hard times = [] n_runs = 0 while sum(times) < min_test_time or min_runs > n_runs: n_runs += 1 graph = {test_puzzle: [None]} start = time.time() result = depth_first_search(graph, graph.keys()[0]) end = time.time() - start if not debug: return test_puzzle,result,end if end > 0.0: times.append(end) return times, n_runs def debugger((times, n_runs)): subtracts = {'main': ['depth_first_search'], 'depth_first_search': ['create_cells','possible_moves','win'], 'possible_moves': ['get_next_moves'], 'get_next_moves': ['get_missing_values'], 'get_missing_values': [], 'create_cells': [], 'win': []} total_time = sum(times) print "%s - %i RUNS"%(puzzle_to_test.upper(),n_runs) print "Total: %.1f seconds" % total_time if n_runs > 1: print "\tMean: %.5f seconds" % (total_time / n_runs) print "\tMax: %.5f seconds" % max(times) print "\tMin: %.5f seconds\n" % min(times) for f_name in DEBUGGER_TIMER: f_time = DEBUGGER_TIMER[f_name][0] - sum([DEBUGGER_TIMER[o_name][0] for o_name in subtracts[f_name]]) DEBUGGER_TIMER[f_name].append(f_time) for f_name in sorted(DEBUGGER_TIMER, key=lambda name: DEBUGGER_TIMER[name][2], reverse=True): real_time = DEBUGGER_TIMER[f_name][2] f_runs = DEBUGGER_TIMER[f_name][1] print "%s()\n\t" \ "Called: %i times per run(%i total)\n\t" \ "Running for %.3fs(in %i runs) / %.5fs per run" % ( f_name, (f_runs + (n_runs - 1)) // n_runs, f_runs, real_time, n_runs, real_time / n_runs) if __name__ == '__main__': puzzle_to_test = 'hard' debug = True if debug: min_test_time = 10 # seconds min_runs = 3 debugger(main(min_test_time,min_runs,puzzle_to_test)) else: puzzle, result,end_time = main(0, 1, puzzle_to_test) print "Puzzle: " for i, n in enumerate(puzzle,1): if i % 9 == 0: print n else: print n, print "\nSolution" for i,n in enumerate(result[0],1): if i%9==0: print n else: print n, print "\nTook %.2f seconds"%end_time 

I would gladly accept any other critique on this program too since I'm a new programmer.

One puzzle ('hard') makes 10 consecutive branches in the search, thus allowing 2¹⁰ (I guess) possible outcomes. It takes around 40 seconds to beat this puzzle.

import functools import time DEBUGGER_TIMER = {} def timeit(func): @functools.wraps(func) def wrapper(*args, **kwargs): t_start = time.clock() ret = func(*args, **kwargs) t_end = time.clock() - t_start function_name = func.__name__ if function_name in DEBUGGER_TIMER: DEBUGGER_TIMER[function_name][0] += t_end DEBUGGER_TIMER[function_name][1] += 1 else: DEBUGGER_TIMER[function_name] = [t_end, 1] return ret return wrapper # index:(row,column,group,value) INDEX_TO_VALUE = {0: (0, 0, 0), 1: (0, 1, 0), 2: (0, 2, 0), 3: (0, 3, 1), 4: (0, 4, 1), 5: (0, 5, 1), 6: (0, 6, 2), 7: (0, 7, 2), 8: (0, 8, 2), 9: (1, 0, 0), 10: (1, 1, 0), 11: (1, 2, 0), 12: (1, 3, 1), 13: (1, 4, 1), 14: (1, 5, 1), 15: (1, 6, 2), 16: (1, 7, 2), 17: (1, 8, 2), 18: (2, 0, 0), 19: (2, 1, 0), 20: (2, 2, 0), 21: (2, 3, 1), 22: (2, 4, 1), 23: (2, 5, 1), 24: (2, 6, 2), 25: (2, 7, 2), 26: (2, 8, 2), 27: (3, 0, 3), 28: (3, 1, 3), 29: (3, 2, 3), 30: (3, 3, 4), 31: (3, 4, 4), 32: (3, 5, 4), 33: (3, 6, 5), 34: (3, 7, 5), 35: (3, 8, 5), 36: (4, 0, 3), 37: (4, 1, 3), 38: (4, 2, 3), 39: (4, 3, 4), 40: (4, 4, 4), 41: (4, 5, 4), 42: (4, 6, 5), 43: (4, 7, 5), 44: (4, 8, 5), 45: (5, 0, 3), 46: (5, 1, 3), 47: (5, 2, 3), 48: (5, 3, 4), 49: (5, 4, 4), 50: (5, 5, 4), 51: (5, 6, 5), 52: (5, 7, 5), 53: (5, 8, 5), 54: (6, 0, 6), 55: (6, 1, 6), 56: (6, 2, 6), 57: (6, 3, 7), 58: (6, 4, 7), 59: (6, 5, 7), 60: (6, 6, 8), 61: (6, 7, 8), 62: (6, 8, 8), 63: (7, 0, 6), 64: (7, 1, 6), 65: (7, 2, 6), 66: (7, 3, 7), 67: (7, 4, 7), 68: (7, 5, 7), 69: (7, 6, 8), 70: (7, 7, 8), 71: (7, 8, 8), 72: (8, 0, 6), 73: (8, 1, 6), 74: (8, 2, 6), 75: (8, 3, 7), 76: (8, 4, 7), 77: (8, 5, 7), 78: (8, 6, 8), 79: (8, 7, 8), 80: (8, 8, 8)} class Cell: board = [] missing_values = set('123456789') def __init__(self, row, column, group, value, index): self.row = row self.column = column self.value = value self.group = group self.index = index Cell.board.append(self) @timeit def get_missing_values(self): values = set('.') for cell in Cell.board: if cell.value not in values: if cell.row == self.row:    values.add(cell.value)    elif cell.column == self.column: values.add(cell.value)    elif cell.group == self.group:  values.add(cell.value) return Cell.missing_values.difference(values) @timeit def create_cells(puzzle): for index, value in enumerate(puzzle): row, column, group = INDEX_TO_VALUE[index] Cell(row, column, group, value, index) @timeit def get_next_moves(): try: moves = {} for cell in Cell.board: if cell.value == '.': missing_values = cell.get_missing_values() moves[cell.index] = missing_values if len(missing_values) == 1: return cell.index, moves[cell.index] for index in sorted(moves, key=lambda k: len(moves[k])): return index, moves[index] finally: Cell.board = [] # clean-up, just in case @timeit def possible_moves(puzzle): moves = get_next_moves() results = set() if moves: for move in moves[1]: index = moves[0] puzzle = puzzle[:index] + move + puzzle[index + 1:] results.add(puzzle) return results @timeit def win(puzzle): if "".join(sorted(puzzle)) == '111111111222222222333333333444444444555555555666666666777777777888888888999999999': return True return False @timeit def depth_first_search(graph, start): visited, stack = set(), [start] solutions = [] while stack: vertex = stack.pop() if '.' not in vertex: if win(vertex): solutions.append(vertex) if len(solutions) > 1: raise Exception("More than one solution") if vertex not in visited: visited.add(vertex) create_cells(vertex) graph[vertex] = possible_moves(vertex) stack.extend(graph[vertex] - visited) if solutions: return solutions else: raise Exception("No solution found") @timeit def main(min_test_time, min_runs, puzzle): easy = "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79" hard = "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.." if puzzle == 'easy': test_puzzle = easy else: test_puzzle = hard times = [] n_runs = 0 while sum(times) < min_test_time or min_runs > n_runs: n_runs += 1 graph = {test_puzzle: [None]} start = time.time() result = depth_first_search(graph, graph.keys()[0]) end = time.time() - start if not debug: return test_puzzle,result,end if end > 0.0: times.append(end) return times, n_runs def debugger((times, n_runs)): subtracts = {'main': ['depth_first_search'], 'depth_first_search': ['create_cells','possible_moves','win'], 'possible_moves': ['get_next_moves'], 'get_next_moves': ['get_missing_values'], 'get_missing_values': [], 'create_cells': [], 'win': []} total_time = sum(times) print "%s - %i RUNS"%(puzzle_to_test.upper(),n_runs) print "Total: %.1f seconds" % total_time if n_runs > 1: print "\tMean: %.5f seconds" % (total_time / n_runs) print "\tMax: %.5f seconds" % max(times) print "\tMin: %.5f seconds\n" % min(times) for f_name in DEBUGGER_TIMER: f_time = DEBUGGER_TIMER[f_name][0] - sum([DEBUGGER_TIMER[o_name][0] for o_name in subtracts[f_name]]) DEBUGGER_TIMER[f_name].append(f_time) for f_name in sorted(DEBUGGER_TIMER, key=lambda name: DEBUGGER_TIMER[name][2], reverse=True): real_time = DEBUGGER_TIMER[f_name][2] f_runs = DEBUGGER_TIMER[f_name][1] print "%s()\n\t" \ "Called: %i times per run(%i total)\n\t" \ "Running for %.3fs(in %i runs) / %.5fs per run" % ( f_name, (f_runs + (n_runs - 1)) // n_runs, f_runs, real_time, n_runs, real_time / n_runs) if __name__ == '__main__': puzzle_to_test = 'hard' debug = True if debug: min_test_time = 10 # seconds min_runs = 3 debugger(main(min_test_time,min_runs,puzzle_to_test)) else: puzzle, result,end_time = main(0, 1, puzzle_to_test) print "Puzzle: " for i, n in enumerate(puzzle,1): if i % 9 == 0: print n else: print n, print "\nSolution" for i,n in enumerate(result[0],1): if i%9==0: print n else: print n, print "\nTook %.2f seconds"%end_time 

EDIT:

Manage to shrink it to 63 seconds the 3 runs on HARD. But I still think it's possible to make it even faster.

Changes:

def get_missing_values(self): values = set('.') for cell in Cell.board: if cell.value not in values: if cell.row == self.row: values.add(cell.value) elif cell.column == self.column: values.add(cell.value) elif cell.group == self.group: values.add(cell.value) return Cell.missing_values.difference(values) 

EDIT2:

Tried user3267581 approach:

Here's my implementation:

ROWS = [0]*9 COLUMNS = [0]*9 GROUPS = [0]*9 # I've used a int[9] matrix because I already have the 9 groups mapped in the INDEX_TO_VALUE lookup-table VALUES = [0]*81 def store(row,column,group,value,index): value = int(value) VALUES[index] = value ROWS[row] |= 1 << value COLUMNS[column] |= 1 << value GROUPS[group] |= 1 << value def create_cells(puzzle): for index, value in enumerate(puzzle): row, column, group = INDEX_TO_VALUE[index] VALUES[index] = value if value == ".": value = 0 store(row, column,group, value,index) def check(number,row,column,group): if ROWS[row] & 1 << number: return False elif COLUMNS[column] & 1 << number: return False elif GROUPS[group] & 1 << number: return False return True def get_missing_values(row, column, group,value): values = set() for n in xrange(1, 10): if check(n, row, column, group): values.add(n) return values - {value} def get_next_moves(): global ROWS, COLUMNS, GROUPS, VALUES try: other_option = None len_option = 9 for index in xrange(81): row, column, group = INDEX_TO_VALUE[index] value = VALUES[index] if value == 0: missing_values = get_missing_values(row, column, group,value) if len(missing_values) == 1: return index, missing_values elif len(missing_values) < len_option: len_option = len(missing_values) other_option = index, missing_values return other_option finally: ROWS = [0] * 9 COLUMNS = [0] * 9 GROUPS = [0] * 9 VALUES = [0]*81 

The result:

HARD - 3 RUNS Total: 85.7 seconds Mean: 28.55933 seconds Max: 28.93500 seconds Min: 28.00800 seconds create_cells() Called: 47680 times per run(143040 total) Running for 23.594s(in 3 runs) / 7.86472s per run store() Called: 3862080 times per run(11586240 total) Running for 22.380s(in 3 runs) / 7.45990s per run get_missing_values() Called: 475329 times per run(1425987 total) Running for 21.041s(in 3 runs) / 7.01353s per run check() Called: 4277961 times per run(12833883 total) Running for 10.917s(in 3 runs) / 3.63885s per run get_next_moves() Called: 47680 times per run(143040 total) Running for 5.406s(in 3 runs) / 1.80215s per run possible_moves() Called: 47680 times per run(143040 total) Running for 1.665s(in 3 runs) / 0.55500s per run 

Even tho the get_missing_values is much faster(21s vs 39s), the other methods(store,and check) increased it's time, create cells also took a bit longer(23s vs 20s), my previous edit took 63s(~22s sec per run), this one is 85s(~28s per run).

HARD - 3 RUNS Total: 68.3 seconds Mean: 22.77100 seconds Max: 24.91000 seconds Min: 21.67100 seconds get_missing_values() Called: 475329 times per run(1425987 total) Running for 39.582s(in 3 runs) / 13.19397s per run create_cells() Called: 47680 times per run(143040 total) Running for 20.316s(in 3 runs) / 6.77190s per run get_next_moves() Called: 47680 times per run(143040 total) Running for 5.957s(in 3 runs) / 1.98568s per run possible_moves() Called: 47680 times per run(143040 total) Running for 1.759s(in 3 runs) / 0.58646s per run depth_first_search() Called: 1 times per run(3 total) Running for 0.698s(in 3 runs) / 0.23259s per run main() Called: 1 times per run(1 total) Running for 0.040s(in 3 runs) / 0.01343s per run win() Called: 1 times per run(3 total) Running for 0.000s(in 3 runs) / 0.00003s per run 

import functools import time DEBUGGER_TIMER = {} def timeit(func): @functools.wraps(func) def wrapper(*args, **kwargs): t_start = time.clock() ret = func(*args, **kwargs) t_end = time.clock() - t_start function_name = func.__name__ if function_name in DEBUGGER_TIMER: DEBUGGER_TIMER[function_name][0] += t_end DEBUGGER_TIMER[function_name][1] += 1 else: DEBUGGER_TIMER[function_name] = [t_end, 1] return ret return wrapper # index:(row,column,group,value) INDEX_TO_VALUE = {0: (0, 0, 0), 1: (0, 1, 0), 2: (0, 2, 0), 3: (0, 3, 1), 4: (0, 4, 1), 5: (0, 5, 1), 6: (0, 6, 2), 7: (0, 7, 2), 8: (0, 8, 2), 9: (1, 0, 0), 10: (1, 1, 0), 11: (1, 2, 0), 12: (1, 3, 1), 13: (1, 4, 1), 14: (1, 5, 1), 15: (1, 6, 2), 16: (1, 7, 2), 17: (1, 8, 2), 18: (2, 0, 0), 19: (2, 1, 0), 20: (2, 2, 0), 21: (2, 3, 1), 22: (2, 4, 1), 23: (2, 5, 1), 24: (2, 6, 2), 25: (2, 7, 2), 26: (2, 8, 2), 27: (3, 0, 3), 28: (3, 1, 3), 29: (3, 2, 3), 30: (3, 3, 4), 31: (3, 4, 4), 32: (3, 5, 4), 33: (3, 6, 5), 34: (3, 7, 5), 35: (3, 8, 5), 36: (4, 0, 3), 37: (4, 1, 3), 38: (4, 2, 3), 39: (4, 3, 4), 40: (4, 4, 4), 41: (4, 5, 4), 42: (4, 6, 5), 43: (4, 7, 5), 44: (4, 8, 5), 45: (5, 0, 3), 46: (5, 1, 3), 47: (5, 2, 3), 48: (5, 3, 4), 49: (5, 4, 4), 50: (5, 5, 4), 51: (5, 6, 5), 52: (5, 7, 5), 53: (5, 8, 5), 54: (6, 0, 6), 55: (6, 1, 6), 56: (6, 2, 6), 57: (6, 3, 7), 58: (6, 4, 7), 59: (6, 5, 7), 60: (6, 6, 8), 61: (6, 7, 8), 62: (6, 8, 8), 63: (7, 0, 6), 64: (7, 1, 6), 65: (7, 2, 6), 66: (7, 3, 7), 67: (7, 4, 7), 68: (7, 5, 7), 69: (7, 6, 8), 70: (7, 7, 8), 71: (7, 8, 8), 72: (8, 0, 6), 73: (8, 1, 6), 74: (8, 2, 6), 75: (8, 3, 7), 76: (8, 4, 7), 77: (8, 5, 7), 78: (8, 6, 8), 79: (8, 7, 8), 80: (8, 8, 8)} class Cell: board = [] missing_values = set('123456789') def __init__(self, row, column, group, value, index): self.row = row self.column = column self.value = value self.group = group self.index = index Cell.board.append(self) @timeit def get_missing_values(self): values = set('.') for cell in Cell.board: if cell.value not in values: if cell.row == self.row:  values.add(cell.value)  elif cell.column == self.column:   values.add(cell.value)  elif cell.group == self.group: values.add(cell.value) return Cell.missing_values.difference(values)    @timeit def create_cells(puzzle): for index, value in enumerate(puzzle): row, column, group = INDEX_TO_VALUE[index] Cell(row, column, group, value, index) @timeit def get_next_moves(): try: other_option = None len_option = 9 for cell in Cell.board: if cell.value == '.': missing_values = cell.get_missing_values() if len(missing_values) == 1: return cell.index, missing_values   elif len(missing_values) < len_option:  len_option = len(missing_values)   other_option = cell.index, missing_values  return other_option finally: Cell.board = [] # clean-up, just in case @timeit def possible_moves(puzzle):  create_cells(puzzle)  moves = get_next_moves() results = set() if moves: index = moves[0] list(results.add("%s%s%s" % (puzzle[:index], move, puzzle[index + 1:])) for move in moves[1])  return results return set() @timeit def win(puzzle): if "".join(sorted(puzzle)) == '111111111222222222333333333444444444555555555666666666777777777888888888999999999': return True return False @timeit def depth_first_search(graph, start): visited, stack = set(), [start] solutions = [] while stack: vertex = stack.pop() if '.' not in vertex: if win(vertex): solutions.append(vertex) if len(solutions) > 1: raise Exception("More than one solution") if vertex not in visited: visited.add(vertex) graph[vertex] = possible_moves(vertex) stack.extend(graph[vertex] - visited) if solutions: return solutions else: raise Exception("No solution found")    @timeit def main(min_test_time, min_runs, puzzle): easy = "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79" hard = "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.." if puzzle == 'easy': test_puzzle = easy else: test_puzzle = hard times = [] n_runs = 0 while sum(times) < min_test_time or min_runs > n_runs: n_runs += 1 graph = {test_puzzle: [None]} start = time.time() result = depth_first_search(graph, graph.keys()[0]) end = time.time() - start if not debug: return test_puzzle,result,end if end > 0.0: times.append(end) return times, n_runs    def debugger((times, n_runs)): subtracts = {'main': ['depth_first_search'], 'depth_first_search': ['possible_moves','win'], 'possible_moves': ['get_next_moves','create_cells'], 'get_next_moves': ['get_missing_values'], 'get_missing_values': [], 'create_cells': [], 'win': []} total_time = sum(times) print "%s - %i RUNS"%(puzzle_to_test.upper(),n_runs) print "Total: %.1f seconds" % total_time if n_runs > 1: print "\tMean: %.5f seconds" % (total_time / n_runs) print "\tMax: %.5f seconds" % max(times) print "\tMin: %.5f seconds\n" % min(times) for f_name in DEBUGGER_TIMER: f_time = DEBUGGER_TIMER[f_name][0] - sum([DEBUGGER_TIMER[o_name][0] for o_name in subtracts[f_name]]) DEBUGGER_TIMER[f_name].append(f_time) for f_name in sorted(DEBUGGER_TIMER, key=lambda name: DEBUGGER_TIMER[name][2], reverse=True): real_time = DEBUGGER_TIMER[f_name][2] f_runs = DEBUGGER_TIMER[f_name][1] print "%s()\n\t" \ "Called: %i times per run(%i total)\n\t" \ "Running for %.3fs(in %i runs) / %.5fs per run" % ( f_name, (f_runs + (n_runs - 1)) // n_runs, f_runs, real_time, n_runs, real_time / n_runs) if __name__ == '__main__': puzzle_to_test = 'hard' debug = True if debug: min_test_time = 1 # seconds min_runs = 3 debugger(main(min_test_time,min_runs,puzzle_to_test)) else: puzzle, result,end_time = main(0, 1, puzzle_to_test) print "Puzzle: " for i, n in enumerate(puzzle,1): if i % 9 == 0: print n else: print n, print "\nSolution" for i,n in enumerate(result[0],1): if i%9==0: print n else: print n, print "\nTook %.2f seconds"%end_time 

EDIT1:

moved the code above. updated the Profiler too.

HARD - 3 RUNS Total: 114.4 seconds Mean: 38.13433 seconds Max: 38.67300 seconds Min: 37.74700 seconds get_missing_values() Called: 475437 times per run(1426311 total) Running for 87.362s(in 3 runs) / 29.12073s per run create_cells() Called: 47700 times per run(143100 total) Running for 19.419s(in 3 runs) / 6.47302s per run get_next_moves() Called: 47700 times per run(143100 total) Running for 6.117s(in 3 runs) / 2.03890s per run depth_first_search() Called: 1 times per run(3 total) Running for 0.856s(in 3 runs) / 0.28532s per run possible_moves() Called: 47700 times per run(143100 total) Running for 0.647s(in 3 runs) / 0.21570s per run main() Called: 1 times per run(1 total) Running for 0.056s(in 3 runs) / 0.01876s per run win() Called: 1 times per run(3 total) Running for 0.000s(in 3 runs) / 0.00002s per run 

import functools import time DEBUGGER_TIMER = {}    def timeit(func): @functools.wraps(func) def wrapper(*args, **kwargs): t_start = time.clock() ret = func(*args, **kwargs) t_end = time.clock() - t_start function_name = func.__name__ if function_name in DEBUGGER_TIMER: DEBUGGER_TIMER[function_name][0] += t_end DEBUGGER_TIMER[function_name][1] += 1 else: DEBUGGER_TIMER[function_name] = [t_end, 1] return ret    return wrapper # index:(row,column,group,value) INDEX_TO_VALUE = {0: (0, 0, 0), 1: (0, 1, 0), 2: (0, 2, 0), 3: (0, 3, 1), 4: (0, 4, 1), 5: (0, 5, 1), 6: (0, 6, 2), 7: (0, 7, 2), 8: (0, 8, 2), 9: (1, 0, 0), 10: (1, 1, 0), 11: (1, 2, 0), 12: (1, 3, 1), 13: (1, 4, 1), 14: (1, 5, 1), 15: (1, 6, 2), 16: (1, 7, 2), 17: (1, 8, 2), 18: (2, 0, 0), 19: (2, 1, 0), 20: (2, 2, 0), 21: (2, 3, 1), 22: (2, 4, 1), 23: (2, 5, 1), 24: (2, 6, 2), 25: (2, 7, 2), 26: (2, 8, 2), 27: (3, 0, 3), 28: (3, 1, 3), 29: (3, 2, 3), 30: (3, 3, 4), 31: (3, 4, 4), 32: (3, 5, 4), 33: (3, 6, 5), 34: (3, 7, 5), 35: (3, 8, 5), 36: (4, 0, 3), 37: (4, 1, 3), 38: (4, 2, 3), 39: (4, 3, 4), 40: (4, 4, 4), 41: (4, 5, 4), 42: (4, 6, 5), 43: (4, 7, 5), 44: (4, 8, 5), 45: (5, 0, 3), 46: (5, 1, 3), 47: (5, 2, 3), 48: (5, 3, 4), 49: (5, 4, 4), 50: (5, 5, 4), 51: (5, 6, 5), 52: (5, 7, 5), 53: (5, 8, 5), 54: (6, 0, 6), 55: (6, 1, 6), 56: (6, 2, 6), 57: (6, 3, 7), 58: (6, 4, 7), 59: (6, 5, 7), 60: (6, 6, 8), 61: (6, 7, 8), 62: (6, 8, 8), 63: (7, 0, 6), 64: (7, 1, 6), 65: (7, 2, 6), 66: (7, 3, 7), 67: (7, 4, 7), 68: (7, 5, 7), 69: (7, 6, 8), 70: (7, 7, 8), 71: (7, 8, 8), 72: (8, 0, 6), 73: (8, 1, 6), 74: (8, 2, 6), 75: (8, 3, 7), 76: (8, 4, 7), 77: (8, 5, 7), 78: (8, 6, 8), 79: (8, 7, 8), 80: (8, 8, 8)} class Cell: board = [] missing_values = set('123456789') def __init__(self, row, column, group, value, index): self.row = row self.column = column self.value = value self.group = group self.index = index Cell.board.append(self) @timeit def get_missing_values(self): values = set() for cell in Cell.board: if cell.value != ".": if cell.row == self.row or cell.column == self.column or cell.group == self.group: if cell != self:   values.add(cell.value) return Cell.missing_values.difference(values) @timeit def create_cells(puzzle): for index, value in enumerate(puzzle): row, column, group = INDEX_TO_VALUE[index] Cell(row, column, group, value, index) @timeit def get_next_moves(): try: moves = {} for cell in Cell.board: if cell.value == '.': missing_values = cell.get_missing_values()  moves[cell.index] = missing_values  if len(missing_values) == 1: return cell.index, moves[cell.index] for index in sorted(moves, key=lambda k: len(moves[k])): return index, moves[index] finally: Cell.board = [] # clean-up, just in case @timeit def possible_moves(puzzle): moves = get_next_moves() results = set() if moves: for move in moves[1]: index = moves[0]  puzzle = puzzle[:index] + move + puzzle[index + 1:]   results.add(puzzle) return results @timeit def win(puzzle): if "".join(sorted(puzzle)) == '111111111222222222333333333444444444555555555666666666777777777888888888999999999': return True return False @timeit def depth_first_search(graph, start): visited, stack = set(), [start] solutions = [] while stack: vertex = stack.pop() if '.' not in vertex: if win(vertex): solutions.append(vertex) if len(solutions) > 1: raise Exception("More than one solution") if vertex not in visited: visited.add(vertex)  create_cells(vertex)  graph[vertex] = possible_moves(vertex) stack.extend(graph[vertex] - visited) if solutions: return solutions else: raise Exception("No solution found") @timeit def main(min_test_time, min_runs, puzzle): easy = "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79" hard = "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.." if puzzle == 'easy': test_puzzle = easy else: test_puzzle = hard times = [] n_runs = 0 while sum(times) < min_test_time or min_runs > n_runs: n_runs += 1 graph = {test_puzzle: [None]} start = time.time() result = depth_first_search(graph, graph.keys()[0]) end = time.time() - start if not debug: return test_puzzle,result,end if end > 0.0: times.append(end) return times, n_runs def debugger((times, n_runs)): subtracts = {'main': ['depth_first_search'], 'depth_first_search': ['create_cells','possible_moves','win'], 'possible_moves': ['get_next_moves'], 'get_next_moves': ['get_missing_values'], 'get_missing_values': [], 'create_cells': [], 'win': []} total_time = sum(times) print "%s - %i RUNS"%(puzzle_to_test.upper(),n_runs) print "Total: %.1f seconds" % total_time if n_runs > 1: print "\tMean: %.5f seconds" % (total_time / n_runs) print "\tMax: %.5f seconds" % max(times) print "\tMin: %.5f seconds\n" % min(times) for f_name in DEBUGGER_TIMER: f_time = DEBUGGER_TIMER[f_name][0] - sum([DEBUGGER_TIMER[o_name][0] for o_name in subtracts[f_name]]) DEBUGGER_TIMER[f_name].append(f_time) for f_name in sorted(DEBUGGER_TIMER, key=lambda name: DEBUGGER_TIMER[name][2], reverse=True): real_time = DEBUGGER_TIMER[f_name][2] f_runs = DEBUGGER_TIMER[f_name][1] print "%s()\n\t" \ "Called: %i times per run(%i total)\n\t" \ "Running for %.3fs(in %i runs) / %.5fs per run" % ( f_name, (f_runs + (n_runs - 1)) // n_runs, f_runs, real_time, n_runs, real_time / n_runs)    if __name__ == '__main__': puzzle_to_test = 'hard' debug = True if debug: min_test_time = 10 # seconds min_runs = 3 debugger(main(min_test_time,min_runs,puzzle_to_test)) else: puzzle, result,end_time = main(0, 1, puzzle_to_test) print "Puzzle: " for i, n in enumerate(puzzle,1): if i % 9 == 0: print n else: print n, print "\nSolution" for i,n in enumerate(result[0],1): if i%9==0: print n else: print n, print "\nTook %.2f seconds"%end_time 

EDIT:

Manage to shrink it to 63 seconds the 3 runs on HARD. But I still think it's possible to make it even faster.

Changes:

def get_missing_values(self): values = set('.') for cell in Cell.board: if cell.value not in values: if cell.row == self.row: values.add(cell.value) elif cell.column == self.column: values.add(cell.value) elif cell.group == self.group: values.add(cell.value) return Cell.missing_values.difference(values)