How does Prolog search and backtrack?
Prolog answers a question by searching. When a choice leads nowhere, it goes back and tries the next one. This is called backtracking.
It matters because backtracking is how Prolog solves puzzles, plans routes and checks rules. In this lesson you watch it work, then list every route through a small bus network.
By the end of this lesson
Note
I can explain how Prolog searches for answers and backtracks to try another.
Key words
| Word | What it means | Example |
|---|---|---|
| List | items in order, in square brackets | [a, b, c] |
| Head | the first item of a list | |
| Tail | the list that is left when the head is taken off | |
| Choice point | a place where more than one fact or rule could be used | |
| Backtracking | going back to the last choice point and trying the next option |
The cells students fill in are left blank in this preview.
A list has a head and a tail
A list holds items in order, inside square brackets: [a, b, c]. Prolog splits a list into its head, the first item, and its tail, everything else.
The pattern [H|T] matches any list that has at least one item. H becomes the head and T becomes the tail. The empty list [] has neither.
Worked example: splitting lists
| List | Head | Tail |
|---|---|---|
| [a, b, c] | a | [b, c] |
| [7] | 7 | [] |
| [] | none | none |
| [[1, 2], 3] | [1, 2] | [3] |
The cells students fill in are left blank in this preview.
Split a list into head and tail
docker exec prolog swipl -q -g "[H|T] = [a, b, c], writeln(H), writeln(T)" -t haltShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Every way to cut a list in two
docker exec prolog swipl -q -g "forall(append(X, Y, [1, 2]), (write(X), write(' + '), writeln(Y)))" -t haltShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Prolog goes back when a choice fails
The goal member(X, [4, 8, 15, 16]) means "X is one of these". There are four ways to answer it. Prolog takes the first, 4, and carries on with the rest of the question.
If a later step fails, Prolog goes back to the last choice point and takes the next option. It keeps going until a choice works or the options run out.
Worked example: look for a member above 10
| Try | X is | Is X above 10? | What Prolog does |
|---|---|---|---|
| 1 | 4 | No | Goes back, takes the next member |
| 2 | 8 | No | Goes back, takes the next member |
| 3 | 15 | Yes | Carries on and stops with 15 |
The cells students fill in are left blank in this preview.
Watch the tries happen
docker exec prolog swipl -q -g "member(X, [4, 8, 15, 16]), write(tried(X)), nl, X > 10, writeln(found(X))" -t haltShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Backtracking can list every route on a map
Here is a one-way bus network with five stops. A route is a list of stops from a start to an end, with no stop visited twice.
The rule trip says: the trip from a stop to itself is just that stop. Otherwise take a link, check the next stop is not yet visited, and make a trip from there.
The map file: links and the trip rule
link(a, b).
link(a, c).
link(b, d).
link(c, d).
link(d, e).
trip(Y, Y, _, [Y]).
trip(X, Y, Seen, [X|Rest]) :-
link(X, Z),
\+ member(Z, Seen),
trip(Z, Y, [Z|Seen], Rest).
Save the map file
docker exec prolog sh -c "printf '%s\n' 'link(a, b).' 'link(a, c).' 'link(b, d).' 'link(c, d).' 'link(d, e).' 'trip(Y, Y, _, [Y]).' 'trip(X, Y, Seen, [X|Rest]) :- link(X, Z), \+ member(Z, Seen), trip(Z, Y, [Z|Seen], Rest).' > map.pl"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Every route from a to e
docker exec prolog swipl -q -g "findall(P, trip(a, e, [a], P), L), writeln(L)" -t halt map.plShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Every route from e to a
docker exec prolog swipl -q -g "findall(P, trip(e, a, [e], P), L), writeln(L)" -t halt map.plShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: the search from a to e
| Step | At | Choice taken | What happens |
|---|---|---|---|
| 1 | a | link to b | Route so far: a, b |
| 2 | b | link to d | Route so far: a, b, d |
| 3 | d | link to e | Reached e. Route one: a, b, d, e |
| 4 | d, b | no other links | Goes back to a |
| 5 | a | link to c | Then c, d, e. Route two: a, c, d, e |
| 6 | a | no links left | The search is finished |
The cells students fill in are left blank in this preview.
A common mistake
Warning
Many people think Prolog looks at every route at once. It follows one route at a time, in the order the facts are written. It goes back only when a choice fails or you ask for more. If the map has a loop, a route can circle for ever unless the rule remembers the stops it has seen.