Backtracking in Prolog

In the process of backtracking, we will go back to the previous goal, and after that, we will try to find another way to satisfy the goal. In this section, we will give two detailed ways to satisfy a sequence of goals using the process of backtracking and unification.

For example:

The following example shows a family relationship between a group of people. In the following clauses, the mother/2 predicate defines 10 facts, father/2 predicate defines the 9 facts, and parent/2 predicate defines the 6 clauses.

Facts are as follows:

The above facts mean that ‘jessica is the mother of chris’ and ‘josh is the father of chris’, respectively. In the above example, we added [M1] labels only for reference purposes. These labels are not part of clauses.

The following diagram shows the facts of the following example. Here, f stands for father.

Example:

Given query

?- parent(josh, Child), write(‘The child is ‘), write(Child), nl.

In this, Prolog tries to satisfy all sequence of goals. Firstly, for variable Child, Prolog finds one or more possible values. It starts with the first goal parent(josh, Child). Prolog tries to unify the first goal with the head of each clause, which defines the predicate parent/2 in turn. To unify this, Prolog works from top to bottom. Clause [P1] and [P2] firstly search, but Prolog fails to match the goal with either of them. Now, Prolog searches the clause [P3], and this time Prolog is successful in unifying the goal with the clause’s head, with A is bound to josh, and variable B is bound to variable Child.

In the body of rule [P3], Prolog works through the goals and trying to succeed the goal in turn. The goals write(‘mother?’), and nl is successfully evaluated by Prolog and then produce the following line of text as output:

mother?  

Now Prolog comes to the third goal, that is mother(josh, B). But this third goal is not unified with the head of any clauses [M1] to [M10], which defines the predicate mother/2. So, the third goal fails.

Now the Prolog system backtracks. In the body of clause [P3], Prolog goes back to the most recently satisfying goal. It works from right to left. The most recent satisfy goal is nl, and we will try to satisfy it.  

The n1/0 built-in predicate is unsatisfiable, that means when we evaluate it while backtracking, it always fails.

Now in the body of [P3], Prolog moves to the left and finds the goal write(‘mother?’). But this goal always fails because the write/1 predicate is also unsatisfiable.

In the body of rule [P3], there are no goals available, working from left to right. So, rule [P3] is rejected by the Prolog system. Now we have the following:

In this case, the most recently evaluated goal is parent(josh, Child), and we will try to satisfy this goal.

Now Prolog goes back to the most recently evaluated previously goal, which is parent(josh, Child), and then we try to satisfy this goal. To find the clauses that define the predicate parent/2, Prolog searches the database from the point it has reached previously, i.e., [P3] clause. Firstly, it examines the [P4] clause and successfully unifies the goal with its head. Variable X is bound to josh, and variable Y is bound to variable Child.

In the body of rule [P4], Prolog works through the goals and trying to succeed the goal in turn. The first two goals of Rule [P4] succeed by Prolog and produce the following line of text as output:

father?  

Now Prolog attempts to satisfy the third goal, that is father(josh, Y). Prolog searches the clauses and finds that clause that defines the father/2 predicate in turn. The search works from top to bottom.

The system finds the first clause [F2], and it is a fact. Now, the variable Y is bound to haley. Variable Y is bound to variable Child so, variable Child is also bound to atom haley.

In the body of rule [P4], there are two further goals, i.e., write(‘father!’) and nl. They both succeed and produce the following line of text as output:

father!  

Now in the body of rule [P4], all the goals have succeeded, so the head of the clause, i.e., parent(josh, haley) succeeds. Therefore, in the user’s query, the goal parent(josh, Child) succeeds.

In the sequence, the first goal has been satisfied, which is entered by the user. In the sequence, there are three more goals, i.e., write(‘The child is ‘), write(Child), and nl. They all succeed and produce the following line of text as output:

The child is haley  

In the user’s query, all the goals have been successfully satisfied. The Prolog system outputs the value of all variables, which are used in the query.

?- parent(josh, Child), write('The child is '), write(Child), nl.  mother?  father?  father!  The child is haley  Child = haley