How to make my backtraching sudoku solving algorithm in Python faster? I wrote a backtracking Sudoku solving algorithm in Python.
It solves a 2D array like this (zero means "empty field"):

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


like this:

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


But for "hard" Sudokus (where there are a lot of zeros at the beginning), it's quite slow. It takes the algorithm around 9 seconds to solve the Sudoku above. That's a lot better then what I startet with (90 seconds), but still slow.

I think that the "deepcopy" can somehow be improved/replaced (because it is executed 103.073 times in the example below), but my basic approaches were slower..

I heard of 0.01 second C/C++ solutions but I'm not sure if those are backtracking algorithms of some kind of mathematical solution...

This is my whole algorithm with 2 example Sudokus:

from copy import deepcopy

def is_sol_row(mat,row,val):
  m = len(mat)
  for i in range(m):
    if mat[row][i] == val:
      return False
  return True

def is_sol_col(mat,col,val):
  m = len(mat)
  for i in range(m):
    if mat[i][col] == val:
      return False
  return True

def is_sol_block(mat,row,col,val):
  rainbow = [0,0,0,3,3,3,6,6,6]
  i = rainbow[row]
  j = rainbow[col]
  elements = {
    mat[i + 0][j + 0], mat[i + 1][j + 0], mat[i + 2][j + 0],
    mat[i + 0][j + 1], mat[i + 1][j + 1], mat[i + 2][j + 1],
    mat[i + 0][j + 2], mat[i + 1][j + 2], mat[i + 2][j + 2],
  }
  if val in elements:
    return False
  return True

def is_sol(mat,row,col,val):
  return is_sol_row(mat,row,val) and is_sol_col(mat,col,val) and is_sol_block(mat,row,col,val)

def findAllZeroIndizes(mat):
  m = len(mat)
  indizes = []
  for i in range(m):
    for j in range(m):
      if mat[i][j] == 0:
        indizes.append((i,j))
  return indizes

def sudoku(mat):
  q = [(mat,0)]
  zeroIndizes = findAllZeroIndizes(mat)
  while q:
    t,numSolvedIndizes = q.pop()
    if numSolvedIndizes == len(zeroIndizes):
      return t
    else:
      i,j = zeroIndizes[numSolvedIndizes]
      for k in range(1,10):
        if is_sol(t,i,j,k):
          newt = deepcopy(t)
          newt[i][j] = k
          q.append((newt,numSolvedIndizes+1))
  return False


mat = [
  [7, 0, 0, 0, 0, 9, 0, 0, 3],
  [0, 9, 0, 1, 0, 0, 8, 0, 0],
  [0, 1, 0, 0, 0, 7, 0, 0, 0],

  [0, 3, 0, 4, 0, 0, 0, 8, 0],
  [6, 0, 0, 0, 8, 0, 0, 0, 1],
  [0, 7, 0, 0, 0, 2, 0, 3, 0],

  [0, 0, 0, 5, 0, 0, 0, 1, 0],
  [0, 0, 4, 0, 0, 3, 0, 9, 0],
  [5, 0, 0, 7, 0, 0, 0, 0, 2],
]

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

print(sudoku(mat))
Your sudoku solver is missing a crucial part: the one that fills all obvious cells without backtracking.

In your example sudoku, in row 1 column 7 there must be a 1 because that's the only place in row 1 where a 1 is possible. That's because the blocks to the left already contain a 1, and columns 8 and 9 also contain a 1 further down.

With that improvement, the algorithm should get quite fast. That's probably how every other sudoku solver attacks the complexity, therefore you should have a look at the answers of related code reviews.

In 2006 I wrote a sudoku solver in C using exactly this improvement. You may have a look at it, it should be pretty fast, even when you translate it back to Python.

Since sudokus are popular, several people have already documented how they wrote a sudoku solver. I found this one via Rosetta Code.