% farmer.pl
%
% Tom Cornell
% May 5, 1999
%
/*
\documentclass[a4paper]{article}

\begin{document}
\title{{\ttfamily farmer.pl}\\
The Farmer, the Wolf, the Goat and the Cabbage}
\author{Tom Cornell}
\maketitle

\begin{verbatim}
*/
:- use_module( library(lists), [member/2,select/3] ).

/*
\end{verbatim}

There are two special points that need to be taken care
of.

1. We need to be able to bring the farmer across the river
in an empty boat. Our solution: Aside from the four protagonists,
we also have the mysterious individual \verb@no_one@,
who has no location but can still be carried in a boat.

2. We have to take care never to bring back
someone we just brought over. Otherwise, we risk falling
down an infinite search tree branch before we have found
even one solution. So we always need to keep track of who
the last one transfered was (including \verb@no_one@).

This version generates lists of passengers as strings
recognized by the underlying automaton. This means that we
can (a) see what the solution looks like and (b) use
calls to \verb@list/1@ to simulate breadth first search
and so enumerate all solutions.

Note that there are infinitely many solutions. Once we get
everyone over to the south bank of the river, we have the
option of returning them all to the north bank and starting
over, for example.

The main predicate is \verb@farmer/1@, which holds of a
list of elements drawn from the set:
\[ \{ \texttt{farmer,wolf,goat,cabbage,no\_one} \} \]
just in case that list represents a solution to the
problem. \verb@farmer/1@ calls \verb@solution/4@, which
acts like \verb@delta_star/3@ in the finite state
automaton implementation. The extra argument represents
the last passenger. It is initialized to \verb@no_one@,
which is intuitively correct. Note however that this
value will not appear as part of the solution.

\begin{verbatim}
*/
farmer( TheSolution ):-
        initial( Q0 ),
        final( Q ),
        solution( Q0, no_one, TheSolution, Q ).
/*
\end{verbatim}

The predicate \verb@solution/4@ can be thought of in terms
of an FSA as follows. Assume that we have a definition of
\verb@crossing/4@ which tells us when it is legal to take
a given passenger across the river. This functions like
the \verb@delta/3@ relation in the FSA. Assuming that we
are recognizing/generating a string of passengers, we can
think of \verb@crossing/4@ as reading a passenger from the
solution string and changing state to reflect the new locations
of the various actors in this drama. 

\begin{verbatim}
*/
solution( Q0, _, [], Q ):- Q0 = Q.
solution( Q0, LastOver, [NextOver|PartSol], Q ):-
        crossing( Q0, LastOver, NextOver, Q1 ),
        solution( Q1, NextOver, PartSol, Q ).

initial( Q ):-
        where( farmer, north, Q ),
        where( wolf, north, Q ),
        where( goat, north, Q ),
        where( cabbage, north, Q ).

final( Q ):-
        where( farmer, south, Q ),
        where( wolf, south, Q ),
        where( goat, south, Q ),
        where( cabbage, south, Q ).

crossing( Q1, Last, Next, Q2 ):-
        where( farmer, Bank1, Q1 ),
        opposite( Bank1, Bank2 ),
        select( Next, [no_one,wolf,goat,cabbage], Others ),
        where( Next, Bank1, Q1 ), % such that X is with the farmer
        neq( Next, Last ),
        /* Construct new state: */
        frame( Others, Q1, Q2 ),
        where( farmer, Bank2, Q2 ),
        where( Next, Bank2, Q2 ),
        safe( Q2 ).


where( farmer, F, q(F,_,_,_) ).
where( wolf, W, q(_,W,_,_) ).
where( goat, G, q(_,_,G,_) ).
where( cabbage, C, q(_,_,_,C) ).
where( no_one, _, _ ).

opposite( south, north ).
opposite( north, south ).

neq( X, Y ):-
        select( X, [no_one,wolf,goat,cabbage], Rest ),
        member( Y, Rest ).

safe( Q ):-
        safe_for_goat( Q ),
        safe_for_cabbage( Q ).

safe_for_goat( Q ):-
        where( goat, NoSo, Q ),
        where( wolf, SoNo, Q ),
        opposite( NoSo, SoNo ).
safe_for_goat( Q ):-
        where( goat, NoSo, Q ),
        where( wolf, NoSo, Q ),
        where( farmer, NoSo, Q ).

safe_for_cabbage( Q ):-
        where( cabbage, NoSo, Q ),
        where( goat, SoNo, Q ),
        opposite( NoSo, SoNo ).
safe_for_cabbage( Q ):-
        where( cabbage, NoSo, Q ),
        where( goat, NoSo, Q ),
        where( farmer, NoSo, Q ).

frame( [], _, _ ).
frame( [A|As], Q1, Q2 ):-
        where( A, ALoc, Q1 ),
        where( A, ALoc, Q2 ),
        frame( As, Q1, Q2 ).

/*
\end{verbatim}

\end{document}
*/

