# decreasing solver speed

How can I decrease the time complexity and increase efficiency, without writing a new algorithm. My solution solves the majority of puzzles in a fast time, but for some difficult ones it can take over a minute! I have added some of the difficult puzzles below the code.

import numpy as np
from skimage.util import view_as_blocks  # pip install scikit-image

#input: 9x9 numpy array, empty cell = 0
#output: 9x9 numpy array: if not solution all array entries should be -1
#backtracking depth-first search with constraint propagation

#searches for 0 value in board
def zero_search(sudoku):
for i in range(len(sudoku)):
for j in range(len(sudoku[0])):
if sudoku[i][j] == 0:
return (i, j)  # row, col

return False

#parameters: board, num = inserted value, pos = board position(vector/tuple)
def valid(sudoku, num, pos):
# Check row
for i in range(len(sudoku[0])):
if sudoku[pos[0]][i] == num and pos[1] != i:
return False

# Check column
for i in range(len(sudoku)):
if sudoku[i][pos[1]] == num and pos[0] != i:
return False

# Check box
box_x = pos[1] // 3
box_y = pos[0] // 3

#y-axis/columns
for i in range(box_y*3, box_y*3 + 3):
#x-axis/rows
for j in range(box_x * 3, box_x*3 + 3):
if sudoku[i][j] == num and (i,j) != pos:
return False

return True

def solver(sudoku):

find = zero_search(sudoku)
if not find:
return True

else:
row, col = find

#check insertion values 1-9
for i in range(1,10):
if valid(sudoku, i, (row, col)):
sudoku[row][col] = i

if solver(sudoku):
return True

sudoku[row][col] = 0

return False

def initial_invalid(sudoku):

# Check row
for i in range(9):
dup_lst=[]
for j in range(9):
if sudoku[j][i]!=0:
if sudoku[j][i] in dup_lst:
return True

else:
dup_lst.append(sudoku[j][i])

#check column
for i in range(9):
dup_lst=[]
for j in range(9):
if sudoku[i][j]!=0:
if sudoku[i][j] in dup_lst:
return True

else:
dup_lst.append(sudoku[i][j])

#not needed
def final_valid (sudoku):

subgrids = view_as_blocks(sudoku, (3, 3))

sums = [np.sum(subgrids[i][j]) for j in range(3) for i in range(3)]
if sum(sums) !=405:
return False

else:
return True

#row_sum = sudoku.sum(axis=1)
#if sum(row_sum) != 405:
#   return False

#col_sum = sudoku.sum(axis=0)
#if sum(col_sum) != 405:
#    return False

def sudoku_solver(sudoku):

if initial_invalid(sudoku):
return np.full((9,9),-1)

if solver(sudoku):
return sudoku
else:
return np.full((9,9),-1)

[[0 8 0 4 3 0 0 0 0]
[0 0 5 0 0 9 0 0 0]
[6 0 0 0 8 0 0 7 0]
[0 0 0 0 9 0 0 0 3]
[0 0 0 8 0 7 0 0 0]
[9 0 0 0 0 0 0 5 4]
[0 6 0 0 0 0 0 0 5]
[0 0 8 0 0 0 4 0 0]
[0 4 0 0 0 6 0 1 0]]

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

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


## Keep track of possible values

A comment in your code says:

#backtracking depth-first search with constraint propagation

...but you're not actually propagating constraints. You can reduce the number of move validations by keeping track of the possible moves, i.e. the values a cell can actually have. Each inserted value (correct or not) constrains the possible values of cells in the same row, column and box, thus reducing the number of values you have to consider in subsequent recursive calls.

## Choose empty cells with least number of possible values

You're choosing the first empty cell. If that happens to have very little constraints, you're unnecessarily exploring a lot of possibilities that may have been invalidated if you had chosen a different cell first. Choosing the empty cell with the least number of possible values drastically reduces the breadth of your depth-first search tree.

## Example implementation

