Sudoku Solver - Backtracking Approach

Introduction

The Sudoku Solver is a classic problem that demonstrates the power of Backtracking. Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids (also called "boxes") contains all of the digits from 1 to 9.

From a computer science perspective, Sudoku is a Constraint Satisfaction Problem (CSP). Backtracking is the ideal algorithmic paradigm for this because it allows us to build a solution incrementally, try partial assignments, and undo them (backtrack) when they lead to a dead end.

The Backtracking Algorithm

Backtracking works by exploring all possible configurations of a solution. The process follows a depth-first search (DFS) pattern:

1. Find an Empty Cell: Locate the next cell in the grid that is empty (represented by . or 0).
2. Try Digits 1-9: Attempt to place a digit (1 through 9) into the empty cell.
3. Validate: Check if the placement is valid according to Sudoku rules (no duplicate in row, column, or 3x3 box).
4. Recurse: If valid, place the digit and recursively call the solver for the next empty cell.
5. Backtrack: If the recursive call returns false (meaning the current path leads to no solution), reset the cell to empty and try the next digit.
6. Base Case: If no empty cells remain, the puzzle is solved.

Key Components

1. Finding the Empty Cell

We need a helper function to scan the board. Since we are filling cells sequentially from top-left to bottom-right, we can simply iterate through the grid to find the first ..

2. Validation Logic (isValid)

This is the most critical part. Before placing a number num at position (row, col), we must ensure it doesn't violate any constraints:

• Row Check: Ensure num is not already present in board[row].
• Column Check: Ensure num is not already present in board[i][col] for all i.
• Box Check: Ensure num is not already present in the 3x3 subgrid. To find the box boundaries:
• startRow = row - row % 3
• startCol = col - col % 3

3. The Recursive Solver

The solver function returns a boolean (true if solved, false if stuck). It orchestrates the flow described in the algorithm section above.

Implementation (TypeScript)

function solveSudoku(board: string[][]): boolean {
  return solve(board);
}

function solve(board: string[][]): boolean {
  // Step 1: Find the next empty cell
  let row = -1;
  let col = -1;
  let isEmpty = true;

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] === '.') {
        row = i;
        col = j;
        isEmpty = false;
        break;
      }
    }
    if (!isEmpty) break;
  }

  // Base Case: If no empty cell is found, the puzzle is solved
  if (isEmpty) return true;

  // Step 2: Try digits 1 through 9
  for (let num = 1; num <= 9; num++) {
    const numStr = num.toString();

    // Step 3: Check if placing num is valid
    if (isValid(board, row, col, numStr)) {
      // Step 4: Place the number
      board[row][col] = numStr;

      // Step 5: Recurse to solve the rest
      if (solve(board)) {
        return true; // Propagate success
      }

      // Step 6: Backtrack - Reset the cell if recursion failed
      board[row][col] = '.';
    }
  }

  // Trigger backtracking
  return false;
}

function isValid(board: string[][], row: number, col: number, num: string): boolean {
  // Check Row
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num) return false;
  }

  // Check Column
  for (let x = 0; x < 9; x++) {
    if (board[x][col] === num) return false;
  }

  // Check 3x3 Box
  const startRow = row - row % 3;
  const startCol = col - col % 3;

  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (board[i + startRow][j + startCol] === num) return false;
    }
  }

  return true;
}

Complexity Analysis

Time Complexity: O(9^(N*N))

In the worst-case scenario (e.g., an empty board), the algorithm explores all possible permutations of numbers in the grid. Since there are 9 choices for each of the 81 cells, the complexity is exponential. However, pruning (the isValid check) drastically reduces the search space in practice.

Space Complexity: O(N*N)

The space complexity is determined by the recursion stack. In the worst case, the recursion depth can go up to the number of cells (81), so the space complexity is O(N*N) where N is the grid size (9).

Optimization: Bitmasking

The isValid function runs in O(1) time (constant time) because the grid size is fixed (9x9). However, we can optimize the memory usage and potentially the speed by using Bitmasks instead of strings or arrays to track used numbers in rows, columns, and boxes.

Instead of scanning the row/col/box to check for duplicates, we maintain three 9x9 integer matrices (or 1D arrays of length 9) representing the bitmask of used numbers.

• Bit 0 represents if '1' is used.
• Bit 1 represents if '2' is used, and so on.

When placing a number num, we set the corresponding bit in the row, column, and box masks. When backtracking, we clear the bit. This reduces the validation check to a simple bitwise AND operation, which is extremely fast.

Common Mistakes to Avoid

1. Not Resetting the Cell: Forgetting to set board[row][col] = '.' after a failed attempt is the most common bug. This prevents the algorithm from trying other numbers in that cell.
2. Inefficient Validation: Checking the entire row and column every time can be optimized, though for 9x9 it is negligible. Always ensure the 3x3 box logic uses the correct modulo arithmetic.
3. Base Case Confusion: Ensure the base case is triggered only when no empty cells remain. If you trigger it when you find an empty cell, the recursion will never terminate.

Real-World Applications

While Sudoku is a puzzle, the backtracking algorithm is foundational in:

• Scheduling: Assigning tasks to time slots or resources without conflicts.
• Route Planning: Finding paths in a graph where certain constraints must be met.
• Puzzle Solving: Crosswords, N-Queens problem, and Word Search.
• Constraint Programming: Used in AI for solving complex logical constraints.