Solving Sudoku with backtracking

Question

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 than what I started 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 or 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))

• greybeard: see also: speed up backtracking sudoku solver
• dfhwze: You can use a backtracking algorithm that is considerably faster than brute force: Knuth's Algorithm X. I wrote one in another language just the other week: codereview.stackexchange.com/questions/226317/….

Answer 1

Style

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

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

should ease reading your code.

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 expressions would be 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. Timing on my machine indicates that 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))

• hardfork: 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..
• 301_Moved_Permanently: @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.

Answer 2

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.