Skip to content
Work Free practice Coding course Blog Method Results Why me About Enquire Book a call

Coding · Backtracking

Understanding the problem

Lesson · 8 min read · Backtracking

Generate and test

Place n queens on an n × n board so that none attacks another. The most direct program chooses n squares out of n², then checks whether the chosen queens attack each other. Every candidate is built completely before it is judged.

A little thought removes most of those candidates: two queens in one row always attack, so choose one column per row instead. Better, but it still builds every complete board before looking at it. Backtracking goes further and checks each queen the moment it is placed.

nAny n squaresOne per row, then checkQueens placed by backtrackingSolutions
41,820256162
61,947,79246,6561524
84,426,165,36816,777,2162,05692

The difference is not a constant factor. A partial board that already has two queens attacking each other can never be completed, and every one of its completions is skipped the moment the conflict appears.

Choose, explore, undo

Backtracking builds a solution one decision at a time. After each decision it asks: can this partial solution still be completed? If not, it abandons the branch, undoes the last decision and tries the next option. If so, it goes one decision deeper.

Three things decide how well it runs:

  • The order of decisions. Decide the most constrained thing first; for queens, rows in order.
  • How early a failure is detected. A check on the partial solution that fails sooner prunes more. Sorting the input often creates such a check, as below.
  • Exact undo. The state after undo must equal the state before the choice. Most bugs are an undo that restores almost everything.

Subsets of [3, 5, 6] summing to 9. Because the list is sorted, one overshoot rules out every later number in that branch.

  1. Step 1 / 8
    nums (sorted)
    305162
    sum3

    Try adding 3: [3] sums to 3.

  2. Step 2 / 8
    nums (sorted)
    305162
    sum8

    Try adding 5: [3, 5] sums to 8.

  3. Step 3 / 8
    nums (sorted)
    305162
    sum8

    Adding 6 to [3, 5] would make 14 > 9. The list is sorted, so every later number overshoots too: prune the rest of this branch.

  4. Step 4 / 8
    nums (sorted)
    305162
    sum9

    Try adding 6: [3, 6] sums to 9.

  5. Step 5 / 8
    nums (sorted)
    305162
    sum9

    [3, 6] sums to 9: a solution.

  6. Step 6 / 8
    nums (sorted)
    305162
    sum5

    Try adding 5: [5] sums to 5.

  7. Step 7 / 8
    nums (sorted)
    305162
    sum5

    Adding 6 to [5] would make 11 > 9. The list is sorted, so every later number overshoots too: prune the rest of this branch.

  8. Step 8 / 8
    nums (sorted)
    305162
    sum6

    Try adding 6: [6] sums to 6.

When the search becomes dynamic programming

If you only need the number of solutions and different paths reach the same situation, the search repeats itself. Counting sign patterns that hit a target is an example: many prefixes produce the same running total at the same index, and the number of ways to finish does not depend on how you got there. Memoise on (index, running total) and the exponential search becomes a table.

Ask two questions of any search: can I detect failure earlier, and do states repeat? The first makes backtracking faster; the second turns it into dynamic programming.