I made this Sudoku solver using depth first search, it takes less than 0.1 second to solve any simple solution(no guessing), but if the solution requires guessing (thus using the DFS) its time grows exponentially.
One puzzle ('hard') makes 10 consecutive branches in the search, thus allowing 210 (I guess) possible outcomes. It takes around 40 seconds to beat this puzzle.
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
As you can see, the source of the most 'work' is the method get_missing_values
from the class Cell
, which takes 76% of all the workload. This method searches for every cell in the grid and compare it to the others to get what possible values could be placed there. I tried to squeeze it as much as I could, using multiple if
-conditions, but it still takes a lot of work.
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