Divide and conquer chops, greedy bets, dynamic programming remembers. But there are problems where none of that is enough: constraint problems, where the solution is a combination of decisions that must be mutually compatible — assigning drivers to shifts, squaring timetables, generating valid inspection routes — and where no recurrence or greedy criterion will do. For them there is the module's fourth strategy: backtracking, a systematic exploration of the solution space that advances decision by decision and, as soon as it detects a dead end, undoes the last step and tries another alternative. It is the most expensive of the four strategies — its cost is exponential in the worst case — but, well pruned, it solves problems at which the others just shrug. With it we will close the module by comparing the four design strategies face to face.

1. The idea: exploring a decision tree with going back
2. The general scheme: choose, explore, undo
3. RutaBus example: assigning drivers to shifts with incompatibilities
4. Pruning: why it matters so much
5. N-Queens: the compact classic
6. Backtracking vs brute force vs DP — and the four strategies face to face
7. The exponential cost

Imagine you build the solution in stages: first decision, second decision, third... Each possible sequence of decisions is a branch of a decision tree; the leaves are complete candidate solutions. Brute force generates all the leaves and checks which ones are valid. Backtracking is smarter:

• It traverses the tree depth-first, taking one decision at a time (the recursion stack from 01-02 and 02-02 keeps track of the current path).
• At each node it checks whether the partial solution can still lead to a valid solution. If it can't, it prunes: it abandons that entire branch without generating it.
• When a node's alternatives run out, it backtracks to the previous node and tries the next option.

The difference with greedy is radical: greedy takes a decision and never comes back; backtracking always reserves the right to regret. The difference with brute force is the pruning: combinations whose failure is already guaranteed halfway through construction are never examined.

Almost every backtracking is written with the same three-beat template. It is worth memorizing:

Let's comment on the key pieces:

• is_complete: the equivalent of the recursion's base case (01-02). Here a complete solution does not stop the algorithm: it is recorded and the search continues for others (unless we only want one: then we can return True and propagate the cutoff).
• is_valid: the pruning function. It checks constraints over the partial solution; the earlier it detects infeasibility, the more tree is saved.
• append / pop: the sacred pair. Everything the "choose" step modifies, the "undo" step must restore exactly. We work on a single shared structure (reference, not copy — remember 02-02) that is woven and unwoven as we go.
• The state of the path lives in the call stack: on returning from the recursion we are, automatically, one level up the tree.

The problem. Tomorrow RutaBus must cover the three shifts of line L1 — Morning, Evening and Night — with its three staff drivers: Anna, Bruno and Carla. Each driver does exactly one shift, but there are availability constraints:

• Anna cannot do the night shift (family care).
• Bruno cannot do the morning one (he finishes today at 23:00: legally required rest).
• Carla cannot do the evening one (mandatory training).

We want all the valid assignments (planning needs alternatives in case someone falls ill).

Implementation details that separate a correct backtracking from a treacherous one:

• solutions.append(dict(assignment)): we store a copy. If we stored the reference, the later del would empty it — the classic copies-vs-references mistake of 02-02.
• The decision at each level is "which driver does shift k": the tree has depth 3 (one per shift) and up to 3 branches per node.
• The pruning is double: driver already busy (free) and the availability constraint (compatible).

The complete search tree, with the prunings marked:

Follow the right branch with your finger: after assigning Morning=Carla and Evening=Bruno, the only free driver for Night is Anna — but Anna doesn't do nights. The branch dies, the algorithm undoes Evening=Bruno, tries the next alternative (there are none left), undoes Morning=Carla... and since there are no options left at the root either, it finishes with the 2 solutions found. That backing-up movement is literally the execution of the del assignment[shift] upon returning from the recursion.

Without pruning, we would have generated the 3! = 6 complete permutations and discarded 4. Here the saving is modest; with 20 shifts and 20 drivers, 20! ≈ 2.4 × 10¹⁸ permutations make the difference between "impossible" and "instant" — if the prunings cut early.

Pruning is the difference between backtracking and combinatorial suicide. Two principles:

• Prune as early as possible. A constraint checked at level 2 eliminates entire subtrees; the same constraint checked at the leaf eliminates only one leaf. That is why is_valid operates on the partial solution, not the complete one.
• Order the decisions to fail early. It pays to decide the most constrained variable first (the shift with the fewest possible drivers): failures surface high in the tree, where pruning is cheap. It is an ordering heuristic; it doesn't change correctness.

Let's be honest: pruning does not change the worst case. An adversary can craft instances where almost nothing gets pruned. Backtracking belongs to the O(2ⁿ)/O(n!) family of the hierarchy of 01-03, and no pruning gets it out of there in general; what pruning does is make it practicable on real instances, which are rarely adversarial.

The N-Queens problem — placing N queens on an N×N board so that none attacks another (same row, column or diagonal) — is the "hello world" of backtracking, and we can afford it here because it belongs to no other module. Decision per level: in which column does the queen of row k go.

Note the representation trick: storing only the column per row eliminates at the root the row conflicts (each row has exactly one queen) — choosing the partial solution's structure well is itself a form of pruning. For n = 8, brute force over the 8⁸ ≈ 16.7 million placements (or the 8! = 40,320 permutations, with the good representation) comes down to about ~2,000 nodes explored with pruning: that is the order of magnitude of the saving.

First the direct duel:

The rule of thumb: if you can define a subproblem and a recurrence, DP turns the exponential tree into a polynomial table — do it. Backtracking is for when the states don't repeat or can't be summarized (each partial solution is unique, like a concrete assignment of drivers): there, there is nothing to memoize and all that remains is to search intelligently.

