Backtracking

Often, when solving real problems, you must pursue a path to its logical conclusion. If this conclusion does not give the answer you were looking for, you must choose an alternate path. For instance, you might have played maze games when you were a child. One sure way to find the end of the maze was to turn left at every fork in the maze until you hit a dead end. At that point you would back up to the last fork, and try the right-hand path, once again turning left at each branch encountered. By methodically trying each alternate path, you would eventually find the right path and win the game.

Visual Prolog uses this same backing-up-and-trying-again method, called backtracking, to find a solution to a given problem. As Visual Prolog begins to look for a solution to a problem (or goal), it might have to decide between two possible cases. It sets a marker at the branching spot (known as a backtracking point) and selects the first subgoal to pursue. If that subgoal fails (equivalent to reaching a dead end), Visual Prolog will backtrack to the back-tracking point and try an alternate subgoal.

Here is a simple example:

/* Program ch04e02.pro */

This small program is made up of two sets of facts and one rule. The rule, represented by the relationship likes, simply states that Bill likes good-tasting food.

To see how backtracking works, give the program the following goal to solve:

    likes(bill, What).

In this case, it will begin the search for a solution by looking from the top for a match to the subgoal likes(bill, What).

It finds a match with the first clause in the program, and the variable What is unified with the variable X. Matching with the head of the rule causes Visual Prolog to attempt to satisfy that rule. In doing so, it moves on to the body of the rule, and calls the first subgoal located there: food(X).

In the search to satisfy the first subgoal, Visual Prolog starts at the top, attempting a match with each fact or head of a rule encountered as processing goes down into the program.

It finds a match with the call at the first fact representing the food relationship. Here, the variable X is bound to the value brussels_sprouts. Since there is more than one possible answer to the call food(X), Visual Prolog sets a backtracking point next to the fact food(brussels_sprouts). This backtracking point keeps track of where Prolog will start searching for the next possible match for food(X).

With X bound to brussels_sprouts, the next call made is

    tastes(brussels_sprouts, good)

and Visual Prolog begins a search to attempt to satisfy this call, again starting from the top of the program. Since no clause is found to match, the call fails and Visual Prolog kicks in its automatic backtracking mechanism. When backtracking begins, Prolog retreats to the last backtracking point set. In this case, Prolog returns to the fact food(brussels_sprouts).

When Prolog retreats to a backtracking point, it frees all the variables set after that point, and sets out to find another solution to the original call.

The call was food(X), so the binding of brussels_sprouts for X is released. Prolog now tries to resolve this call, beginning from the place where it left off. It finds a match with the fact food(pizza)] and returns, this time with the variable X bound to the value pizza.

Prolog now moves on to the next subgoal in the rule, with the new variable binding. A new call is made, tastes(pizza, good)], and the search begins at the top of the program. This time, a match is found and the goal returns successfully.

Since the variable What in the goal is unified with the variable X in the likes rule, and the variable X is bound to the value pizza, the variable What is now bound to the value pizza and Visual Prolog reports the solution

    What=pizza
    1 Solution

1. Visual Prolog's Relentless Search for Solutions (무차별 탐색)

As we've described earlier, with the aid of backtracking, Visual Prolog will not only find the first solution to a problem, but is actually capable of finding all possible solutions.

Consider Program 3, which contains facts about the names and ages of some players in a racquet club.

/* Program ch04e03.pro */

You'll use Visual Prolog to arrange a ping-pong tournament between the nine-year-olds in a racquet club. There will be two games for each pair of club players. Your aim is to find all possible pairs of club players who are nine years old. This can be achieved with the compound goal:

    player(Person1, 9),
    player(Person2, 9),
    Person1 <> Person2.

In natural language: Find Person1 (age 9) and Person2 (age 9) so that Person1 is different from Person2.

Visual Prolog will try to find a solution to the first subgoal player(Person1, 9) and continue to the next subgoal only after the first subgoal is reached. The first subgoal is satisfied by matching Person1 with peter. Now Visual Prolog can attempt to satisfy the next subgoal:

        player(Person2, 9)

by also matching Person2 with peter. Now Prolog comes to the third and final subgoal

        Person1 <> Person2

