# Speed up performance of backtracking solution for Sudoku solver

I can't improve the performance of the following Sudoku Solver backtracking solution. I know there are 3 loops here and they probably cause slow performance but I can't find a better/more efficient way.

I tried to isolate "board" from mutation but it hasn't changed the performance. I also tried to use list comprehension for the top 2 "for" loops (i.e. only loop through rows and columns with zeros), tried to find coordinates of all zeros, and then use a single loop to go through them - hasn't helped.

I think I'm doing something fundamentally wrong here with recursion - any advice or recommendation on how to make the solution faster?

def box(board,row,column):
start_col = column - (column % 3)
finish_col = start_col + 3
start_row = row - (row % 3)
finish_row = start_row + 3
return [y for x in board[start_row:finish_row] for y in x[start_col:finish_col]]

def possible_values(board,row,column):
values = {1,2,3,4,5,6,7,8,9}
col_values = [v[column] for v in board]
row_values = board[row]
box_values = box(board, row, column)
return (values - set(row_values + col_values + box_values))

def solve(board, i_row = 0, i_col = 0):
for rn in range(i_row,len(board)):
if rn != i_row: i_col = 0
for cn in range(i_col,len(board)):
if board[rn][cn] == 0:
options = possible_values(board, rn, cn)
for board[rn][cn] in options:
if solve(board, rn, cn):
return board
board[rn][cn] = 0
#if no options left for the cell, go to previous cell and try next option
return False
#if no zeros left on the board, problem is solved
return True

problem = [
[9, 0, 0, 0, 8, 0, 0, 0, 1],
[0, 0, 0, 4, 0, 6, 0, 0, 0],
[0, 0, 5, 0, 7, 0, 3, 0, 0],
[0, 6, 0, 0, 0, 0, 0, 4, 0],
[4, 0, 1, 0, 6, 0, 5, 0, 8],
[0, 9, 0, 0, 0, 0, 0, 2, 0],
[0, 0, 7, 0, 3, 0, 2, 0, 0],
[0, 0, 0, 7, 0, 5, 0, 0, 0],
[1, 0, 0, 0, 4, 0, 0, 0, 7]
]

solve(problem)

• See my answer at codereview.stackexchange.com/questions/268007/… Jul 27 at 15:13
• @coderodde thanks, this is useful. I tested your solution and another solution from a comment above in that thread - although they're faster than mine, they are both not fast enough to pass Codewars's kata tests without timeout (codewars.com/kata/55171d87236c880cea0004c6/train/python). I conclude Codewar's timeout is too restrictive so backtracking solution will not work there (despite the fact the tasks asks for it!) Jul 27 at 16:09
• Processing the squares in order (e.g., top-left to bottom-right) is not an efficient way to search the solution space. It is more efficient to find squares with the fewest possibilities and do them first. In a best case, you find one that only has 1 possibility. Pick it and adjust the possible values for that row, column, and square. If the minimum has more that one possibility, then pick one and try it, If it doesn't work, try the others. If none work, backtrack like you do now. Lather, rinse, repeat. Jul 27 at 23:52

Code with significantly improved performance (thanks to @RootTwo for the hint). It's not ideal but it passes the required performance tests:

def solve(board, i_row = 0, i_col = 0):
cells_to_solve = [((rn, cn), possible_values(board,rn,cn)) for rn in range(len(board)) for cn in range(len(board)) if board[rn][cn] == 0]
if not cells_to_solve: return True

min_n_of_values = min([len(x[1]) for x in cells_to_solve])
if min_n_of_values == 0: return False

best_cells_to_try = [((rn,cn),options) for ((rn,cn),options) in cells_to_solve if len(options) == min_n_of_values]

for ((rn,cn),options) in best_cells_to_try:
for board[rn][cn] in options:
if solve(board, rn, cn):
return board
board[rn][cn] = 0
return False