There are three cannibals and three missionaries on one bank of a river. They want to get to the other side. There is a rowboat, but it can only hold one or two people at a time.
The boat will not go across the river by itself. It must be rowed. Either a missionary a cannibal can row the boat, but if it ever happens that cannibals outnumber missionaries on either bank of the river, then the cannibals will eat the missionaries on that bank.
The problem is to develop a plan for getting everybody across the river, without anybody being eaten.
Write a program using backtracking Missionaries/Cannibals problem. It should print all solutions that do not involve reaching the same state twice. Try to make your printout readable. Print the plan as a sequence of states. It is not necessary to give instructions for how to get from one state to the next, since that should be obvious from the states themselves.
Use the Farmer/Wolf/Goat/Cabbage program as a guide. Here are some suggestions.
Decide on a reasonable notion of a state. What do you need to know? How can you represent it? This step is critical.. How you choose to represent the state can have a strong impact on how easy the program is to write. Think ahead about the operations that you need to implement, and then ask how the state might be represented to make the operations easy to write.
Write a function next(s) that produces a state that might follow state s in a plan. The next state might involve a missionary and a cannibal paddling across the river, for example.
Expression next(s) should produce a stream of all of the states that could follow state s. Do not pay attention to whether the states are good or bad. Just produce them all.
Write a predicate admissible(s) that is true if s is an admissible state. An admissible state is one where no missionary is being eaten on either bank of the river.
A plan is a list of states. Write a function plan(x,g) that takes a list of states and extends it into a plan that ends on state g. You will find it convenient to represent the plans backward, so that a the first state is at the end of the list and the last state is at the beginning of the list. plan(x,g) should produce a list of states y so that y begins with g (so the plan ends on g) and x is a suffix of y.
plan(x,g) should really produce a stream of lists, giving all plans that start like x, end on g, and contain no inadmissible states and contain no duplicate states.
Write the program in Astarte. Write the output so that it is readable. For example, write a procedure called PrintState that prints a state in a readable form, showing missionaries and cannibals on each bank of the river.