decreasing solver speed

Question

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]]

Answer 1

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