I tried to stay close to your original code and this code should only demonstrate how you can implement the mentioned concepts. There are still things that could be improved, but since you specifically asked about time complexity I concentrated purely on that.

import numpy as np
from skimage.util import view_as_blocks  # pip install scikit-image

# input: 9x9 numpy array, empty cell = 0
# output: 9x9 numpy array: if not solution all array entries should be -1
# backtracking depth-first search with constraint propagation

# Returns (row, col) of an empty cell with the least number of possible values.
# Returns False if no empty cell exists.
def get_emtpy_cell_with_least_possible_values(sudoku, possible_values):
min_possible_values = 10
min_row = -1
min_col = -1
for i in range(len(sudoku)):
for j in range(len(sudoku[0])):
if sudoku[i][j] == 0:
num_possible_numbers = sum(possible_values[i][j])
if num_possible_numbers < min_possible_values:
min_possible_values = num_possible_numbers
min_row = i
min_col = j
if min_possible_values < 10:
return (min_row, min_col)
else:
# No empty cell found
return False

def remove_possible_values(possible_values, row, col, value):
""" Remove 'value' from the possible values in row, col, and the box containing
cell [row][col]. Returns a list of tuples (row, col) for each cell that has been changed.
"""
cells_changed = []
for c_index, c in enumerate(possible_values[row]):
if c[value - 1] == 1:
cells_changed.append((row, c_index))
c[value - 1] = 0

for r in range(9):
if possible_values[r][col][value - 1] == 1:
cells_changed.append((r, col))
possible_values[r][col][value - 1] = 0

# Check box
box_x = col // 3
box_y = row // 3

# y-axis/columns
for i in range(box_y*3, box_y*3 + 3):
# x-axis/rows
for j in range(box_x * 3, box_x*3 + 3):
if possible_values[i][j][value - 1] == 1:
cells_changed.append((i,j))
possible_values[i][j][value - 1] = 0
return cells_changed

def restore_possible_values(possible_values, value, changed_cells):
""" Restore 'value' as possible value for each cell (row, col) in 'changed_cells'.
"""
for row, col in changed_cells:
possible_values[row][col][value - 1] = 1

def solver(sudoku, possible_values):
next_cell = get_emtpy_cell_with_least_possible_values(sudoku, possible_values)
if not next_cell:
return True
else:
row, col = next_cell

# check insertion values 1-9
for guessed_value in range(1, 10):
if possible_values[row][col][guessed_value - 1] != 1:
continue
# update possible values and sudoku board for recursive call
changed_cells = remove_possible_values(possible_values, row, col, guessed_value)
sudoku[row][col] = guessed_value

if solver(sudoku, possible_values):
return True
# restore possible values and sudoku board for next iteration
restore_possible_values(possible_values, guessed_value, changed_cells)
sudoku[row][col] = 0

return False

def initial_invalid(sudoku):

# Check row
for i in range(9):
dup_lst = []
for j in range(9):
if sudoku[j][i] != 0:
if sudoku[j][i] in dup_lst:
return True

else:
dup_lst.append(sudoku[j][i])

# check column
for i in range(9):
dup_lst = []
for j in range(9):
if sudoku[i][j] != 0:
if sudoku[i][j] in dup_lst:
return True

else:
dup_lst.append(sudoku[i][j])

def sudoku_solver(sudoku):

if initial_invalid(sudoku):
return np.full((9, 9), -1)

possible_values = np.ones((9,9,9), dtype=int)
# initialize possible values based on already existing values
for row in range(9):
for col in range(9):
value = sudoku[row][col]
if value != 0:
remove_possible_values(possible_values, row, col, value)

if solver(sudoku, possible_values):
return sudoku
else:
return np.full((9, 9), -1)



Some measurements on my computer using your examples:

original code improved code
Sudoku 1 21.836s 1.449s
Sudoku 2 2.753s 0.639s
Sudoku 3 50.993s 0.479s