2
\$\begingroup\$

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))
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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;

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 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))
\$\endgroup\$
  • \$\begingroup\$ 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.. \$\endgroup\$ – ndsvw Aug 20 at 11:07
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – 409_Conflict Aug 20 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.