Backtracking Explained

Analogy categoryAnalogies

Backtracking is what Prolog does when a goal fails, or when more solutions are explicitly requested: it undoes the bindings made since the most recent choice point and resumes the search from there, trying the next untried alternative clause or fact. It is the mechanism that lets a single query produce multiple solutions.

🏏

Cricket analogy: When a captain's first bowling change doesn't get a wicket, they revert to the previous field setting and try a different bowler -- exactly how Prolog backtracks by undoing recent bindings and retrying the last unexplored alternative.

Choice Points and the Search Tree

A choice point is created whenever a goal could be satisfied by more than one clause or fact. Prolog explores the resulting search tree depth-first, and when backtracking is triggered it pops the call stack back to the most recent choice point rather than restarting the entire search from the beginning.

🏏

Cricket analogy: Every over with more than one plausible bowler creates a decision branch a captain could have gone another way on, just as every predicate call with multiple matching clauses creates a Prolog choice point marking an unexplored branch.

prolog

color(red).
color(green).
color(blue).

shape(circle).
shape(square).

combo(Color, Shape) :-
    color(Color),
    shape(Shape).

?- combo(C, S).
C = red, S = circle ;
C = red, S = square ;
C = green, S = circle ;
C = green, S = square ;
C = blue, S = circle ;
C = blue, S = square.

Backtracking Through Conjunctions

In a clause body written as a conjunction of subgoals (G1, G2), if G2 fails after G1 has already succeeded once, Prolog backtracks into G1 to look for another binding before giving up on the whole clause. This right-to-left retry pattern is why predicates like member/2 and append/3 can generate multiple solutions on repeated backtracking.

🏏

Cricket analogy: Testing partnership(X, Y) where X must open the batting and Y must have scored a century means Prolog fixes an X, searches for a matching Y, and backtracks to the next X if none works -- like a selector checking openers until one pairs with a valid partner.

Performance Implications of Backtracking

Unconstrained backtracking, especially over generate-and-test style predicates, can become extremely expensive because Prolog will exhaustively enumerate every combination that earlier goals produce. Nested generate-and-test predicates compound this further, and redundant recomputation on backtracking is one of the most common sources of unexpectedly slow Prolog programs.

🏏

Cricket analogy: Re-bowling every possible field combination from scratch after each failed delivery rather than remembering what's already been tried would waste an entire session -- the same wasted effort naive Prolog backtracking incurs without indexing or cuts to prune dead branches.

Generate-and-test patterns like combo/2 above are combinatorially explosive: with N colors and M shapes, backtracking alone will enumerate all N x M combinations even if only a handful are useful, and nested generate-and-test predicates multiply this cost further. In real programs, use first-argument indexing (automatic in most systems for the first argument), reorder goals so cheap, discriminating checks run before expensive ones, and use cut deliberately once you know no further alternatives are needed -- otherwise a query can silently take exponential time to fail or succeed.

Backtracking undoes bindings made since the last choice point and retries the next untried alternative there.
A choice point is created whenever a goal could be satisfied by more than one clause or fact.
Prolog's search is depth-first: it fully explores one branch before backing off to try a sibling branch.
Within a clause body, if a later subgoal fails, Prolog backtracks into earlier subgoals to look for new bindings before failing the whole clause.
Conjunctive goals (G1, G2) can each retry independently -- when G2 fails, the retry happens by backing into G1.
Unconstrained backtracking over generate-and-test predicates can be combinatorially expensive.
Techniques like first-argument indexing, careful goal ordering, and cut can dramatically reduce wasted backtracking.