# 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.

# Style

Your code mostly follows PEP8 but is a bit more terse. Mostly:

• Using 4 spaces for indentation;
• Putting a space after every coma;
• Using two blank lines to separate top-level functions;

You also use camelCaseVariableNames from time to time, instead of snake_case.

Lastly, using an if __name__ == '__main__' would allow you to more easily test or reuse your module.

# Naming

I find is_sol and derived functions kind of misleading as it does not test if it found a solution (as the name would suggest) but if a number could fit at a given position in the grid. Changing names to use wording such as test, check… and/or fits, find… could improve understanding at a glance.

# Looping

Many times you iterate over indices to retrieve a value in a list. I suggest you have a look at Ned Batchelder's talk loop like a native and try to iterate over the elements directly instead.

You also often use plain-Python for loops where list-comprehensions or generator expresions would faster: any and all are your friends here.

# Copying

Instead of using the slow deepcopy you could leverage the fact that you know your data structure. You use a list of lists, so copy your inner lists into a new outer list. Timings on my machine indicates this is 40x faster:

>>> import timeit
>>> timeit.timeit('deepcopy(mat)', 'from __main__ import mat; from copy import deepcopy')
48.071381973999905
>>> timeit.timeit('[row.copy() for row in mat]', 'from __main__ import mat')
1.1098871960002725


# Proposed improvements

VALID_NUMBERS = range(1, 10)

def fits_in_row(value, grid, row):
return all(element != value for element in grid[row])

def fits_in_column(value, grid, column):
return all(row[column] != value for row in grid)

def fits_in_block(value, grid, row, column):
block_row = (row // 3) * 3
block_column = (column // 3) * 3
return all(
grid[block_row + i][block_column + j] != value
for i in range(3) for j in range(3)
)

def fits_in_cell(value, grid, row, column):
return (
fits_in_row(value, grid, row)
and fits_in_column(value, grid, column)
and fits_in_block(value, grid, row, column)
)

def empty_cells_indices(grid):
return [
(i, j)
for i, row in enumerate(grid)
for j, element in enumerate(row)
if element not in VALID_NUMBERS
]

def sudoku(grid):
to_solve = [(grid, 0)]
empty_cells = empty_cells_indices(grid)

while to_solve:
grid, guessed_cells = to_solve.pop()
if guessed_cells == len(empty_cells):
return grid

row, column = empty_cells[guessed_cells]
for value in VALID_NUMBERS:
if fits_in_cell(value, grid, row, column):
new = [row.copy() for row in grid]
new[row][column] = value
to_solve.append((new, guessed_cells + 1))

if __name__ == '__main__':
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]
# ]

import pprint
pprint.pprint(sudoku(mat))

• Using copy instead of deepcopy is indeed a lot faster. Thanks you so much for the tipps. When I replace the deepcopy with copy in my initial solution, it takes me ~ 1.8s, but using things like "all, any..." seem to make it slower than that. (2.4s). Using only one line return all(element != value for element in grid[row]) looks nice but it seems that something takes longer.. – ndsvw Aug 20 '19 at 11:07
• @ndsvw The code I proposed run in 1.6s on my machine. I will test removing all alls in a bit to check but this seems odd that it runs slower. – 301_Moved_Permanently Aug 20 '19 at 11:11