%Prolog example developed by Dr. Klerer, New York
%/* */
go(Start,Goal,Route) :- go1([[Start]],Goal,R),rev(R,Route).
go1([First; Rest],Goal,First) :- First = [Goal; _].
go1([[Last; Trail]; Others],Goal,Route) :-
findall([Z,Last; Trail],legalnode(Last,Trail,Z),List),
append(Others,List,Newroutes),
go1(Newroutes,Goal,Route).
%/* */
%/* different_sides is used to provide a means of getting the boat */
%/* between the sides of the river. */
different_sides(a,b).
different_sides(b,a).
%/* */
%/* dinner_time is the predicate that demonstates the invalid */
%/* conditions of the problem. It should be noted that it is a */
%/* derivation to save time: (C>M and M\=0) or (3-C>3-M and 3-M\=0) */
%/* ==> (C>M and M\=0) or (CM or C=1.
rule(boat(a_cannibal,S1),state(M1,C1,S1),state(M2,C2,S2)) :-
M2 is 3-M1,
C2 is 3-C1+1,
different_sides(S1,S2),
not dinner_time(M2,C2),
C1>=1.
rule(boat(two_cannibals,S1),state(M1,C1,S1),state(M2,C2,S2)) :-
M2 is 3-M1,
C2 is 3-C1+2,
different_sides(S1,S2),
not dinner_time(M2,C2),
C1>=2.
rule(boat(two_missionaries,S1),state(M1,C1,S1),state(M2,C2,S2)) :-
M2 is 3-M1+2,
C2 is 3-C1,
different_sides(S1,S2),
not dinner_time(M2,C2),
M1>=2.
rule(boat(one_of_each,S1),state(M1,C1,S1),state(M2,C2,S2)) :-
M2 is 3-M1+1,
C2 is 3-C1+1,
different_sides(S1,S2),
not dinner_time(M2,C2),
M1>=1,
C1>=1.
:-print('Missionaries, cannibals and boat is ready!').