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 task, we use a term of the form state(T,Ls,Rs), where:

T is an integer that denotes the time taken so far
Ls is a list of toys that are currently on the left side
Rs is a list of toys that are currently on the right side

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:

the initial state, which we can represent as state(0,[buzz,woody,rex,hamm],[]) in our representation
the desired final state, where all toys are on the right side, or equivalently, none of the toys are on the left side, and which we can hence represent as state(_,[],_)

We are looking for a sequence of state transitions or moves that take us from the initial state to the desired final state.

We distinguish between two kinds of moves:

left_to_right(Toy1,Toy2) means that Toy1 and Toy2 move from left to right
right_to_left(Toy) means that Toy moves from right to left

It follows from the 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.

For convenience, we are using a Prolog Definite Clause Grammar (DCG) to describe a sequence of moves. In addition, we are using declarative integer arithmetic to reason about integer expressions.

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

Escape from Zurg in Prolog

Motivation

Prolog solution

Further reading