PROBLEM

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells.

Solution 1: Original Approach (Brute Force Backtracking)

Approach

1. Backtracking algorithm:

• Traverse the board cell by cell and row by row.
• For each empty cell ('.') check if any number from ('1' to '9') is valid to place in the board through following restrict:
  • Row Check: Ensure the number isn't already in the current row.
  • Column Check: Ensure the number isn't already in the current column.
  • Subgrid Check: Ensure the number isn't already in the current 3x3 subgrid.
• If valid, place the number and move to the next cell (recursive call).
• If a number placement leads to a valid solution, return True.
• If no number works, backtrack by resetting the cell to '.'.

2. Base Case: If row == 9, all rows have been processed, and the solution is complete.
3. Recursive Step: If col == 9, move to the next row (row + 1, col = 0).

Complexity

• Time complexity: O(9^81)

• There are 81 cells, and each can have 9 possible numbers in the worst case.
• However, pruning via is_valid reduces the number of possibilities significantly.

• Space complexity: O (81)

Code

class Solution:
      def solveSudoku(self, board: List[List[str]]) -> None:
      def is_valid(row:int, col: int, num):
        #CHECK ROW
        for i in range(9):
          if board[row][i] == num:
            return False
          if board[i][col] == num:
            return False

          if board[3*(row//3) + i//3][3*(col//3) + i%3] == num:
            return False
        return True
        
          
      def backtrack(row, col):
        if row == 9:
          return True
        if col == 9: # increase row to 1 and reset col
          return backtrack(row+1, 0)
        
        if board[row][col] == '.':
          for i in '123456789':
            if is_valid(row,col, i):
              board[row][col] = i
              if backtrack(row, col+1):
                return True
              else:
                board[row][col] = '.'
          return False
        else:
          return backtrack(row, col+1)
        
      backtrack(0,0)

Solution 2: Optimized Approach (Using Sets)

Initiation:

• Follow the solution1
• Instead using three lists of sets to track used number instead of check check valid position every time.

Complexity

• Time complexity: $$O(9^m)$$ - m is number of empty cells
• Space complexity: O(81)

Code

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        # Initialize sets with existing board values
        for r in range(9):
            for c in range(9):
                if board[r][c] != ".":
                    rows[r].add(board[r][c])
                    cols[c].add(board[r][c])
                    boxes[3 * (r // 3) + c // 3].add(board[r][c])

        def is_valid(r, c, num):
            return (
                num not in rows[r]
                and num not in cols[c]
                and num not in boxes[(r // 3) * 3 + c // 3]
            )

        def backtracking(row, col):
            if row == 9:
                return True
            if col == 9:
                return backtracking(row + 1, 0)

            if board[row][col] == ".":
                for i in "123456789":
                    if is_valid(row, col, i):
                        board[row][col] = i
                        rows[row].add(i)
                        cols[col].add(i)
                        boxes[3 * (row // 3) + col // 3].add(i)

                        if backtracking(row, col + 1):
                            return True

                        board[row][col] = "."
                        rows[row].remove(i)
                        cols[col].remove(i)
                        boxes[3 * (row // 3) + col // 3].remove(i)

                return False
            else:
                return backtracking(row, col + 1)

        backtracking(0, 0)