7    Problem Solving

Solution of Exercise 7

7.1    Car Driving in Switzerland (Graph Search by Prolog-prover)

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).

tr( X, Y) :- road( X, Y, _).
tr( X, Y) :- road( Y, X, _).

distance( X, Y, L) :- road( X, Y, L), !.
distance( X, Y, L) :- road( Y, X, L).

path( Start, Start, Route, Route).
path( X, Y, PartialRoute, Route):- 
    tr( X, Z), not( member( Z, PartialRoute)), 
    path( Z, Y, [ Z| PartialRoute], Route).

route( Start, Destination, Route, Length) :- 
    path( Start, Destination, [ Start], RevRoute),
    revl( RevRoute, Route, Length).

revl( [ X1| Xs], Y, L) :- revl( Xs, [ X1], Y, 0, L).        

revl( [ X1| Xs], [ Y1| Ys], Y, L0, L) :- 
    distance( X1, Y1, DXY),
    L1 is L0 + DXY,
    revl( Xs, [ X1, Y1| Ys], Y, L1, L).
revl( [], Y, Y, L, L).

/* Test 
?- route(zuerich, baden, Route, L).
?- route(zuerich, altdorf, Route, L).
*/

Select code

Back to example 7.1

7.2    Two Canisters

/* General problem solving: forward, depth-first */
/* Transitions: move( State, NewState, Transition_name) */
/* Start = initial state;  Goal = goal state */
solve( Start, Path) :- solve( Start, [Start], Path).

solve( Goal, _, []) :- goal( Goal).
solve( State, Visited, [ T| Path]):- 
    move( State, NewState, T), 
    \+ member( NewState, Visited),
    solve( NewState, [ NewState | Visited], Path).

write_list( []).
write_list( [ X1| Xs]) :- nl, write( X1), write_list( Xs).

backtrack :- nl, nl, write( 'Further solutions? [y./n.]: '), 
            read( A), (A = n ; A = no).


/* Two Canisters */			 
canister :- solve( k( 0, 0), Path), 
            nl, write_list( Path), backtrack.

goal( k( 4, _)).

move( k( _, Y), k( 7, Y), a( 'fill C7', state_c7( 7))).          
move( k( X, _), k( X, 5), a( 'fill C5', state_c7( X))).
move( k( _, Y), k( 0, Y), a( 'empty C7', state_c7( 0))).
move( k( X, _), k( X, 0), a( 'empty C5', state_c7( X))).

move( k( X, Y), k( 0, Y1), a( 'empty C7 into C5', state_c7( 0))) :- 
    Y1 is Y + X, Y1 =< 5. 
move( k( X, Y), k( X1, 5), a( 'fill C5 from C7', state_c7( X1))) :- 
    X1 is X + Y - 5, X1 >= 0. 
move( k( X, Y), k( X1, 0), a( 'empty C5 into C7', state_c7( X1))) :- 
    X1 is X + Y, X1 =< 7.
move( k( X, Y), k( 7, Y1), a( 'fill C7 from C5', state_c7( 7))) :- 
    Y1 is X + Y - 7, Y1 >= 0.
	  
/* Test
?- canister.
*/

Select code

Back to example 7.2

7.3    River Crossing

river :- start_fl( Start), solve( Start, Path), 
         nl, write_list( Path), backtrack.

start_fl( f( farmer( L), sheep( L), goat( L), hay( L))) :- L = bank1.
goal( f( farmer( R), sheep( R), goat( R), hay( R))) :- R = bank2.

move( f( farmer( B),  sheep( S),  goat( Z),  hay( H)),
      f( farmer( B1), sheep( S1), goat( Z1), hay( H1)),
      crossing( from( B), to( B1), with( P))) :-
    opposite( B, B1),
    ( P = sheep,  S = B, S1 = B1, Z1 = Z,  H1 = H  ;
      P = goat,   Z = B, S1 = S,  Z1 = B1, H1 = H  ;
      P = hay  ,  H = B, S1 = S,  Z1 = Z,  H1 = B1 ;
      P = none,   S1 = S,  Z1 = Z,  H1 = H ),
    safe( farmer( B1), sheep( S1), goat( Z1), hay( H1)).

opposite( bank1, bank2).
opposite( bank2, bank1).

safe( farmer( B), sheep( _), goat( _), hay( B)).
safe( farmer( _), sheep( B), goat( B), hay( H)) :- opposite( B, H).

/* Test
?- river.
*/

Select code

Back to example 7.3

7.4    A Robot

robot :- robot0( Start), solve( Start, Path), 
           write_list( Path), backtrack.

robot0( r( robot( at_door, on_floor), ramp( at_window), stopcock( open))).
goal( r( Robot, Ramp, stopcock( closed))).

move( r( robot( X, on_floor), R, V), 
      r( robot( Y, on_floor), R, V), walk_to( Y)) :- 
               position( Y), X \= Y.
move( r( robot( X, on_floor), ramp( X), V),
      r( robot( Y, on_floor), ramp( Y), V), push_ramp_to( Y)) :- 
               position( Y), X \= Y.
move( r( robot( X, on_floor), ramp( X), V),
      r( robot( X, on_ramp), ramp( X), V), step_up_ramp).
move( r( robot( X, on_ramp), ramp( X), V),
      r( robot( X, on_floor), ramp( X), V), step_down_ramp).
move( r( robot( in_corner, on_ramp), R, stopcock( open)),
      r( robot( in_corner, on_ramp), R, stopcock( closed)), close).
move( r( robot( in_corner, on_ramp), R, stopcock( closed)),
      r( robot( in_corner, on_ramp), R, stopcock( open)), open).

position( at_door).
position( at_window).
position( in_corner).

/* Test 
?- robot.
*/

Select code

Back to example 7.4