% Missionaries and Cannibals: teaching example % Peter Ross, May 1983 % % To start it: % ?- search(state(3,3,0,0,left), state(3,3,0,0,left), Ans). % or % ?- try(Ans). % Oddity: trace it, and 'check(_,_)' never appears in the trace. :- op(700,yfx,&). search(state(0,0,_,_,right), Answer, Answer). search(state(Ml,Cl,Mr,Cr,left), PastMoves, Answer) :- try(M,C,given(Ml,Cl)), NewMl is Ml-M, NewCl is Cl-C, NewMr is Mr+M, NewCr is Cr+C, NewState = state(NewMl,NewCl,NewMr,NewCr,right), check(NewState,PastMoves), search(NewState, PastMoves & NewState, Answer). search(state(Ml,Cl,Mr,Cr,right), PastMoves, Answer) :- try(M,C,given(Mr,Cr)), NewMl is Ml+M, NewCl is Cl+C, NewMr is Mr-M, NewCr is Cr-C, NewState = state(NewMl,NewCl,NewMr,NewCr,left), check(NewState, PastMoves), search(NewState, PastMoves & NewState, Answer). check(state(Ml,Cl,Mr,Cr,_), History) :- (Ml>0, Ml0, Mr0. try(2,0,given(M,_)) :- M>1. try(0,1,given(_,C)) :- C>0. try(0,2,given(_,C)) :- C>1. try(1,1,given(M,C)) :- M>0, C>0. try(Ans) :- search(state(3,3,0,0,left), state(3,3,0,0,left), Ans). go :- try(Ans), gimme(Ans). gimme(History & State) :- gimme(History), showme(State). gimme(State) :- showme(State). showme(state(Ml,Cl,Mr,Cr,Bank)) :- write('Left: M='), write(Ml), write(' C='), write(Cl), write(' Right: M='), write(Mr), write(' C='), write(Cr), write(' Boat on '), write(Bank), write(' bank.'), nl.