Backtracking Problems

[!TIP] War Story: The Database Query Planner Early in my career, I was tasked with optimizing a database query planner. The planner had to evaluate thousands of potential join orders to find the fastest execution path. At first, we tried generating every possible combination (a brute-force approach), but the system would run out of memory for complex queries. The breakthrough came when we implemented Backtracking with Pruning. We realized that if a partial join order was already slower than our best known complete path, any subsequent joins on that path would only make it worse. By immediately abandoning those paths (“backtracking”), we reduced query planning time from minutes to milliseconds. This same fundamental pattern applies to solving Sudoku, routing delivery trucks, and placing N-Queens.

[!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

Board Size (N):

Ready to solve.

3. The Backtracking Template

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

Java

Go

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);
    }
  }
}

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?