Backtracking

Prerequisites

• Recursion.
• DFS: backtracking is DFS on a tree of choices.
• Arrays.

The analogy

How it works

The three moves: choose an option for the next decision, explore recursively, and un-choose it when you come back, so the next option starts from a clean state.

Start with 4 queens by hand

One queen per row. Try columns 1 to 4 in order; a column is safe if no earlier queen shares its column or a diagonal. Predict, then open "Check".

Finish the picture: why pruning matters

Compare blind enumeration with backtracking on 4 queens.

• Blind enumeration. Predict how many complete placements (one queen per row) you'd check.
  Check

  $4^4 = 256$, testing each full board only at the end.

• Backtracking. Predict why it checks far fewer.
  Check

  A clash is detected as soon as it happens, so whole subtrees are cut: after (1, 1), (2, 2) is rejected immediately, along with the 16 boards that start that way.

The rule in plain words

Build the solution one decision at a time (here: one row at a time). For each option, check the constraints against the decisions so far.

If the option is valid, take it and recurse; when the recursion returns, undo it and try the next option. If no option works, return to let the previous decision change.

The code

Read this code after you have placed the queens by hand. It will make more sense.

int safe(int col[], int row, int c) {           /* can a queen go at (row, c)? */
    for (int r = 0; r < row; r++)
        if (col[r] == c || col[r] - c == row - r || c - col[r] == row - r)
            return 0;                           /* same column or diagonal */
    return 1;
}

int solve(int col[], int row, int n) {          /* returns the number of solutions */
    if (row == n) return 1;                     /* all queens placed */
    int count = 0;
    for (int c = 0; c < n; c++)
        if (safe(col, row, c)) {
            col[row] = c;                       /* choose */
            count += solve(col, row + 1, n);    /* explore */
        }                                       /* next c overwrites col[row]: un-choose */
    return count;
}

graph TD
  R["empty board"] --> A["row 1: col 1"]
  R --> B["row 1: col 2"]
  A --> A3["row 2: col 3"]
  A --> A4["row 2: col 4"]
  A3 --> X1["row 3: no safe column ✗"]
  B --> B4["row 2: col 4"]
  B4 --> B41["row 3: col 1"]
  B41 --> S["row 4: col 3 ✓"]
          

How fast is it?

With one queen per row and per column, the full search space is $n!$ placements, and pruning explores only a fraction of it:

For $n = 8$: $8^8 \approx 16.8$ million boards, $8! = 40{,}320$ permutations, and backtracking visits about 2,000 partial boards to find all 92 solutions. The worst case is still exponential.

Common mistakes

• Forgetting to undo a choice (when state is shared), so later branches see stale decisions.
• Checking constraints only at the end instead of at each step, losing all the pruning.
• Missing the diagonal test: two queens attack diagonally when |row difference| = |column difference|.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Backtracking is DFS over choices because it extends one partial solution as deep as possible before trying alternatives.
• Pruning saves time because one early clash removes every solution that would extend it.
• Choices must be undone because the next option must start from the same state as the first.
• The worst case is exponential because pruning can't always cut enough of the search space.
• The diagonal test uses |Δrow| = |Δcolumn| because that's exactly when two squares share a diagonal.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is backtracking like walking through a maze?
   Sample answer

   At each junction you choose a path; at a dead end you walk back to the last junction and try the next path.

2. Walk through the start of 4-queens: rows 1 and 2, and the first dead end.
   Sample answer

   Row 1 takes column 1, row 2 takes column 3 (the first safe one); row 3 then has no safe column, so we backtrack and move row 2 to column 4.

3. Why does safe compare col[r] - c and c - col[r] with row - r?

   A good answer describes a diagonal.

   Sample answer

   Two squares are on the same diagonal when the column difference equals the row difference in either direction; the two comparisons cover both diagonals.

4. So what is backtracking, in one sentence?
   Sample answer

   Building a solution choice by choice and abandoning (undoing) a partial solution as soon as it breaks a constraint.

5. Why is backtracking much faster than trying every full board?

   A good answer mentions whole subtrees.

   Sample answer

   A clash found after two queens rules out every board that starts with those two queens, so huge parts of the search space are never visited.

6. What is the worst-case cost of backtracking?
   Sample answer

   Still exponential, bounded by the size of the search space (such as $n!$ for $n$-queens); pruning usually makes it far smaller in practice.

7. How does the code "un-choose" a queen?
   Sample answer

   It overwrites col[row] with the next column in the loop, and later rows only read entries for rows above them, so the old value never interferes.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the search-space numbers and subset sum. I'd keep the maze analogy, the 4-queens trace with one dead end, and "choose, explore, un-choose; prune early".

External resources

• GeeksforGeeks: Backtracking: n-queens, sudoku, subset sum and more.
• Wikipedia: Backtracking: the general method and examples.
• Wikipedia: Eight queens puzzle: history and solution counts.

Videos

• YouTube search: n-queens backtracking: pick a walkthrough with the board.