Use Prolog to create depth-first, breadth-first, and best-first solutions for th

Question

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.),

Explanation / Answer

% 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

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.