Use Prolog to create depthfirst breadthfirst and bestfirst s

Use Prolog to create depth-first, breadth-first, and best-first solutions for the Missionary and Cannibal problem.

The Missionaries and Cannibals problem (Three Missionaries and three Cannibals come to a river. There is a boat that will hold only two of them – either person can row the boat. If there are ever more Missionaries than Cannibals on either side of the river the Cannibals will get converted. Devise a series of crossings of the river so that all the characters get across and no one gets converted. This problem can also be stated in terms of eating Missionaries – enforcing both constraints makes the problem impossible.),

Solution

% mandc(CurrentState, Visited, Path) % to run the code in iProlog, do % % prolog mandc.pro % : mandc(state(3,3,left), [state(3,3,left)], Path)? % if you are looking at this with a web browser like \"netscape\", you can % save a copy by selecting \"Save As\" from the \"File\" menu. mandc(state(0, 0, right), _, []). mandc(CurrentState, Visited, [Move | RestOfMoves]) :- newstate(CurrentState, NextState), not(member(NextState, Visited)), make_move(CurrentState, NextState, Move), mandc(NextState, [NextState | Visited], RestOfMoves). % make_move(State1, State2, Move) builds the move(-,-,-) that gets you % from State1 to State2. make_move(state(M1, C1, left), state(M2, C2, right), move(M, C, right)) :- M is M1 - M2, C is C1 - C2. make_move(state(M1, C1, right), state(M2, C2, left), move(M, C, left)) :- M is M2 - M1, C is C2 - C1. % carry(X,Y) is true if the boat can carry X missionaries and Y cannibals. carry(2, 0). carry(1, 0). carry(1, 1). carry(0, 1). carry(0, 2). % legal(X, Y) is true if it is safe for the missionaries to have X % missionaries and Y cannibals together on a river bank (left or right). legal(X, X). legal(3, X). legal(0, X). % newstate(State1, State2) is true if it is possible to get from State1 % to State2. newstate(state(M1, C1, left), state(M2, C2, right)) :- carry(M, C), M <= M1, C <= C1, M2 is M1 - M, C2 is C1 - C, legal(M2, C2). newstate(state(M1, C1, right), state(M2, C2, left)) :- carry(M, C), M2 is M1 + M, C2 is C1 + C, M2 <= 3, C2 <= 3, legal(M2, C2).