title: How to improve this Sudoku Solver?
body: <p>I had an idea a while ago of making a program that would solve a Sudoku board, so I made the code below. The code receives as input a 9x9 integer list, where an incomplete cell is represented by the number 0.</p>
  
  <pre><code>def checkSolutions(grid, i, j):
      """
      Given a Sudoku board and the position of an
      incomplete cell, it returns a list with all
      the possible numbers that this position can occupy.
      """
  
      digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
      solutions = []
  
      solutions1x9 = [grid[x][j] for x in range(9)]
      solutions9x1 = [grid[i][x] for x in range(9)]
  
      rowGrid = i // 3
      columnGrid = j // 3
      solutions3x3 = [grid[i][j] for i in range(3*rowGrid, 3*rowGrid+3)
                      for j in range(3*columnGrid, 3*columnGrid+3)]
  
      solutions = solutions + [i for i in digits if i not in solutions1x9]
      solutions = solutions + [i for i in digits if i not in solutions9x1]
      solutions = solutions + [i for i in digits if i not in solutions3x3]
  
      solutions = list(set(solutions))
      solutions = [i for i in solutions if i not in solutions1x9]
      solutions = [i for i in solutions if i not in solutions9x1]
      solutions = [i for i in solutions if i not in solutions3x3]
  
      return solutions
  
  def checkSudoku(grid):
      """
      Given a Sudoku board, it returns True if it is
      a board that follows the rules of the game and
      returns False otherwise.
      """
  
      digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
      for i in range(9):
          if sorted(grid[i]) != digits:
              return False
  
      for i in range(9):
          column = [grid[j][i] for j in range(9)]
          if sorted(column) != digits:
              return False
  
      for i in range(3):
          for j in range(3):
              grid3x3 = [grid[x][y] for x in range(3*i, 3*i+3)
                      for y in range(3*j, 3*j+3)]
              if sorted(grid3x3) != digits:
                  return False
  
      return True
  
  def sudoku(grid):
      """
      Given an incomplete Sudoku board, it prints on
      the screen the solution of that game.
      """
      for i in range(9):
          for j in range(9):
              if grid[i][j] == 0:
                  solutions = checkSolutions(grid, i, j)
  
                  if len(solutions) == 1:
                      grid[i][j] = solutions[0]
                      continue
  
                  for k in solutions:
                      auxGrid = [x.copy() for x in grid]
                      auxGrid[i][j] = k
                      sudoku(auxGrid)
  
      if checkSudoku(grid):
          print(grid)
  </code></pre>
  
  <p>My problem is: if the function <code>sudoku</code> receives as input the following list</p>
  
  <pre><code>grid1 = [[0, 3, 7, 6, 0, 1, 5, 8, 4],
           [8, 0, 0, 3, 0, 4, 9, 2, 0],
           [6, 0, 9, 2, 5, 0, 3, 7, 1],
           [9, 8, 0, 5, 6, 7, 1, 0, 0],
           [0, 6, 0, 4, 1, 2, 0, 9, 0],
           [0, 0, 1, 8, 3, 9, 0, 6, 5],
           [7, 9, 6, 0, 4, 3, 8, 0, 2],
           [0, 5, 8, 7, 0, 6, 0, 0, 9],
           [1, 2, 4, 9, 0, 5, 6, 3, 0]]
  </code></pre>
  
  <p>it returns the result in less than one second, which is</p>
  
  <pre><code>[[2, 3, 7, 6, 9, 1, 5, 8, 4],
   [8, 1, 5, 3, 7, 4, 9, 2, 6],
   [6, 4, 9, 2, 5, 8, 3, 7, 1],
   [9, 8, 2, 5, 6, 7, 1, 4, 3],
   [5, 6, 3, 4, 1, 2, 7, 9, 8],
   [4, 7, 1, 8, 3, 9, 2, 6, 5],
   [7, 9, 6, 1, 4, 3, 8, 5, 2],
   [3, 5, 8, 7, 2, 6, 4, 1, 9],
   [1, 2, 4, 9, 8, 5, 6, 3, 7]]
  </code></pre>
  
  <p>But if it receives as input the list:</p>
  
  <pre><code>grid2 = [[1, 6, 8, 0, 0, 0, 9, 0, 2],
           [0, 0, 0, 3, 0, 1, 0, 0, 0],
           [0, 3, 0, 6, 2, 0, 0, 0, 0],
           [0, 0, 9, 0, 0, 0, 1, 0, 6],
           [0, 0, 1, 0, 0, 0, 3, 7, 0],
           [0, 4, 3, 5, 0, 0, 0, 0, 9],
           [0, 0, 0, 8, 0, 2, 6, 0, 0],
           [0, 0, 0, 9, 0, 5, 0, 2, 3],
           [2, 0, 6, 0, 3, 0, 7, 0, 0]]
  </code></pre>
  
  <p>it should returns</p>
  
  <pre><code>[[1, 6, 8, 4, 5, 7, 9, 3, 2],
   [5, 7, 2, 3, 9, 1, 4, 6, 8],
   [9, 3, 4, 6, 2, 8, 5, 1, 7],
   [8, 2, 9, 7, 4, 3, 1, 5, 6],
   [6, 5, 1, 2, 8, 9, 3, 7, 4],
   [7, 4, 3, 5, 1, 6, 2, 8, 9],
   [3, 9, 5, 8, 7, 2, 6, 4, 1],
   [4, 1, 7, 9, 6, 5, 8, 2, 3],
   [2, 8, 6, 1, 3, 4, 7, 9, 5]]
  </code></pre>
  
  <p>but the program takes so long to run that I don't even know if it returns something (I waited 30 minutes before closing the code execution). So my doubts are:</p>
  
  <ul>
  <li>is there a mistake in my code for certain input types?</li>
  <li>how can I improve my code to accept entries with more empty cells?</li>
  <li>my code works perfectly fine and is it normal to take longer for entries with more empty cells?</li>
  </ul>
  
  <p>Thanks for any help!</p>