Backtracking Problems

[!NOTE] Backtracking is a brute-force approach that incrementally builds candidates for a solution and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot lead to a valid solution.

1. The Maze Analogy

Imagine you are in a maze. You reach a fork with three paths: Left, Straight, Right.

  1. You choose Left. You walk for a bit and hit a dead end.
  2. You Backtrack to the fork.
  3. You choose Straight. You hit another dead end.
  4. You Backtrack to the fork.
  5. You choose Right. This path leads to the exit.

This is exactly how backtracking algorithms work. They explore the “State Space Tree” using Depth-First Search (DFS).

2. N-Queens Problem: A Classic Duel

Goal: Place N queens on an N × N chessboard such that no two queens attack each other. Constraint: No two queens can share the same row, column, or diagonal.

Interactive Visualizer

Watch how the algorithm tries to place a queen row by row. When it places a queen that causes a conflict, the board turns red, and it backtracks to try a different position.

N-Queens Visualizer

Ready to solve.

3. The Backtracking Template

Almost all backtracking problems can be solved using this standard template:

Java

void backtrack(Candidate candidate) {
  // 1. Base Case: Success
  if (isSolution(candidate)) {
    output(candidate);
    return;
  }

  // 2. Iterate through all possible next steps
  for (Step nextStep : getCandidates(candidate)) {
    if (isValid(nextStep)) {
      // 3. Choose
      place(nextStep);

      // 4. Explore (Recurse)
      backtrack(nextStep);

      // 5. Un-choose (Backtrack)
      remove(nextStep);
    }
  }
}

Go

func backtrack(candidate Candidate) {
  // 1. Base Case: Success
  if isSolution(candidate) {
    output(candidate)
    return
  }

  // 2. Iterate through all possible next steps
  for _, nextStep := range getCandidates(candidate) {
    if isValid(nextStep) {
      // 3. Choose
      place(nextStep)

      // 4. Explore (Recurse)
      backtrack(nextStep)

      // 5. Un-choose (Backtrack)
      remove(nextStep)
    }
  }
}

4. Pruning: The Secret Weapon

The power of backtracking comes from Pruning. If we realize early that a partial solution cannot possibly work (e.g., placing a queen in a column that is already attacked), we stop exploring that branch immediately. This saves massive amounts of computation compared to checking every single combination.

Constraint Satisfaction Problems (CSP)

Backtracking is the go-to algorithm for CSPs, such as:

  • Sudoku Solvers
  • Crossword Generators
  • Graph Coloring
  • Cryptarithmetic Puzzles

5. Deep Dive Strategy Lab: Backtracking Problems

Intuition Through Analogy

Think of this chapter like trying all lock combinations safely. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?