Since Person1 and Person2 are both bound to peter, this subgoal fails. Because of this, Visual Prolog backtracks to the previous subgoal, and searches for another solution to the second subgoal:

        player(Person2, 9)

    This subgoal is fulfilled by matching Person2 with chris.

Now, the third subgoal:

        Person1 <> Person2

can succeed, since peter and chris are different. Here, the entire goal is satisfied by creating a tournament between the two players, chris and peter.

However, since Visual Prolog must find all possible solutions to a goal, it backtracks to the previous goal--hoping to succeed again. Since

        player(Person2, 9)

can also be satisfied by taking Person2 to be susan, Visual Prolog tries the third subgoal once again. It succeeds (since peter and susan are different), so another solution to the entire goal has been found.

Searching for more solutions, Visual Prolog once again backtracks to the second subgoal, but all possibilities for this subgoal have been exhausted. Because of this, backtracking now continues back to the first subgoal. This can be satisfied again by matching Person1 with chris. The second subgoal now succeeds by matching Person2 with peter, so the third subgoal is satisfied, again fulfilling the entire goal. Here, another tournament has been scheduled, this time between chris and peter.

Searching for yet another solution to the goal, Visual Prolog backtracks to the second subgoal in the rule. Here, Person2 is matched to chris and again the third subgoal is tried with these bindings. The third subgoal fails, since Person1 and Person2 are equal, so backtracking regresses to the second subgoal in search of another solution. Person2 is now matched with susan, and the third subgoal succeeds, providing another tournament for the racket club (chris vs. susan).

Once again, searching for all solutions, Prolog backtracks to the second subgoal, but this time without success. When the second subgoal fails, backtracking goes back to the first subgoal, this time finding a match for Person1 with susan. In an attempt to fulfill the second subgoal, Prolog matches Person2 with peter, and subsequently the third subgoal succeeds with these bindings. A fifth tournament has been scheduled for the players.

Backtracking again goes to the second subgoal, where Person2 is matched with chris. A sixth solution is found for the racquet club, producing a full set of tournaments.

The final solution tried is with both Person1 and Person2 bound to susan. Since this causes the final subgoal to fail, Visual Prolog must backtrack to the second subgoal, but there are no new possibilities. Visual Prolog then backtracks to the first subgoal, but the possibilities for Person1 have also been exhausted. No more solutions can be found for the goal, so the program terminates.

Type in this compound goal for the program:

    player(Person1, 9),
    player(Person2, 9),
    Person1 <> Person2.

Verify that Visual Prolog responds with

    Person1=peter, Person2=chris
    Person1=peter, Person2=susan
    Person1=chris, Person2=peter
    Person1=chris, Person2=susan
    Person1=susan, Person2=peter
    Person1=susan, Person2=chris
    6 Solutions

Notice how backtracking might cause Visual Prolog to come up with redundant solutions. In this example, Visual Prolog does not distinguish that Person1 = peter is the same thing as Person2 = peter. We will show you later in this chapter how to control the search Visual Prolog generates.

Exercise in Backtracking

Using Program 3, decide what Visual Prolog will reply to the following goal:

    player(Person1, 9), player(Person2, 10).

Check your answer by typing in the exercise and the given goal when you run the program.

A Detailed Look at Backtracking

With this simple example under your belt, you can take a more detailed look at how Visual Prolog's backtracking mechanism works. Start by looking at Program 4 in light of the following goal, which consists of two subgoals:

    likes(X, wine) , likes(X, books)

When evaluating the goal, Visual Prolog notes which subgoals have been satisfied and which have not. This search can be represented by a goal tree:

/* Program ch04e04.pro */

The Four Basic Principles of Backtracking

In this example, the goal tree shows that two subgoals must be satisfied. To do so, Visual Prolog follows the first basic principle of backtracking:

Visual Prolog determines which subgoal it will use when trying to satisfy the clause according to the second basic principle of backtracking:

When executing Program 4, Visual Prolog finds a matching clause with the first fact defining the likes predicate. Take a look at the goal tree now.

The subgoal likes(X, wine) matches the fact likes(john, wine) and binds X to the value john. Visual Prolog tries to satisfy the next subgoal to the right.

The call to the second subgoal begins a completely new search with the binding X = john. The first clause

    likes(john, wine)

does not match the subgoal

    likes(X, books)

