backtracking as DFS over partial solutions

Picture solving a maze without a map. You walk forward making choices at each junction; when you hit a dead end, you do not start over — you step back to the last junction with an untried path and try that instead. That step back is backtracking. As an algorithm, backtracking builds a solution one decision at a time, and the moment a partial choice cannot possibly lead anywhere good, it undoes that last choice and tries the next option.

Concretely, backtracking is depth-first search over partial solutions. A partial solution is a solution built only partway — say the first three positions of a permutation, or the first two queens placed. The algorithm is recursive: if the partial solution is complete, record it; otherwise, for each candidate value of the next decision, check whether adding it keeps the partial solution feasible; if so, add it, recurse to make the remaining decisions, and on return remove it (undo) so the next candidate can be tried in a clean state. This explores a tree whose nodes are partial solutions and whose leaves are complete candidates, going deep before wide — exactly DFS. The make-recurse-undo skeleton is the same across N-queens, subset-sum, graph coloring, and constraint problems; only the feasibility check changes.

The whole point, and the reason backtracking beats blind enumeration, is that the feasibility check lets you abandon a partial solution before extending it — pruning away an entire subtree of candidates in one stroke. If the first two queens already attack each other, you never place the other queens at all, skipping all the leaves below. In the worst case backtracking is still exponential (it can degrade to full enumeration when nothing prunes), but on real, constrained instances the pruning often slashes the explored tree to a tiny fraction, which is what makes it practical.