2. The Core Idea (Explore + Undo)
- Why backtracking is an incremental exploration method
- How the algorithm moves forward through choices
- Why invalid branches are abandoned early
- What it means to undo a choice
- How recursion matches the search tree structure
Once the search space is modeled as a tree of partial solutions, the central question becomes: how do we move through that tree efficiently?
The essential idea of backtracking is simple: explore one choice, continue recursively, and undo it if necessary.
2.1 Incremental Construction
Backtracking does not generate full solutions all at once. It builds them step by step.
At each stage, the algorithm extends a partial solution by making one additional decision.
This incremental structure is what makes pruning possible: we can reject a bad direction before completing the whole assignment.
2.2 Explore
To explore means: choose one candidate extension for the current partial solution and descend into the corresponding branch of the search tree.
If the current node is (x₁, …, xᵢ), then exploring corresponds to selecting a value for xᵢ₊₁.
In tree language, this means moving from a node to one of its children.
2.3 Test Early
After making a choice, the algorithm checks whether the new partial solution is still feasible.
If the constraints are already violated, there is no reason to continue deeper into that branch.
2.4 Dead Ends
A branch becomes a dead end when the current partial solution cannot be extended into any valid complete solution.
This may happen because:
- a constraint is violated immediately
- no valid next choice remains
- the branch structure makes completion impossible
At that point, the algorithm stops descending and returns.
2.5 Undo
Undoing a choice means removing the most recent decision and restoring the previous search state.
Conceptually:
This is why the technique is called backtracking: the algorithm goes back to the previous level and tries another option.
2.6 Why Recursion Fits Naturally
The search space has a tree structure, and recursion is the natural mechanism for traversing trees.
Each recursive call corresponds to:
- one node in the search tree
- one partial solution
- one active level of decision-making
Returning from recursion corresponds exactly to undoing the last choice.
2.7 The Full Intuition
The complete mechanism can be summarized as:
- Build a partial solution
- Try one possible next choice
- Test whether the branch is still feasible
- If yes, continue recursively
- If no, undo the choice and try another one
Next: Part 3 — Generic Backtracking Algorithm
Now that the central mechanism is clear, we can move from intuition to formal structure.
In Part 3, we will write the generic backtracking algorithm and identify its standard components: state, choice generation, feasibility test, recursion, and undo step.