since wine is not the same as books. Visual Prolog must therefore try the next clause, but lance does not match     the value X (because, in this case, X is bound to john), so the search continues to the third clause defining the predicate likes:

likes(Z, books):- reads(Z), is_inquisitive(Z).

The argument Z is a variable, so it is able to match with X. The second arguments agree, so the call matches the head of the rule. When X matches Z, the arguments are unified. With the arguments unified, Visual Prolog will equate the value X has (which is john) with the variable Z. Because of this, now the variable Z also has the value john.

The subgoal now matches the left side (head) of a rule. Continued searching is determined by the third basic principle of backtracking:

This yields the following goal tree:

The goal tree now includes the subgoals

    reads(Z) and is_inquisitive(Z)

where Z is bound to the value john. Visual Prolog will now search for facts that match both subgoals. This is the resulting final goal tree:

According to the fourth basic principle of backtracking:

So now the initial goal is satisfied.

Visual Prolog uses the result of the search procedure in different ways, depending on how the search was initiated. If the goal is a call from a subgoal in the body of a rule, Visual Prolog attempts to satisfy the next subgoal in the rule after the call has returned. If the goal is a query from the user, Visual Prolog replies directly:

    X=john
    1 Solution

As you saw in Program 4, having once satisfied an external goal, Visual Prolog backtracks to find all alternate solutions. It also backtracks if a subgoal fails, hoping to re-satisfy a previous subgoal in such a way that the failed subgoal is satisfied by other clauses.

To fulfill a subgoal, Visual Prolog begins a search with the first clause that defines the predicate. One of two things can then happen:

It finds a matching clause, in which case the following occurs:

If there is another clause that can possibly re-satisfy the subgoal, Visual Prolog places a pointer (to indicate a backtracking point) next to the matching clause.

All free variables in the subgoal that match values in the clause are bound to the corresponding values.

If the matching clause is the head of a rule, that rule's body is then evaluated; the body's subgoals must succeed for the call to succeed.

It can't find a matching clause, so the goal fails. Visual Prolog backtracks as it attempts to re-satisfy a previous subgoal. When processing reaches the last backtracking point, Visual Prolog frees all variables that had been assigned new values since the backtracking point was set, then attempts to re-satisfy the original call.

Visual Prolog begins a search from the top of the program. When it backtracks to a call, the new search begins from the last backtracking point set. If the search is unsuccessful, it backtracks again. If backtracking exhausts all clauses for all subgoals, the goal fails.

Backtracking

Here is another, slightly more complex, example, illustrating how backtracking takes place in Prolog.

/* Program ch04e05.pro */

Visual Prolog calls the can_swim predicate with a free variable, What. In trying to solve this call, Visual Prolog searches the program looking for a match. It finds a match with the clause defining can_swim, and the variable What is unified with the variable Y.

Next, Visual Prolog attempts to satisfy the body of the rule. In doing so, Visual Prolog calls the first subgoal in the body of the rule, type(X, animal), and searches for a match to this call. It finds a match with the first fact defining the type relationship.

At this point, X is bound to ungulate. Since there is more than one possible solution, Visual Prolog sets a backtracking point at the fact type(ungulate, animal).

With X bound to ungulate, Visual Prolog makes a call to the second subgoal in the rule (is_a(Y, ungulate)), and again searches for a match. It finds one with the first fact, is_a(zebra, ungulate). Y is bound to zebra and Prolog sets a backtracking point at is_a(zebra, ungulate).

Now, with X bound to ungulate and Y bound to zebra, Prolog tries to satisfy the last subgoal, lives(zebra, in_water). Prolog tries each lives clause, but there is no lives(zebra, in_water) clause in the program, so the call fails and Prolog begins to backtrack in search of another solution.

When Visual Prolog backtracks, processing returns to the last point where a backtracking point was placed. In this case, the last backtracking point was placed at the second subgoal in the rule, on the fact is_a(zebra, ungulate).

When Visual Prolog reaches a backtracking point, it frees the variables that were assigned new values after the last backtracking point and attempts to find another solution to the call it made at that time. In this case, the call was is_a(Y, ungulate).

Visual Prolog continues down into the clauses in search of another clause that will match with this one, starting from the point where it previously left off. Since there are no other clauses in the program that can match this one, the call fails and Visual Prolog backtracks again in an attempt to solve the original goal.

