Prolog Tutorial - Search and Backtracking

Search

Introducing Backtracking

Suppose that we have the following database


eats(fred,pears).
eats(fred,t_bone_steak).

eats(fred,apples).

So far we have only been able to ask if fred eats specific things. Suppose that I wish to instead answer the question, "What are all the things that fred eats". To answer this I can use variables again. Thus I can type in the query


?- eats(fred,FoodItem).

As we have seen earlier, Prolog will answer with


FoodItem = pears

This is because it has found the first clause in the database. At this point Prolog allows us to ask if there are other possible solutions. When we do so we get the following.


FoodItem = t_bone_steak

if I ask for another solution, Prolog will then give us.


FoodItem = apples

If we ask for further solutions, Prolog will answer no, since there are only three ways to prove fred eats something. The mechanism for finding multiple solution is called backtracking. This is an essential mechanism in Prolog and we shall see more of it later.

Backtracking in Rules

We can also have backtracking in rules. For example consider the following program.

hold_party(X):-: birthday(X),
happy(X).

birthday(tom).

birthday(fred).

birthday(helen).

happy(mary).

happy(jane).

happy(helen).

If we now pose the query


?- hold_party(Who).

In order to solve the above, Prolog first attempts to find a clause of birthday, it being the first subgoal of birthday. This binds X to tom. We then attempt the goal happy(tom). This will fail, since it doesn't match the above database. As a result, Prolog backtracks. This means that Prolog goes back to its last choice point and sees if there is an alternative solution. In this case, this means going back and attempting to find another clause of birthday. This time we can use clause two, binding X to fred. This then causes us to try the goal happy(fred). Again this will fail to match our database. As a result, we backtrack again. This time we find clause three of birthday, and bind X to helen, and attempt the goal happy(helen). This goal matches against clause 3 of our happy database. As a result, hold_party will succeed with X=helen.

Search Example 1

Consider the following examples.


fun(X) :-              /* something is either fun because its .... */
        red(X),            /* red */

        car(X).            /* and a car */


fun(X) :-              /* or its fun if its.... */

        blue(X),           /* blue */

        bike(X).           /* and a bike */


/* database of red items */

red(apple_1).

red(block_1).

red(car_27).


/* database of cars */

car(desoto_48).

car(edsel_57).

This program says that red cars or blue bikes are fun. It then goes on to name some examples of each type of object.

Search Example 2

Let's now ask what is a fun item. To do this we first must enter the following query


?- fun(What).

We first attempt to prove something is fun. To do this we have two clauses of fun that we can use


/* clause 1 */
fun(X) :-

        red(X),

        car(X).

/* clause 2 */

fun(X) :-

        blue(X),

        bike(X).

Using the first clause, we can now look to see if we can find some red object

Search Example 3

First let's retrieve a red object from the red database


/* database of red items */
red(apple_1).      first choice

red(block_1).

red(car_27).

The first red item that we find is apple_1. This gives us the instantiation X=apple_1. Next we have to see if this is a car, so we ask the question car(apple_1). Does this match with our existing database of facts about cars?


/* database of cars */
car(desoto_48).

car(edsel_57).

The answers is that it will not. apple_1 will not match with desoto_48 or with edsel_57. So what do we do next? In such cases, Prolog backtracks in order to find another solution. Thus we go back to the red database, and see if we can find another possible solution. In this case we can


red(apple_1).     
red(block_1).      second choice 

red(car_27).

We can use the next clause and see if block_1 is a red car.

Search Example 4

Returning to our cars database, again block_1 will not match against desoto_48 or with edsel_57. In this case we must backtrack a second time to see if there is another red item that we can find. This time we find the third clause in the database, and use that.


red(apple_1).     
red(block_1).

red(car_27).     third choice

We now attempt the car goal again, but this time for car_27. Now recall what we said earlier about the dangers of over estimating the powers of Prolog. Prolog will try to match the goal car(car_27) against the database


car(desoto_48).
car(edsel_57).

This will fail. car_27 does not match with either desoto_48 or edsel_57. Although the programmer probably meant car_27 to mean car number 27 to be a car, Prolog has no way of gleaning this intended semantics, and fails the call based on a simple pattern match.

Well, what do we do now? The first step is to go back and see if there are any more possible red items. Well we have now exhausted all three choices, hence there are no more red items to choose from. Given that there are no more possible ways that we could satisfy clause 1, we now move on to clause 2, as we see on the next card.

Search Example 5

Let us recall our program. It said that something was fun if it was red and a car or blue and a bike. Well, we couldn't find something that was both red and a car, so we now see if something blue and a bike. Let's recap the code:

/* clause 1 */
fun(X) :-    we've tried this clause but without luck

        red(X),

        car(X).

/* clause 2 */

fun(X) :-   so lets have a go with this clause now

        blue(X),

        bike(X).

Thus we will now try to prove that something is fun, by trying to find something that is blue, using the blue database:

/* database of blue items */
blue(flower_3).

blue(glass_9).

blue(honda_81).

In this case we now choose blue(flower_3)

Search Example 6

We now have to prove the goal bike(flower_3) against our bike database:

bike(iris_8).
bike(my_bike).

bike(honda_81).

This again must fail, since flower_3 does not match against iris_8, my_bike, or honda_81. So as before, we must backtrack and find an alternate blue item. Recall our database:


blue(flower_3).
blue(glass_9).

blue(honda_81).

We have tried flower_3 without luck, so next we try the second blue fact, blue(glass_9). We now try goal bike(glass_9). Again this fails to unify. As a result we must go back yet again and find another blue object. This time we will use the third clause of blue, blue(honda_81). We will now give us the goal bike(honda_81). This matches clause three!. So at last we have found something which is blue and a bike. As a result we can now conclude that it is fun, Prolog then displays the following:


?- fun(What).
What=honda_81

yes

Search Exercises

Exercise 6

Consider the goal ?- fun(What)


fun(X) :-              /* fun if .... */                       
        red(X),        /* red */                    

        car(X).            /* and a car */      
       
fun(X) :-              /* or its fun if its.... */    

        blue(X),           /* blue */                   

        bike(X).           /* and a bike */

Below you will see pairs of goals. These may either be output of a goal e.g. red(my_hat) or calls to another goal e.g. car(my_hat).

Indicate which of the following goals you you would expect to see first, for the above query, by checking the button beside it:


/* database of red  & blue items */
red(cricket_ball).        blue(cheese).       

red(my_hat).              blue(raleigh).        

red(car_27).              blue(honda).        

                                               

/* database of cars  and bikes*/             

car(peugot).              bike(yamaha).        

car(rover).               bike(raleigh).     

                          bike(honda).

Exercise 7

Consider the following program.


a(X):-
     b(X), c(X), d(X).

a(X):-

     c(X), d(X).

a(X):-

     d(X).


b(1).                             

b(a).                            

b(2).

b(3).

d(10).

d(11).

c(3).

c(4).

Given the query ?- a(X). Indicate in the box below the successive variable bindings that the variable X gets when the above query is run, and all solutions are asked for (by using ;). NB you should list even those bindings which do not lead to overall success, and you should list each answer even if it occurs more than once.

Separate bindings by a comma (ie. 1,3,5.....), and don't use any spaces in your answer.

This is the end of the search topic.

Next Topic

Return to Introduction Menu