Skip to content
LumenaryAcademy
Foundations 55 min

Backtracking and search

How Prolog actually finds answers, depth first, left to right, backing up on failure, and how to collect, count and steer the search.

Code tested · 3AI-draftedAwaiting review by a computer scientist
MotivationH

Where do the answers come from?

In the first two lessons, answers appeared as if by magic: ask grandparent(G, ada) and Prolog produces Amara, then Obi, then false. There is no magic. Prolog follows one simple, fixed strategy for exploring the possibilities your clauses describe, and once you can follow that strategy in your head you can predict the order of answers, see why a program is slow, and see why another never stops.

The strategy is depth-first search with backtracking. Whenever Prolog has a choice (several clauses that might match a goal), it takes the first, remembers that the others exist, and carries on. When it reaches a dead end (a goal that cannot be satisfied), it goes back to the most recent choice it made, undoes everything since, and takes the next option. That going back is backtracking. It is the same idea a person uses to solve a maze by keeping one hand on the wall, and the same idea behind many search algorithms in other languages, except that in Prolog you get it for free with every predicate.

DefinitionsH

The execution model

To run a query, Prolog keeps a list of goals still to prove, starting with the query's goals in order. It repeats one step:

  1. Take the leftmost goal.
  2. Find the first clause, from the top of the program, whose head unifies with it. If other clauses might also match, leave a choice point to come back to.
  3. Replace the goal by that clause's body (nothing, for a fact), with the bindings from unification applied.
  4. If the goal list becomes empty, report an answer. If no clause matches a goal, backtrack: return to the most recent choice point, undo the bindings made since it, and try its next clause.

When the user (or forall, or findall) asks for another answer, Prolog backtracks exactly as if the last answer had failed. When no choice points remain, there are no more answers, and the toplevel says false.

Definition— Choice point

A saved position in the search: a goal, the clauses still untried for it, and the state of the variables, to which Prolog returns on backtracking.

Logicians call this procedure SLD resolution; the search space it explores is the search tree (or SLD tree). Two rules fix the shape of the search: goals are tried left to right, and clauses top to bottom. The logical meaning of a program does not depend on these orders, but its behaviour (the order of answers, its speed, and whether it terminates) depends on them entirely.

Some predicates you will use with search:

PredicateWhat it does
member(X, List)True for each element X of List, one per backtrack
between(Low, High, X)True for each integer X from Low to High
forall(Cond, Action)True if Action succeeds for every solution of Cond
findall(T, Goal, List)List of T for every solution of Goal; [] if none
bagof(T, Goal, List)Like findall, but fails if there are none, and groups by free variables
setof(T, Goal, List)Like bagof, with the list sorted and duplicates removed
aggregate_all(count, Goal, N)Counts solutions (also sum, max, bag, set; SWI-Prolog library)
Worked examplesH

Watching the search

A search you can see

This program builds meals from a starter and a main course, with a test on the lengths of their names (atom_length/2 gives the number of characters, and =< compares numbers; lesson 5 covers arithmetic). Messages printed inside the rule show the order in which Prolog tries things:

prolog
:- initialization(main, main).

% A tiny menu: which dishes can a guest choose?
starter(soup).
starter(salad).

main_course(curry).
main_course(paella).
main_course(tagine).

% A meal is a starter and a main course whose names are not too long
% together; the trace messages show the order of the search.
meal(S, M) :-
    starter(S),
    format("  try starter ~w~n", [S]),
    main_course(M),
    format("    try main ~w~n", [M]),
    atom_length(S, LS),
    atom_length(M, LM),
    LS + LM =< 10,
    format("      accept ~w + ~w~n", [S, M]).

main :-
    format("All meals:~n"),
    forall(meal(S, M), format("=> ~w with ~w~n", [S, M])).
text
All meals:
  try starter soup
    try main curry
      accept soup + curry
=> soup with curry
    try main paella
      accept soup + paella
=> soup with paella
    try main tagine
      accept soup + tagine
=> soup with tagine
  try starter salad
    try main curry
      accept salad + curry
=> salad with curry
    try main paella
    try main tagine
