Sudoku Solver Using Backtracking in DSA Typescript - Time & Space Complexity

Time Complexity: Sudoku Solver Using Backtracking

O(9^n)

Understanding Time Complexity

We want to understand how the time needed to solve a Sudoku puzzle changes as the puzzle size or difficulty changes.

Specifically, how the backtracking method explores possibilities and how that affects the time it takes.

Scenario Under Consideration

Analyze the time complexity of the following Sudoku solver using backtracking.

function solveSudoku(board: number[][]): boolean {
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === 0) {
        for (let num = 1; num <= 9; num++) {
          if (isValid(board, row, col, num)) {
            board[row][col] = num;
            if (solveSudoku(board)) return true;
            board[row][col] = 0;
          }
        }
        return false;
      }
    }
  }
  return true;
}

This code tries numbers 1 to 9 in empty cells and uses recursion to fill the board step-by-step.

Identify Repeating Operations

Look at what repeats most in this code.

• Primary operation: Trying numbers 1 to 9 in each empty cell and checking if the number fits.
• How many times: Potentially for every empty cell, and for each number, the function calls itself recursively to try the next cell.

How Execution Grows With Input

Imagine the puzzle has n empty cells.

Input Size (empty cells n)	Approx. Operations
10	Up to 9^10 tries (about 3.5 billion)
20	Up to 9^20 tries (very large, trillions)
40	Up to 9^40 tries (astronomically large)

Pattern observation: The number of tries grows exponentially as the number of empty cells increases.

Final Time Complexity

Time Complexity: O(9^n)

This means the time needed can grow very fast, roughly nine times more work for each extra empty cell.

Common Mistake

[X] Wrong: "The solver always tries all 9 numbers for every empty cell."

[OK] Correct: The solver stops trying numbers as soon as it finds a valid one that leads to a solution, so it often tries fewer than 9 numbers per cell.

Interview Connect

Understanding this exponential growth helps you explain why backtracking can be slow and why pruning or smarter checks matter.

It shows your grasp of how recursive search explores many possibilities and how complexity grows with input size.

Self-Check

"What if we used a heuristic to pick the next empty cell with the fewest valid options? How would the time complexity change?"