From this position, the last backtracking point was set at type(ungulate, animal).

Visual Prolog frees the variables set in the original call and tries to find another solution to the call type(X, animal). The search begins after the backtracking point. Visual Prolog finds a match with the next type fact in the program (type(fish, animal)); X is bound to fish, and a new backtracking point is set at that fact.

Visual Prolog now moves down to the next subgoal in the rule; since this is a new call, the search begins at the top of the program with is_a(Y, fish).

Visual Prolog finds a match to this call and Y is bound to herring.

Since Y is now bound to herring, the next subgoal called is lives(herring, in_water). Again, this is a new call, and the search begins from the top of the program.

Visual Prolog tries each lives fact, but fails to find a match and the subgoal fails.

Visual Prolog now returns to the last backtracking point, is_a(herring, fish).

The variables that were bound by this matching are now freed. Starting at the point where it last left off, Visual Prolog now searches for a new solution to the call is_a(Y, fish).

Visual Prolog finds a match with the next is_a clause, and Y becomes bound to the symbol shark.

Visual Prolog tries the last subgoal again, with the variable Y bound to shark. It calls lives(shark, in_water); the search begins at the top of the program, since this is a new call. It finds a match and the last subgoal to the rule succeeds.

At this point, the body of the can_swim(Y) rule is satisfied. Visual Prolog returns Y to the call can_swim(What). Since What is bound to Y, and Y is bound to shark, What is now bound to shark in the goal.

Visual Prolog continues processing where it left off in the goal section, and calls the second subgoal in the goal.

Visual Prolog completes the program by outputting

    A shark can swim.

and the program terminates successfully.

Figure 4.1: How the can_swim Program Works

2. Controlling the Search for Solutions

Prolog's built-in backtracking mechanism can result in unnecessary searching; because of this, inefficiencies can arise. For instance, there may be times when you want to find unique solutions to a given question. In other cases, it may be necessary to force Visual Prolog to continue looking for additional solutions even though a particular goal has been satisfied. In cases such as these, you must control the backtracking process. In this section, we'll show you some techniques you can use to control Visual Prolog's search for the solutions to your goals.

Visual Prolog provides two tools that allow you to control the backtracking mechanism: the fail predicate, which is used to force backtracking, and the cut (signified by !), which is used to prevent backtracking.

3. Using the fail Predicate

Visual Prolog begins backtracking when a call fails. In certain situations, it's necessary to force backtracking in order to find alternate solutions. Visual Prolog provides a special predicate, fail, to force failure and thereby encourage backtracking. The effect of the fail predicate corresponds to the effect of the comparison 2 = 3 or any other impossible subgoal. Program 6 illustrates the use of this special predicate.

/* Program ch04e06.pro */

Once an internal goal has completely succeeded, there is nothing that tells Visual Prolog to backtrack. Because of this, an internal call to father will come up with only one solution. However, the predicate everybody in Program 6 uses fail to force backtracking, and therefore finds all possible solutions.

The object of the predicate everybody is to produce a cleaner response from program runs. Compare the answers to the two preceding goals:

    Goal father(X, Y).
    X=leonard, Y=katherine
    X=carl, Y=jason
    X=carl, Y=marilyn
    3 Solutions

and

    Goal everybody. 

        leonard is katherine's father
        carl is jason's father
        carl is marilyn's father
        yes

The predicate everybody uses backtracking to generate more solutions for father(X, Y) by forcing Prolog to backtrack through the body of the everybody rule:

    father(X, Y), write(X," is ",Y,"'s father\n"), fail.

fail can never be satisfied (it always fails), so Visual Prolog is forced to backtrack. When backtracking takes place, Prolog backtracks to the last call that can produce multiple solutions. Such a call is labeled non-deterministic. A non-deterministic call contrasts with a call that can produce only one solution, which is a deterministic call.

The write predicate can't be re-satisfied (it can't offer new solutions), so Visual Prolog must backtrack again, this time to the first subgoal in the rule.

Notice that it's useless to place a subgoal after fail in the body of a rule. Since the predicate fail always fails, there would be no way of reaching a subgoal located after fail.

Exercises

Load and run Program 6 and evaluate the following goals:

a. father(X, Y).

b. everybody.