meal(S, M)S = soupS = saladcurrypaellataginecurrypaellatagineanswer 1answer 2answer 3answer 4failsfails
The search tree of meal(S, M). Prolog explores it depth first, left to right. Each leaf is either an answer (the numbers give their order) or a failure, after which Prolog backtracks to the nearest choice point above.

Follow the trace with the tree. starter(S) has two matching facts, so it leaves a choice point and takes soup. main_course(M) leaves another and takes curry. The test passes, the rule succeeds, and forall prints the meal and then asks for another answer, which makes Prolog backtrack to the most recent choice point: main_course, which offers paella. Only when all three main courses are used up does Prolog back up further, to starter, and take salad. With salad, the test fails for paella and tagine (5 + 6 = 11 characters), so those branches produce no answer, and the trace shows no accept line for them.

Notice also what the trace does not show: after try main paella under salad, Prolog did not go back and retry the starter first. Backtracking always returns to the latest choice, never to an arbitrary one.

Tracing the search

You do not have to add format calls to see the search: SWI-Prolog has a tracer that reports every step. Each goal is pictured as a box with four ports: Call (the goal is first tried), Exit (it succeeded), Redo (backtracking has come back into it for another solution) and Fail (it has no more solutions). This four-port model, devised by Lawrence Byrd in 1980, is used by nearly every Prolog debugger.

Here is a trace of a cut-down menu with two starters, two main courses and the test atom_length(S, 5) (a five-letter starter), started at the toplevel with leash(-all) (do not stop at each port) and then trace, meal(S, M):

text
   Call: (13) meal(_30446, _30448)
   Call: (14) starter(_30446)
   Exit: (14) starter(soup)
   Call: (14) main_course(_30448)
   Exit: (14) main_course(curry)
   Call: (14) atom_length(soup, 5)
   Fail: (14) atom_length(soup, 5)
   Redo: (14) main_course(_30448)
   Exit: (14) main_course(paella)
   Call: (14) atom_length(soup, 5)
   Fail: (14) atom_length(soup, 5)
   Redo: (14) starter(_30446)
   Exit: (14) starter(salad)
   Call: (14) main_course(_30448)
   Exit: (14) main_course(curry)
   Call: (14) atom_length(salad, 5)
   Exit: (14) atom_length(salad, 5)
   Exit: (13) meal(salad, curry)
S = salad,
M = curry

The numbers in brackets are call depths, and names like _30446 are SWI-Prolog's internal names for unbound variables (they differ from run to run). Read the Fail and Redo lines together: after atom_length(soup, 5) fails, the very next event is a Redo of the most recent goal that still has alternatives. In the interactive tracer you step with Enter, skip over a call with s and leave with a; gtrace opens a graphical version.

Generate and test, and why the order of goals matters

Many problems can be solved by generating candidate answers and testing them. Colouring a map so that neighbours differ is the classic example. Here are two versions of the same program for five countries of East Africa:

prolog
:- initialization(main, main).

colour(red).
colour(green).
colour(blue).

% colouring(Map): a list Country-Colour in which no two neighbours share
% a colour (Kenya, Uganda, Tanzania, Rwanda and Burundi).
colouring([kenya-K, uganda-U, tanzania-T, rwanda-R, burundi-B]) :-
    colour(K), colour(U), dif_colour(K, U),
    colour(T), dif_colour(K, T), dif_colour(U, T),
    colour(R), dif_colour(U, R), dif_colour(T, R),
    colour(B), dif_colour(R, B), dif_colour(T, B).

dif_colour(X, Y) :- X \== Y.

% The same problem as pure generate-and-test: choose everything, then check.
colouring_slow([kenya-K, uganda-U, tanzania-T, rwanda-R, burundi-B]) :-
    colour(K), colour(U), colour(T), colour(R), colour(B),
    K \== U, K \== T, U \== T, U \== R, T \== R, R \== B, T \== B.

