Human Wolf Goat Cabbage version 1

wgc1.pl

#!/usr/pkg/bin/swi-prolog
%
% Solve the puzzle of the wolf, the goat and th cabbage
%

:- use_module(library(lists)).

go :-
    Begin = situation([h,w,g,c], []),
    Goal  = situation([], [h,c,g,w]),
    solve(Begin, Goal, [Begin]).

%go :- solve(situation([h,w,g,c], []),  situation([], [h,c,g,w]), []).

solve(State1, State2, History) :-
    same_state(State1, State2),
	writef("Solution: %t history\n%t.\n", [State1, History]).

solve(From, To, History) :-
    move(From, Intermediate),
	\+ history_member(Intermediate, History),
	    solve(Intermediate, To, [Intermediate | History]).

move(situation([h | From], To), situation(NewFrom, [h | NewTo])) :-
    move1(From, To, NewFrom, NewTo),
    writef("%s %s => %s %s\n", [From, To, NewFrom, NewTo]).

move(situation(To, [h | From]),  situation([h | NewTo], NewFrom)) :-
    move1(From, To, NewFrom, NewTo),
    writef("%s %s <= %s %s\n", [To, From, NewTo, NewFrom]).

% move1 moves one object from the left to the right
% and checks that this is safe on the left.
% (implied is that the human is now on the right).
% OR
% it moves nothing, in which case the boat only transports
% the human. It should also check on the left.

move1(Left, Right, Left, Right) :-
    safe(Left).

move1(Left, Right, NewLeft, [Object | Right]) :-
    pick(Left, Object, NewLeft),
	safe(NewLeft).

% Pick an element from a list and return the element and the reduced list

pick([Head | Tail], Head, Tail).

pick([Head | Tail], Object, [ Head | SmallerTail]) :-
    pick(Tail, Object, SmallerTail).
	
% eats/2 with single elements
eats(w, g).
eats(g, c).

% eats with a set on the right
eats1(Eater, [Food | Foods]) :-
    eats(Eater, Food);
    eats1(Eater, Foods).

% eats/2 with 2 sets
eats2([Eater|Eaters], Foods) :-
    eats1(Eater, Foods);
    eats2(Eaters, Foods).

% is this combination safe ?

safe(Side) :-
    safe(Side, Side).

safe(Eaters, Foods) :-
    \+ eats2(Eaters, Foods).

% Member/2
history_member(Element, [Head | Tail]) :-
    same_state(Element, Head);
    history_member(Element, Tail).

% Check if two states are the same
same_state(situation(L1, R1), situation(L2, R2)) :-
    permutation(L1, L2),
	permutation(R1, R2).