2. Edit the body of the rule defining everybody so that the rule ends with the call to the write predicate (delete the call to fail). Now compile and run the program, giving everybody. as the goal. Why doesn't Visual Prolog find all the solutions as it does with the query father(X, Y)?

3. Relocate the call to fail at the end of the everybody rule. Again, give the query everybody as the goal. Why are the solutions to everybody terminated by no? For a clue, append everybody. as a second clause to the definition of predicate everybody and re-evaluate the goal.

4. Preventing Backtracking: The Cut

Visual Prolog contains the cut, which is used to prevent backtracking; it's written as an exclamation mark (!). The effect of the cut is simple: It is impossible to backtrack across a cut.

You place the cut in your program the same way you place a subgoal in the body of a rule. When processing comes across the cut, the call to cut immediately succeeds, and the next subgoal (if there is one) is called. Once a cut has been passed, it is not possible to backtrack to subgoals placed before the cut in the clause being processed, and it is not possible to backtrack to other predicates defining the predicate currently in process (the predicate containing the cut).

There are two main uses of the cut:

When you know in advance that certain possibilities will never give rise to meaningful solutions, it's a waste of time and storage space to look for alternate solutions. If you use a cut in this situation, your resulting program will run quicker and use less memory. This is called a green cut.

When the logic of a program demands the cut, to prevent consideration of alternate subgoals. This is a red cut.

How to Use the Cut

In this section, we give examples that show how you can use the cut in your programs. In these examples, we use several schematic Visual Prolog rules (r1, r2, and r3), which all describe the same predicate r, plus several subgoals (a, b, c, etc.).

Prevent Backtracking to a Previous Subgoal in a Rule

    r1 :- a, b, !, c.

This is a way of telling Visual Prolog that you are satisfied with the first solution it finds to the subgoals a and b. Although Visual Prolog is able to find multiple solutions to the call to c through backtracking, it is not allowed to backtrack across the cut to find an alternate solution to the calls a or b. It is also not allowed to backtrack to another clause that defines the predicate r1.

As a concrete example, consider Program 7.

/* Program ch04e07.pro */

In this example, the goal is to find a Corvette with a sexy color and a price that's ostensibly affordable. The cut in the buy_car rule means that, since there is only one Corvette with a sexy color in the database, if its price is too high there's no need to search for another car.

Given the goal

    buy_car(corvette, Y)

Visual Prolog calls car, the first subgoal to the buy_car predicate.

It makes a test on the first car, the Maserati, which fails.

It then tests the next car clauses and finds a match, binding the variable Color with the value black.

It proceeds to the next call and tests to see whether the car chosen has a sexy color. Black is not a sexy color in the program, so the test fails.

Visual Prolog backtracks to the call to car and once again looks for a Corvette to meet the criteria.

It finds a match and again tests the color. This time the color is sexy, and Visual Prolog proceeds to the next subgoal in the rule: the cut. The cut immediately succeeds and effectively "freezes into place" the variable bindings previously made in this clause.

Visual Prolog now proceeds to the next (and final) subgoal in the rule: the comparison

    Price < 25000.

This test fails, and Visual Prolog attempts to backtrack in order to find another car to test. Since the cut prevents backtracking, there is no other way to solve the final subgoal, and the goal terminates in failure.

Prevent Backtracking to the Next Clause

The cut can be used as a way to tell Visual Prolog that it has chosen the correct clause for a particular predicate. For example, consider the following code:

    r(1):- ! , a , b , c.
    r(2):- ! , d.
    r(3):- ! , c.
    r(_):- write("This is a catchall clause.").

Using the cut makes the predicate r deterministic. Here, Visual Prolog calls r with a single integer argument. Assume that the call is r(1). Visual Prolog searches the program, looking for a match to the call; it finds one with the first clause defining r. Since there is more than one possible solution to the call, Visual Prolog places a backtracking point next to this clause.

Now the rule fires and Visual Prolog begins to process the body of the rule. The first thing that happens is that it passes the cut; doing so eliminates the possibility of backtracking to another r clause. This eliminates backtracking points, increasing the run-time efficiency. It also ensures that the error-trapping clause is executed only if none of the other conditions match the call to r.

