Escape from Zurg in Prolog


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


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

We distinguish between two kinds of moves: 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 },

moves_(state(_,[],_))     --> [].
moves_(state(T0,Ls0,Rs0)) -->
        { select(Toy, Rs0, Rs1),
          toy_time(Toy, Time),
          T1 #= T0 + Time, T1 #=< 60 },
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)] ? ;

Source file:

Further reading

Prolog is frequently compared with other languages. Such comparisons are often heavily biased against Prolog by misusing or neglecting some of its features. See Prolog compared with LISP for an example from 1982. Its abstract ends with:
Nevertheless, the results are interesting enough so as to make us consider them worth divulging, especially because they seem to contradict the notion, repeatedly argued for by Prolog advocates, that performances of the two languages are similar in relation to speed.
In this concrete case, Richard O'Keefe has published a response as Prolog compared with LISP? in 1983. The abstract ends with:
In this article, I point out which features of Prolog have been misused and give guidelines for their proper use. I also compare a new Prolog and LISP program performing a similar task, and find that the execution times are comparable. This is in accord with earlier results.

More about Prolog: The Power of Prolog

In particular:

Main page