main :-
    colouring(Map),
    format("First colouring: ~w~n", [Map]),
    aggregate_all(count, colouring(_), N),
    format("Number of colourings: ~w~n", [N]),
    aggregate_all(count, colouring_slow(_), N2),
    format("Same count by generate-and-test: ~w~n", [N2]),
    aggregate_all(count, (colour(_), colour(_), colour(_), colour(_), colour(_)), C),
    format("Complete candidates generate-and-test examines: ~w~n", [C]).
text
First colouring: [kenya-red,uganda-green,tanzania-blue,rwanda-red,burundi-green]
Number of colourings: 6
Same count by generate-and-test: 6
Complete candidates generate-and-test examines: 243

Both versions are logically the same, and both find the 6 colourings. But colouring_slow generates every complete assignment of three colours to five countries, 35=2433^5 = 243 of them, before testing any, while colouring tests each constraint as soon as both of its countries have colours. When Kenya and Uganda are both red, the fast version rejects that pair at once and never generates the 27 completions that start that way; the slow version builds all 27 and rejects each one at the end. With five countries the difference is small; with fifty countries, 3503^{50} is about 7×10237 \times 10^{23} candidates, which at a billion a second would take millions of years. Test as early as you can is the first rule of efficient search in Prolog. Lesson 7 goes further: constraint programming makes the system do this pruning automatically.

Search in a graph, and collecting answers

Finding routes in a network is search in its purest form. A route must not visit a city twice, or the search could go round a cycle forever, so the program carries a list of the cities visited so far (\+ member(...) means "is not a member"; lesson 5 explains \+):

prolog
:- initialization(main, main).

% link(A, B): a direct train between A and B in a made-up network.
link(lisbon, porto).
link(lisbon, madrid).
link(porto, madrid).
link(madrid, barcelona).
link(madrid, lyon).
link(barcelona, lyon).
link(lyon, geneva).

% Trains run both ways.
connected(A, B) :- link(A, B).
connected(A, B) :- link(B, A).

% route(From, To, Route): Route is a list of cities from From to To
% that never visits a city twice.
route(From, To, Route) :-
    walk(From, To, [From], Reversed),
    reverse(Reversed, Route).

walk(To, To, Visited, Visited).
walk(From, To, Visited, Route) :-
    connected(From, Next),
    \+ member(Next, Visited),
    walk(Next, To, [Next|Visited], Route).

main :-
    findall(R, route(lisbon, geneva, R), Routes),
    length(Routes, N),
    format("~w routes from lisbon to geneva:~n", [N]),
    forall(member(R, Routes), format("  ~w~n", [R])),
    findall(Len-R, (member(R, Routes), length(R, Len)), Pairs),
    msort(Pairs, [Best-Shortest|_]),
    format("Shortest has ~w cities: ~w~n", [Best, Shortest]),
    setof(City, R^route(porto, City, R), Reachable),
    format("Reachable from porto: ~w~n", [Reachable]),
    forall(bagof(To, link(From, To), Tos),
           format("Links from ~w: ~w~n", [From, Tos])),
    findall(X, link(geneva, X), None),
    format("findall with no answers: ~w~n", [None]),
    (   bagof(X, link(geneva, X), _)
    ->  true
    ;   format("bagof with no answers fails~n")
    ).
text
4 routes from lisbon to geneva:
  [lisbon,porto,madrid,barcelona,lyon,geneva]
  [lisbon,porto,madrid,lyon,geneva]
  [lisbon,madrid,barcelona,lyon,geneva]
  [lisbon,madrid,lyon,geneva]
Shortest has 4 cities: [lisbon,madrid,lyon,geneva]
Reachable from porto: [barcelona,geneva,lisbon,lyon,madrid,porto]
Links from barcelona: [lyon]
Links from lisbon: [porto,madrid]
Links from lyon: [geneva]
Links from madrid: [barcelona,lyon]
Links from porto: [madrid]
findall with no answers: []
bagof with no answers fails

