Based on the material presented in class you may wonder what Prolog is good for. We did not have time to cover a full example demonstrating the expressive power of Prolog during the lecture. Here is such an example.

Prolog is a great language for several types of *puzzle solving*
problems. Consider the following well-known riddle:

To solve this problem in Prolog, one can encode the configuration of
the 4 objects (farmer, wolf, goat, cabbage) as a list. If `w` denotes
the West bank and `e` denotes the East bank, then the initial state
it:

`[w,w,w,w]`
(everyone is on the West bank)

`[e,e,w,w]`
(and the goat eats the cabbage)

The desired final configuration is:

`[e,e,e,e]`
(everyone is on the East bank)

In each move, the farmer crosses the river with wither the wolf, the goat, the cabbage, or nothing. Each move can be represented with a corresponding atom:

Now, each move transforms one configuration into another. This can be
written as a Prolog predicate `move(Config,Move,NextConfig)`
where `Config` is a configuration, `Move` is one of the
four basic moves, and `NextConfig` is the configuration that
results from applying that move to `Config`.

For instance, the goal `move([w,w,w,w],wolf,[e,e,w,w])` would
be valid and could be encoded as a fact:

`move([w,w,w,w],wolf,[e,e,w,w]). (note the '.')`

But there would be MANY such facts to encode. The key observation here is that when the wolf and the farmer move, the goat and the cabbage do not change position. So a more generate fact is:

`move([w,w,Goat,Cabbage],wolf,[e,e,Goat,Cabbage]). `

where `Goat` and `Cabbage` are variables.

Now, there is a similar move when the farmer and the wolf go from East to West. One can thus further generalize the above fact as:

`move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]) :- change(X,Y).`

which assumes that a `change` predicate is defined as:

`change(e,w).`

`change(w,e).`

One could have thought of just writing:

`move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]).`
but in this case `X` and `Y` above
could unify to any atom (e.g. to `goat`), which is invalid.

Now, one can encode all the valid moves:

change(e,w).

change(w,e).

move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]) :- change(X,Y).

move([X,Wolf,X,Cabbage],goat,[Y,Wolf,Y,Cabbage]) :- change(X,Y).

move([X,Wolf,Goat,X],cabbage,[Y,Wolf,Goat,Y]) :- change(X,Y).

move([X,Wolf,Goat,Cabbage],nothing,[Y,Wolf,Goat,Cabbage]) :- change(X,Y).

Next, configurations need to be tested for safety (so that nothing gets eaten). To do this we define a predicate

oneEq(X,X,_).

oneEq(X,_,X).

The idea is that if at least one of the goat or the wolf is on the same bank as the farmer, AND if at least one of the goat or cabbage is on the same side as the farmer, then the configuration is safe (think about it for a minute). This can be encoded as:

safe([Man,Wolf,Goat,Cabbage]) :-

oneEq(Man,Goat,Wolf), oneEq(Man,Goat,Cabbage).

With

solution([e,e,e,e],[]).

solution(Config,[FirstMove|OtherMoves]) :- move(Config,Move,NextConfig), safe(NextConfig), solution(NextConfig,OtherMoves).

WARNING: nothing in this Prolog program specifies how long the solution has to be. In fact, a solution could be arbitrary long (e.g. insert an infinite number of

which means: "First cross with the goat, then cross back empty, then cross with the wolf, then cross back with the goat, then cross with the cabbage, then cross back empty, a finally cross with the goat". It turns out that this is the minimum number of steps. If you keep asking Prolog for solutions you'll find that there are no solutions with an even number of steps, that some queries answer several times the same solution, etc.. There is MUCH MORE to Prolog than what we're covering in this class and we recommend that you follow the links provided on the main page to learn more about Prolog.?-length(X,7), solution([w,w,w,w],X).

X = [goat, nothing, wolf, goat, cabbage, nothing, goat]

Yes

Here is the entire source code.

Other common puzzle solving programs in Prolog are: