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)