Escape from Zurg in Prolog


Motivation

There is a paper that asks for a solution to the following problem:
Buzz, Woody, Rex, and Hamm have to escape from Zurg. They merely have to cross one last bridge before they are free. However, the bridge is fragile and can hold at most two of them at the same time. Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts. The problem is that our friends have only one flashlight with one battery that lasts for only 60 minutes. The toys need different times to cross the bridge (in either direction):

Toy
Time

Buzz 5
Woody    10
Rex 20
Hamm 25


Since there can be only two toys on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to those toys on the other side that still have to cross the bridge. The problem now is: In which order can the four toys cross the bridge in time (that is, within 60 minutes) to be saved from Zurg?


The approach taken by the paper follows a long tradition: First, a convoluted Prolog solution is presented, and this is then compared with a more elegant solution in a different language. The point of this page is to show you that there is also an elegant Prolog solution for this task.

Prolog solution

To represent the state of the world in this problem, we will use a term of the form state(T,Ls,Rs), where:
Without loss of generality, let us suppose that all toys are initially on the left side, and need to cross the bridge to get to the right side. Clearly, two important states are hence:
We are looking for a sequence of state transitions or moves that take us from the initial state to the desired final state. For convenience, we are using a Prolog Definite Clause Grammar (DCG) to describe such sequences of moves.

We distinguish between two kinds of moves: It follows from the from task description that no other kinds of moves are necessary.

An important precondition for each such move is that we stay within the time limit of 60 minutes.

Using these features, here is a Prolog solution for this puzzle:

toy_time(buzz,   5).
toy_time(woody, 10).
toy_time(rex,   20).
toy_time(hamm,  25).

moves(Ms) :- phrase(moves(state(0,[buzz,woody,rex,hamm],[])), Ms).

moves(state(T0,Ls0,Rs0)) -->
        { select(Toy1, Ls0, Ls1), select(Toy2, Ls1, Ls2),
          Toy1 @< Toy2,
          toy_time(Toy1, Time1), toy_time(Toy2, Time2),
          T1 #= T0 + max(Time1,Time2), T1 #=< 60 },
        [left_to_right(Toy1,Toy2)],
        moves_(state(T1,Ls2,[Toy1,Toy2|Rs0])).

moves_(state(_,[],_))     --> [].
moves_(state(T0,Ls0,Rs0)) -->
        { select(Toy, Rs0, Rs1),
          toy_time(Toy, Time),
          T1 #= T0 + Time, T1 #=< 60 },
        [right_to_left(Toy)],
        moves(state(T1,[Toy|Ls0],Rs1)).
    
Note that only 4 predicates (instead of 8) are necessary.

Example interaction, using GNU Prolog 1.3.0:
| ?- moves(Ms).

Ms = [left_to_right(buzz,woody),right_to_left(buzz),left_to_right(hamm,rex),right_to_left(woody),left_to_right(buzz,woody)] ? ;

Ms = [left_to_right(buzz,woody),right_to_left(woody),left_to_right(hamm,rex),right_to_left(buzz),left_to_right(buzz,woody)] ? ;

no
    

Source file: zurg.pl

Related: Thinking in States


More about Prolog


Main page