Prolog Tutorial - Search and Backtracking Introducing BacktrackingSuppose that we have the following databaseeats(fred,pears).eats(fred,tbonesteak).eats(fred,apples).So far we have only been able to ask if fred eats specific things. Supposethat I wish to instead answer the question, 'What are all the things thatfred eats'. To answer this I can use variables again. Thus I can type inthe query?- eats(fred,FoodItem).As we have seen earlier, Prolog will answer withFoodItem = pearsThis is because it has found the first clause in the database. At thispoint Prolog allows us to ask if there are other possible solutions. Whenwe do so we get the following.FoodItem = tbonesteakif I ask for another solution, Prolog will then give us.FoodItem = applesIf we ask for further solutions, Prolog will answer no, since there areonly three ways to prove fred eats something.
The mechanism for findingmultiple solution is called backtracking. This is an essential mechanismin Prolog and we shall see more of it later.Backtracking in RulesWe can also have backtracking in rules. For example consider thefollowing program.holdparty(X):- birthday(X),happy(X).birthday(tom).birthday(fred).birthday(helen).happy(mary).happy(jane).happy(helen).If we now pose the query?- holdparty(Who).In order to solve the above, Prolog first attempts to find a clause ofbirthday, it being the first subgoal of birthday. This binds X to tom.
Wethen attempt the goal happy(tom). This will fail, since it doesn't matchthe above database. As a result, Prolog backtracks.
This means thatProlog goes back to its last choice point and sees if there is analternative solution. In this case, this means going back and attemptingto 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). Againthis 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, andattempt the goal happy(helen). This goal matches against clause 3 of ourhappy database. As a result, holdparty will succeed with X=helen.Search Example 1Consider 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(apple1).red(block1).red(car27)./. database of cars./car(desoto48).car(edsel57).This program says that red cars or blue bikes are fun.
It then goes on toname some examples of each type of object.Search Example 2Let's now ask what is a fun item. To do this we first must enter thefollowing query?- fun(What).We first attempt to prove something is fun. To do this we have two clausesof 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 redobjectSearch Example 3First let's retrieve a red object from the red database/. database of red items./red(apple1). First choicered(block1).red(car27).The first red item that we find is apple1. This gives us theinstantiation X=apple1. Next we have to see if this is a car, so weask the question car(apple1). Does this match with our existingdatabase of facts about cars?/. database of cars./car(desoto48).car(edsel57).The answers is that it will not.
Apple1 will not match with desoto48 orwith edsel57. So what do we do next? In such cases, Prolog backtracks inorder to find another solution.
Thus we go back to the red database, andsee if we can find another possible solution. In this case we canred(apple1).red(block1). Second choicered(car27).We can use the next clause and see if block1 is a red car.Search Example 4Returning to our cars database, again block1 will not match againstdesoto48 or with edsel57. In this case we must backtrack a second timeto see if there is another red item that we can find. This time we findthe third clause in the database, and use that.red(apple1).red(block1).red(car27). Third choiceWe now attempt the car goal again, but this time for car27.
Nowrecall what we said earlier about the dangers of over estimating thepowers of Prolog. Prolog will try to match the goal car(car27)against the databasecar(desoto48).car(edsel57).This will fail. Car27 does not match with either desoto48 oredsel57.
Visual Prolog Software
Although the programmer probably meant car27 to mean carnumber 27 to be a car, Prolog has no way of gleaning this intendedsemantics, 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 ifthere are any more possible red items. Well we have now exhausted allthree choices, hence there are no more red items to choose from.Given that there are no more possible ways that we could satisfyclause 1, we now more on to clause 2, as we see on the next card.Search Example 5Let us recall our program. It said that something was fun if it was redand a car or blue and a bike.
Well, we couldn't find something that wasboth red and a car, so we now see if something blue and a bike.