Note that this type of structure is much like a "case" structure written in other programming languages. Also notice that the test condition is coded into the head of the rules. You could just as easily write the clauses like this:

    r(X) :- X = 1 , ! , a , b , c.
    r(X) :- X = 2 , ! , d.
    r(X) :- X = 3 , ! , c.
    r(_) :- write("This is a catchall clause.").

However, you should place the testing condition in the head of the rule as much as possible, as doing this adds efficiency to the program and makes for easier reading.

As another example, consider the following program. Run this program and give the query friend(bill, Who) as the goal.

/* Program ch04e08.pro */

Without cuts in the program, Visual Prolog would come up with two solutions: Bill is a friend of both Jane and Sue. However, the cut in the first clause defining friend tells Visual Prolog that, if this clause is satisfied, it has found a friend of Bill and there's no need to continue searching for more friends. A cut of this type says, in effect, that you are satisfied with the solution found and that there is no reason to continue searching for another friend.

Backtracking can take place inside the clauses, in an attempt to satisfy the call, but once a solution is found, Visual Prolog passes a cut. The friend clauses, written as such, will return one and only one friend of Bill's (given that a friend can be found).

Determinism and the Cut

If the friend predicate (defined in the previous program) were coded without the cuts, it would be a non-deterministic predicate (one capable of generating multiple solutions through backtracking). In many implementations of Prolog, programmers must take special care with non-deterministic clauses because of the attendant demands made on memory resources at run time. However, Visual Prolog makes internal checks for non-deterministic clauses, reducing the burden on you, the programmer.

However, for debugging (and other) purposes, it can still be necessary for you to intercede; the check_determ compiler directive is provided for this reason. If check_determ is inserted at the very beginning of a program, Visual Prolog will display a warning if it encounters any non-deterministic clauses during compilation.

You can make non-deterministic clauses into deterministic clauses by inserting cuts into the body of the rules defining the predicate. For example, placing cuts in the clauses defining the friend predicate causes that predicate to be deterministic because, with the cuts in place, a call to friend can return one, and only one, solution.

The not Predicate

This program demonstrates how you can use the not predicate to identify an honor student: one whose grade point average (GPA) is at least 3.5 and who is not on probation.

/* Program ch04e10.pro */

Here are some examples of correct clauses and incorrect clauses.

    likes(bill, Anyone):-        /* 'Anyone' is an output argument */
    likes(sue, Anyone),
    not(hates(bill, Anyone).

In this example, Anyone is bound by likes(sue, Anyone) before Visual Prolog finds out that hates(bill, Anyone) is not true. This clause works just as it should.

If you rewrite this so that it calls not first, you will get an error message to the effect that free variables are not allowed in not.

    likes(bill, Anyone):-                 /* This won't work right */
    not(hates(bill, Anyone)),
    likes(sue, Anyone).

Even if you correct this (by replacing Anyone in not(hates(bill, Anyone)) with an anonymous variable) so that the clause does not return the error, it will still return the wrong result.

    likes(bill, Anyone):-                 /* This won't work right */
    not(hates(bill, _)),
    likes(sue, Anyone).

This clause states that Bill likes Anyone if nothing that Bill hates is known and if Sue likes Anyone. The original clause stated that Bill likes Anyone if there is some Anyone that Sue likes and that Bill does not hate.

Example

Always be sure that you think twice when using the not predicate. Incorrect use will result in an error message or errors in your program's logic. The following is an example of the proper way to use the not predicate.

/* Program ch04e11.pro */

Exercises

Suppose an average taxpayer in the USA is a married US citizen with two children who earns no less than $500 a month and no more than $2,000 per month. Define a special_taxpayer predicate that, given the goal special_taxpayer(fred)., will succeed only if fred fails one of the conditions for an average taxpayer. Use the cut to ensure that there is no unnecessary backtracking.

Players in a certain squash club are divided into three leagues, and players may only challenge members in their own league or the league below (if there is one).

Write a Visual Prolog program that will display all possible matches between club players in the form:

        tom versus bill
        marjory versus annette

    Use the cut to ensure, for example, that

        tom versus bill

    and

        bill versus tom

    are not both displayed.

This is an exercise in backtracking, not a test of your ability to solve murder mysteries. Load and run the following program, then enter the goal killer(X).

(Note: Bert is guilty because he has a motive and is smeared in the same stuff as the victim.)

/* Program ch04e12.pro */