7    Problem Solving

Solutions

7.1    Car Driving in Switzerland

A road map can be represented as a set of facts:

road( City1, City2, Distance)

This means that there is a direct road between the cities City1 and City2.

road( zuerich,   baden,    22).    
road( baden,     basel,    83).
road( zuerich,   rotkreuz, 39).    
road( baden,     olten,    43).
road( olten,     bern,     67).    
road( olten,     luzern,   57).
road( olten,     basel,    39).    
road( rotkreuz,  luzern,   18).    
road( rotkreuz,  schwyz,   26).
road( luzern,    altdorf,  39).    
road( schwyz,    altdorf,  16).

Implement the predicate:

route( X, Y, W, L)

which means that there is a route W from X to Y having the length L. W is the ordered list of the cities in between starting with X.

Solution 7.1

7.2    Two Canisters

There are two canisters. The big one holds 7 liters, the small one 5 liters. How can we achieve 4 liters of water in the big canister? Only the following actions are possible:

1. Fill a canister completely.
2. Empty a canister.
3. Pour the content of a canister into the other one until the former is empty or the later is full.

Write first a general method for problem solving and apply it afterwards to the specific problem of the two canisters.

Solution 7.2

7.3    River Crossing

A farmer with a sheep, a goat and a bag of hay wants to cross a river. He has a boat that provides place only for him and one other object. He should not leave the sheep and the goat unsupervised with the hay. How can he manage the crossing?

(Hint: the farmer has a portable computer with a Prolog interpreter.

Solution 7.3

7.4    A Robot

A robot should shut a stopcock in a contaminated room. The robot stands at the door, while the stopcock is in the opposite corner at the ceiling. He (it) can reach it only if he steps on a movable ramp that is at the window. The robot can perform the following actions:

1. Walk around
2. Push the ramp
3. Step on the ramp
4. Step down from the ramp
5. Shut the stopcock
6. Open the stopcock

Which actions should the robot perform in order to shut the stopcock?

Hint: Represent the initial state e.g. as

Implement the predicate:

state(
    robot( at_door, on_floor),
    ramp( at_window), 
    stopcock( open)).

and the final state as

state(
    robot( in_corner, on_ramp),
    ramp( in_corner),
    stopcock( closed)).

Solution 7.4