< Back




37. Sudoku Solver

We're given an unfinished Sudoku table and we're asked to solve it. This is a normal constraint
satisfaction problem (CSP), and we can solve it using backtracking. First, we gather some information
- the size of the board, and we take the square root of that to get the size of the boxes in the
board.

We define two lambda helper functions, one to get the binary representation of a number we've
selected, and another to get the box where a cell, defined by (row, col), is contained within. We're
using binary to represent what numbers are present in a row, column, or box, and we use bit
manipulation to check if a number is present in a row, column, or box. These bitwise operations are
faster than using sets or some other form of index, and the position of a bit determines the number
or numbers current present in a row, column, or box.

We define two helper functions to fill or empty a box with a number, and another helper function to
check if a number selection is valid for a cell. Finally, we recursively search from (0, 0).

If the location we're at during search is already filled, we skip it. If we're at the end of
the board, we return True. Otherwise, we go to the next column if we're not at the end of the row.
If we're at the end of the row, we go to the next row.

If the location we're at during search is not filled, we try to fill it with a number from 1 to 9. If
the number we've selected is valid, we fill the location with the number, and we recursively search
from the next location. If the recursive search returns True, we return True. Otherwise, we empty the
location and try the next number. Eventually, if we can't find a valid number, we return False - this
will cascade backwards during backtracking as well.

Eventually, we'll have completed our search and the board will be solved.

The solution is as follows:


  class Solution:
      def solveSudoku(self, board: List[List[str]]) -> None:
          N = len(board)
          n = int(N ** (1/2))
          binary = lambda x: 1 << (x - 1)
          box = lambda x, y: (x // n) * n + y // n
          rows, cols, boxes = (
              [0 for _ in range(N)],
              [0 for _ in range(N)],
              [0 for _ in range(N)],
          )

          def fill(row: int, col: int, num: int) -> None:
              rep = binary(num)
              rows[row] ^= rep
              cols[col] ^= rep
              boxes[box(row, col)] ^= rep
              board[row][col] = str(num)

          def empty(row: int, col: int, num: int) -> None:
              rep = binary(num)
              rows[row] ^= rep
              cols[col] ^= rep
              boxes[box(row, col)] ^= rep
              board[row][col] = "."

          def ok(row: int, col: int, num: int) -> bool:
              rep = binary(num)
              return (
                  not rows[row] & rep
                  and not cols[col] & rep
                  and not boxes[box(row, col)] & rep
              )

          def fillNext(row: int, col: int) -> bool:
              if row == N - 1 and col == N - 1:
                  return True
              elif col == N - 1:
                  return backtrack(row + 1, 0)
              else:
                  return backtrack(row, col + 1)

          def backtrack(row: int, col: int) -> bool:
              if board[row][col] != ".":
                  return fillNext(row, col)

              ans = False

              for num in range(1, 10):
                  if ok(row, col, num):
                      fill(row, col, num)
                      ans = fillNext(row, col)

                      if ans:
                          return ans

                      empty(row, col, num)

              return ans

          for i in range(N):
              for j in range(N):
                  if board[i][j] != ".":
                      fill(i, j, int(board[i][j]))

          backtrack(0, 0)


_ Time Complexity:

  O(9^(n^2)) - Where n is the number of rows and columns, our recursive backtracking solution will
  execute this many operations.

_ Space Complexity:

  O(n) - Where n is the number of rows and columns in the board, we use O(n) space for the rows,
  columns, and boxes.