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

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

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.