The Farmer, Fox, Chicken and Grain problem

I haven’t had much opportunity to work with logic programming languages, so I attempted this simple planning problem in Prolog:

A farmer is returning to his farm after a long day of working in the fields. He has with him a fox, a chicken, and some grain. He must cross a small stream on his way back to the barn. At the stream, there is a canoe, in which he can transport at most one item across at a time. However, he cannot leave the fox alone with the chicken, or the fox will eat the chicken. Similarly, he cannot leave the chicken alone with the grain because the chicken will eat the grain. Devise a plan (sequence of actions) that the farmer can take to safely bring all of his possessions across the stream and continue on his way home.

I wrote the following solution using gprolog. Both gprolog and the other prolog available on Debian systems, swi-prolog, have really horrible programming environments. I can see why many people would skip over prolog given such poor implementations.


initial(X) :- sort([farmer,fox,chicken,grain],X).

% exclude invalid combinations

check_invalid([chicken, fox]) :- !, fail.
check_invalid([chicken, grain]) :- !, fail.
check_invalid([chicken, fox, grain]) :- !,fail.
check_invalid(_) :- true.

% check if we have reached the goal

find_solution(Goal,Goal,_, Moves,Plan) :-
    reverse(Moves,Plan).

% try to make a move, check whether the result is valid
% and check the history to see if we are repeating a move

find_solution(Initial,Goal,History, Moves, Plan) :-
    cross(Initial,[Near,Far],Move),
    sort(Near,SNear),
    sort(Far,SFar),
    check_invalid(SNear),
    check_invalid(SFar),
    \\+(member([SNear,SFar],History)),
    find_solution([SNear,SFar], Goal, [[SNear,SFar] | History], [ Move | Moves], Plan).

% cross from Near to Far side
cross([Near,Far],Result,Move) :-
    member(farmer, Near),
    cross1([Near,Far],Result, Move, forward).

% cross from Far to Near side
cross([Near,Far],[NN,NF],Move) :-
    member(farmer, Far),
    cross1([Far,Near],[NF,NN], Move, backward).

% let the farmer cross alone
cross1([Near,Far],[NN,NF],Move,Direction) :-
    select(farmer,Near,NN),
    append([farmer],Far, NF),
    Move = [Direction, farmer, []].

% let the farmer cross with one Animal/grain
cross1([Near,Far],[NN,NF],Move,Direction) :-
    select(farmer,Near,RemainingNear),
    member(Animal,RemainingNear),
    select(Animal,RemainingNear,NN),
    append([farmer,Animal],Far, NF),
    Move = [Direction, farmer, [Animal]].

run(Plan) :-
    initial(I),
    find_solution([I,[]],
                  [[],I],
                  [],
                  [],
                  Plan).

2 Replies to “The Farmer, Fox, Chicken and Grain problem”

  1. SWI-Prolog has a really good built-in Emacs-clone (“?- emacs(‘file.pl’)”) that seems to be omitted from the Debian package . Try installing it from source (you need the X.org development packages installed to get the GUI interface, graphical debugger etc.). There is also a really good Emacs mode maintained by Stefan Bruda.

    And instead of your check_invalid/1, you can write:

    invalid([chicken, fox]).
    invalid([chicken, grain]).
    invalid([chicken, fox, grain]).

    and use \+ invalid(SNear), \+ invalid(SFar). It’s also clearer and cheaper to use a triple or pair for moves, like move(forward, chicken).

  2. I’ve now also solved it:

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    solve(Ps) :- length(Ps, _), solve(Ps, l_b_r([f,c,g],e,[]), l_b_r([],e,_)).

    valid(S, S) :-
    S = l_b_r(L,_,R),
    ( L == [] ; \+ ( invalid_(L) ; invalid_(R) ) ).

    invalid_(Ls) :- memberchk(c, Ls), ( memberchk(g, Ls) ; memberchk(f, Ls) ).

    solve([]) –> [].
    solve([M|Ms]) –> move(M), valid, solve(Ms).

    move(take(X), l_b_r(L0,e,R0), l_b_r(L,X,R0)) :- select(X, L0, L).
    move(take(X), l_b_r(L0,e,R0), l_b_r(L0,X,R)) :- select(X, R0, R).
    move(drop(X), l_b_r(L0,X,R0), l_b_r(L0,e,[X|R0])) :- X \== e.
    move(drop(X), l_b_r(L0,X,R0), l_b_r([X|L0],e,R0)) :- X \== e.
    move(exch(X,Y), l_b_r(L0,X,R0), l_b_r(L0,Y,[X|R])) :-
    X \== e, select(Y, R0, R).
    move(exch(X,Y), l_b_r(L0,X,R0), l_b_r([X|L],Y,R0)) :-
    X \== e, select(Y, L0, L).

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    Example:

    ?- solve(Ps).
    Ps = [take(c), drop(c), take(f), exch(f, c), exch(c, g), drop(g), take(c), drop(c)]

Comments are closed.