Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 40 ยท Unification and Backtracking

Prolog Backtracking: Choice Points, Retry and Generate-and-Test

Understand backtracking in Prolog: how choice points and the trail let the system undo bindings and retry alternatives, with fail loops, generate-and-test and findall.

Backtracking is Prolog's way of searching. When a goal fails, Prolog does not give up: it goes back to the last place where it had a choice, undoes everything it did since, and tries a different alternative. Almost every non-trivial Prolog program relies on this, sometimes without the programmer noticing. In this lesson you will see exactly what happens and how to use it deliberately.

Prolog is read-only on this site. Runnable examples use the Python mini-Prolog stand-in, whose solver is built on Python generators: asking a generator for its next value is the same as asking Prolog to backtrack.

Choice points and the trail

Whenever Prolog selects a goal and more than one clause could match, it records a choice point: "if things go wrong later, come back here and try the next clause". It also records, on a stack called the trail, every variable it binds after that point.

When a goal fails:

  1. Prolog finds the most recent choice point.
  2. It undoes all bindings recorded after it (popping the trail), restoring the variables to the state they had at that point.
  3. It resumes with the next untried alternative.
  4. If there is no choice point left, the whole query fails.

This is chronological backtracking: the last decision is revised first.

A trace by hand

PROLOG
num(1). num(2). num(3).

?- num(X), X > 1.
  1. num(X) matches the first clause. X = 1. A choice point remains (two clauses left).
  2. X > 1 becomes 1 > 1: fails.
  3. Backtrack: undo X = 1; take the second clause. X = 2.
  4. 2 > 1 succeeds. The query succeeds with X = 2.
  5. If you press ;, Prolog backtracks again: X = 3 (also > 1). The next ; finds nothing more: false.
flowchart LR
    A["num(X)"] -->|"X = 1"| B["1 > 1 ?"]
    B -->|"fail"| A
    A -->|"X = 2"| C["2 > 1 ?"]
    C -->|"ok: answer X = 2"| D["success"]
    D -.->|"press ;"| A
    A -->|"X = 3"| E["3 > 1: answer X = 3"]

Failure sends control back to the previous choice point.

Forcing backtracking with fail

fail is a goal that never succeeds, so it always triggers backtracking. This lets you visit every solution:

PROLOG
?- between(1, 3, X), write(X), nl, fail.
1
2
3
false.

Each time fail is reached, Prolog backs into between/3, which gives the next number, write prints it, and so on. When between/3 has no more values, the query fails and prints false. This is a failure-driven loop. forall(Generator, Action) is the tidy version, and findall/3 collects instead of printing:

PROLOG
?- findall(X, (member(X, [1, 2, 3, 4]), X mod 2 =:= 0), Evens).
Evens = [2, 4].

Side effects are not undone

Backtracking restores variable bindings. It does not undo output or changes to the database:

PROLOG
?- member(X, [a, b]), write(X), nl, X == b.
a
b
X = b.

The first iteration printed a and then X == b failed, so Prolog backtracked into member/2; the a that had been printed stays on the screen. The same applies to assert (adding facts) and to file writes. That is why side effects inside code that backtracks need care.

Generate and test

The most direct use of backtracking is generate and test: one goal generates candidates, the following goals test them. Prolog explores the combinations automatically.

PROLOG
n(1). n(2). n(3). n(4). n(5). n(6). n(7). n(8). n(9). n(10).

pair_sum(A, B, Sum) :- n(A), n(B), A < B, A + B =:= Sum.
PROLOG
?- pair_sum(A, B, 7).
A = 1, B = 6 ;
A = 2, B = 5 ;
A = 3, B = 4 ;
false.

For A = 1 the engine tries B = 1, 2, ..., 10 and keeps those where the tests pass; then it backs into A for A = 2. Nested loops, with no loop syntax. The cost is proportional to the number of candidates, so smart programs prune early. Compare A < B placed right after both are bound (as above) with leaving all tests to the end.

Python Generate and test: Pythagorean triples (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The engine finds (3,4,5), (5,12,13) and (6,8,10). Behind the scenes it tested thousands of combinations; you wrote three lines.

Watching the retries

Turn on the stand-in's trace to see the same story as the hand trace above. Each Call: line is a goal being tried. When a test like 1>1 fails, the engine returns to the generator and the next Call: num(...) result appears with a different value.

Python Backtracking trace (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the trace top to bottom. num(_X) is called once; the comparison goals 1>1, 2>1, 3>1 follow because the solver yields each match in turn and tests it.

Backtracking into earlier goals

Backtracking can retry any earlier goal that has choice points left, not only the one right before the failing goal. In a(X), b(Y), c(X, Y), if c fails, Prolog first retries b(Y) for another Y. Only when b runs out of alternatives does it go back to a(X), undo Y, and retry a with the next X. Think of it as an odometer: the last goal turns fastest.

Controlling backtracking

Sometimes you want less backtracking, because you know there is only one correct answer, or because retrying would repeat work. The tools:

  • once(Goal): take the first solution and discard the choice points.
  • ( If -> Then ; Else ): commit to the first solution of If.
  • The cut !: discard all choice points created since the clause began. It is powerful and easy to misuse, so it is treated carefully in chapter 5.
  • Better program design: if clauses are mutually exclusive, first-argument indexing leaves no choice point at all.

Prefer pure, backtracking-friendly code first and add control only for efficiency or for predicates that really must be deterministic.

Common mistakes

  • Expecting printed output or assert effects to disappear on backtracking.
  • Writing a generator after the test, so the test runs with an unbound variable.
  • Forgetting fail or forall, and printing only the first answer.
  • Missing a base case, so the retrying never ends.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does Prolog do when a goal fails?

    Chronological backtracking revises the last decision first.
  2. 2. What is the purpose of the goal fail?

    fail never succeeds, so Prolog backtracks into earlier goals; this makes failure-driven loops.
  3. 3. Which things does backtracking NOT undo?

    Only bindings made after the choice point are restored; output and database changes stay.
  4. 4. In pair_sum(A, B, S) :- n(A), n(B), A < B, A + B =:= S., why is A < B useful?

    Testing as soon as the variables are bound cuts off useless branches and prevents (2,5) and (5,2) both appearing.

Summary

  • Prolog records choice points and a trail of bindings; on failure it undoes back to the last choice point and tries the next alternative.
  • fail, forall/2 and findall/3 use backtracking to visit all solutions.
  • Side effects are not undone.
  • Generate-and-test puzzles are expressed as generators followed by tests, ordered so tests prune early.
  • once/1, if-then-else and the cut reduce backtracking when you need determinism.

Next: Tracing and Debugging