Solve Three Missionaries and Three cannibals Problem Using Prolog

 % Main control block and printing  
   
 find :-  
   path([3,3,left],[0,0,right],[[3,3,left]],_).  
   
 output([]) :- nl, nl.  
 output([[A,B,String]|T]) :-  
 output(T),  
      write(B), write(' ~~ '), write(A), write(': '), write(String), nl.  
   
   
 % Base case  
 path([A,B,C],[A,B,C],_,MoveList):-  
 nl,nl,output(MoveList).  
   
   
 % Recursive call to solve the problem  
 path([A,B,C],[D,E,F],Traversed,Moves) :-  
   move([A,B,C],[I,J,K],Out),  
   legal([I,J,K]),  
 % Don't use this move unless it's safe.  
   
   not(member([I,J,K],Traversed)),  
   path([I,J,K],[D,E,F],[[I,J,K]|Traversed],[ [[I,J,K],[A,B,C],Out] | Moves ]).  
   
   
   
 % Move commands and descriptions of the move  
   
 move([A,B,left],[C,B,right],'One missionary crosses the river') :-  
   A > 0, C is A - 1.  
 move([A,B,left],[C,B,right],'Two missionaries cross the river') :-  
   A > 1, C is A - 2.  
 move([A,B,left],[C,D,right],'One missionary and One cannibal cross the river') :-  
   A > 0, B > 0, C is A - 1, D is B - 1.  
 move([A,B,left],[A,D,right],'One cannibal crosses the river') :-  
   B > 0, D is B - 1.  
 move([A,B,left],[A,D,right],'Two cannibals cross the river') :-  
   B > 1, D is B - 2.  
 move([A,B,right],[C,B,left],'One missionary returns from the other side') :-  
   A < 3, C is A + 1.  
 move([A,B,right],[C,B,left],'Two missionaries return from the other side') :-  
   A < 2, C is A + 2.  
 move([A,B,right],[C,D,left],'One missionary and One cannibal return from the other side') :-  
   A < 3, B < 3, C is A + 1, D is B + 1.  
 move([A,B,right],[A,D,left],'One cannibal returns from the other side') :-  
   B < 3, D is B + 1.  
 move([A,B,right],[A,D,left],'Two cannibals return from the other side') :-  
   B < 2, D is B + 2.  
   
 % Legal move definition where B is missionaries and A is cannibals:  
   
 legal([B,A,_]) :-  
   (A =< B ; B = 0),  
   C is 3-A, D is 3-B,  
   (C =< D; D = 0).