The details reward attention:

  • walk/4 builds the route backwards, adding each new city to the front of the list, and route/3 reverses it at the end. Adding to the front of a list is cheap; lesson 4 explains why.
  • The four routes come out in depth-first order: the search goes through Porto before trying Lisbon's second link, Madrid. Depth-first search does not find the shortest route first. To get it, this program collects every route, pairs each with its length, and sorts with msort/2, which keeps duplicates and sorts Length-Route pairs by length first. For large graphs you would use a breadth-first search instead.
  • setof(City, R^route(porto, City, R), Reachable) collects every city reachable from Porto, sorted and without repeats. The R^ says "for some route R": without it, setof would give a separate answer for every different route.
  • bagof(To, link(From, To), Tos) leaves From free, so it groups: one solution per value of From, each with that city's links. forall prints them all. findall never groups; it collects everything into one list.
  • With no solutions at all, findall gives [], while bagof and setof fail. Choose whichever behaviour your program needs.
Common misconceptionsH

When the search never ends

The commonest Prolog bug is a query that never finishes. Here is a definition that is logically correct (A reaches B if A reaches some C and C links to B) but written with the recursive goal first:

prolog
link(lisbon, porto).
link(porto, madrid).

reachable(A, B) :- reachable(A, C), link(C, B).
reachable(A, B) :- link(A, B).

The query reachable(lisbon, X) takes the first clause, whose first goal is reachable(lisbon, C), which takes the first clause again, and again, forever, without ever reaching a link fact. SWI-Prolog eventually runs out of stack and reports something like this (the program was saved as loop.pl; the exact numbers vary from run to run):

text
ERROR: [Thread main] /w/loop.pl:1: user:main Stack limit (1.0Gb) exceeded
ERROR: [Thread main]   Stack sizes: local: 0.9Gb, global: 48.4Mb, trail: 0Kb
ERROR: [Thread main]   Stack depth: 6,340,532, last-call: 0%, Choice points: 6,340,525
ERROR: [Thread main]   Probable infinite recursion (cycle):
ERROR: [Thread main]     [6,340,532] user:reachable(lisbon, _120)
ERROR: [Thread main]     [6,340,531] user:reachable(lisbon, _140)

This is left recursion: a predicate that calls itself as its first goal with no progress made. The fix is to make progress before recursing, and to put the base case first:

prolog
reachable(A, B) :- link(A, B).
reachable(A, B) :- link(A, C), reachable(C, B).

That version terminates on a graph without cycles. On a graph with cycles it can still loop, which is why the route program carries a visited list. Lesson 7 shows a third solution, tabling, which lets Prolog run even the left-recursive version correctly.

Misconception

"Prolog finds the best answer first." It finds answers in the order its depth-first search reaches them, which depends on clause and goal order. If you want the shortest or cheapest, compute it explicitly.

Misconception

"Clause order and goal order do not matter in a logic language." They do not change what is true, but they change which answers come first, how much work the search does and whether it terminates at all.

Misconception

"findall and bagof are the same." findall treats free variables as "anything" and returns [] when there are no answers; bagof groups by free variables (unless you mark them with ^) and fails when there are no answers. setof is bagof plus sorting and removing duplicates.

Exercises

Exercises

Try each question before opening the hints. Every answer about program output was checked by running the program with SWI-Prolog 10.1.

1. Backtracking and search

Warm-upComputational

How many answers does meal(S, M) have in the lesson's menu program?

2. Backtracking and search

CoreComputational

Suppose the two starter/1 facts are swapped, so that starter(salad). comes before starter(soup). What is the first answer of meal(S, M)? Answer in the form salad with curry.

3. Backtracking and search

Warm-upComputational

What list does setof(X, member(X, [b, a, b]), L) bind L to? (findall would give [b,a,b].)

4. Backtracking and search

Warm-upComputational

Which values of X satisfy between(1, 5, X), X mod 2 =:= 0? List them separated by commas.

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

5. Backtracking and search

CoreComputational

Three countries all border each other. With the lesson's three colours and the rule that neighbours differ, how many colourings are there? (Count them as aggregate_all(count, ...) would.)

6. Backtracking and search

CoreHuman

Which definition of ancestor/2 makes the query ancestor(amara, X) run forever (until the stack overflows)?

Choose one

7. Backtracking and search

StretchHuman

Which statements are true? Choose all that apply.

Choose all that apply

Further reading and resources