And the module's closing — the four strategies face to face:

Faced with a new RutaBus problem, this is the recommended interrogation order: a provable greedy? (the cheapest); if not, is there a recurrence with overlap? (DP); does it split into independent halves? (divide and conquer); none of the above but there are checkable constraints? (backtracking). And if not even that, perhaps it's time for a heuristic assumed as such — like our veteran supervisor_route.

Let's analyze backtracking with the tools of Module 2. In the worst case, the decision tree has branching factor b (alternatives per level) and depth n (decisions): up to bⁿ nodes. For permutation-style assignments, the unpruned tree has n! leaves. It is the summit of the hierarchy of 01-03, the zone where adding one element multiplies the time.

• Time: O(bⁿ) or O(n!) in the worst case, multiplied by the cost of is_valid at each node (keep it cheap: ideally O(1) or O(n) as in N-Queens!).
• Space: surprisingly modest — O(n) for the partial solution plus O(n) of recursion stack (02-02). Backtracking does not store the tree: it walks it. That is why it can attack astronomical search spaces with pocket-sized memory.
• The best and average case (02-03) depend brutally on the prunings and the exploration order: two correct implementations of the same problem can differ by factors of thousands. In backtracking, the engineering of the pruning is the performance.

• Undoing halfway. If "choose" touches two structures (the assignment and a set of busy drivers), "undo" must restore both. Any asymmetry silently corrupts the following branches. Check that every append/add/assignment has its mirror pop/remove/del.
• Storing references instead of copies. solutions.append(assignment) stores an object that will keep mutating; in the end you'll have a list of empty or all-identical solutions. Copy (dict(assignment), some_list[:]) when recording — the subtlety of 02-02 striking again.
• Pruning late. Checking validity only at the leaves turns backtracking into brute force with extra steps. Ask yourself which constraints you can evaluate with the solution halfway built.
• Forgetting the return after recording. Without the return upon completing the solution, the loop keeps "extending" an already-complete solution, with index errors or ghost solutions.
• Recomputing is_valid from scratch. In N-Queens, is_valid is O(n); maintaining sets of occupied columns and diagonals brings it down to O(1) per query in exchange for some memory — the trade-off of 02-02, once again. (And it adds two more structures that choose/undo must keep in mirror.)
• Using backtracking where there is a recurrence. If you detect repeated subproblems, you are paying an exponential price for something DP solves in polynomial time. Review the comparison table before writing a single line.

A fourth shift ("Reinforcement") and a fourth driver ("David") join, with these additional constraints: David can only do Reinforcement or Night, and Bruno cannot do Reinforcement either. Adapt assign_shifts (updating the constants is enough) and compute by hand, drawing the tree, how many valid solutions there are. Then check with the code.

Write inspection_routes(network, origin, k) that generates all the inspection routes of exactly k stops starting at origin, without repeating a stop, moving only between connected stops. The network is an adjacency dictionary, for example:

In n_queens, the function is_valid walks over the queens already placed: O(n) per check. Rewrite the algorithm keeping three sets — occupied columns, row − col diagonals and row + col diagonals — so that the check is O(1). Don't forget the choose/undo mirror over the three sets.

Solution 1

New constants:

Tree: for Morning only Anna or Carla fit. (a) Morning=Anna → Evening ∈ {Bruno} (Carla doesn't do evenings, David doesn't either) → Night ∈ {Carla, David}: with Night=Carla we are left with Reinforcement=David ✔; with Night=David we are left with Reinforcement=Carla ✔. (b) Morning=Carla → Evening ∈ {Anna, Bruno}. With Evening=Anna → Night ∈ {Bruno, David}: Night=Bruno leaves Reinforcement=David ✔; Night=David leaves Reinforcement=Bruno ✘ (Bruno doesn't do reinforcements: prune and backtrack). With Evening=Bruno → Night ∈ {David} (Anna doesn't do nights) → Reinforcement=Anna ✔. Total: 4 solutions. If your manual count differs from the code, the code wins — and the exercise becomes finding the branch you miscounted.

Solution 2

The three-beat template, intact; only the candidates change (neighbors in the network) and the pruning (no repeats). The neighbor not in route is an O(k) list search (the hidden cost from 02-01); with a parallel set it would drop to O(1). This function is, moreover, our first exploration of the RutaBus network as a graph — a seed of what is coming in Module 4.

Solution 3

The "descending" diagonals share the value row − col and the "ascending" ones the value row + col; three O(1) set lookups replace the O(n) loop. The price: four structures that choose/undo must keep perfectly synchronized — check that every add has its remove.

Backtracking completes our repertoire: build the solution in stages, prune the branches with no future and undo to explore alternatives, with the choose–explore–undo template as universal skeleton and the mirror discipline (everything done gets undone) as the golden rule. We have applied it to RutaBus's driver assignment, to the inspection routes over the network — our first walk through it as a graph — and to the classic N-Queens, and we have accepted its nature: exponential cost in the worst case, which only the quality of the prunings makes practicable. With this, Module 3 is complete: divide and conquer for independent subproblems, greedy for provably safe local decisions, dynamic programming for overlapping subproblems with a recurrence, and backtracking for constraints that demand searching with going back — four molds, four diagnostic questions, and the judgment of Module 2 to subject to analysis any design that comes out of them. In Module 4 we will bring in the harvest: the classic algorithms born from these strategies — binary search and the merge sort and quick sort orderings as children of divide and conquer, Dijkstra as the greedy that is optimal, Floyd-Warshall as dynamic programming on graphs — implemented and analyzed piece by piece, starting with the jewel of logarithmic efficiency: binary search.