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.
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.
The boat will not go across the river by itself. It must be rowed.
The problem is to develop a plan for getting everybody across the river, without anybody being eaten.
Write a program in a logic programming style that solves the Missionaries/Cannibals problem. It should print all solutions that do not involve reaching the same state twice. Try to make your printout readable. Print it 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.
With the exception of a very limited amount of code that is responsible for accomplishing the printing, the program should be a collection of predicates. Each predicate must be accompanied with a comment that describes the meaning of the predicate. The meaning must be a reasonable definition of a predicate, not a description of the computation that is done while evaluating the predicate.
Use the Farmer/Wolf/Goat/Cabbage program as a guide. That program is not written in a logic-programming style, but it can be modified to that style. Here are some suggestions.
Decide on a reasonable notion of a state. What do you need to know? How can you represent it?
Write a predicate next(s,t) that is true if t is a state that could follow state s in a plan. Changing from s to t should involve the boat crossing the river once.
Write a predicate admissible(s) that is true if s is an admissible state.
Think about what other predicates you will need. Be sure that all of your computation, with the exception of the actual printing, is done by predicates. Keep the predicates simple.
For this program, you have a choice of using Prolog or Astarte.
To write in Astarte, read logic programming in Astarte. You must use logic programming style for this program. If you write in Astarte, you will find sets useful. You can use basic set operations, if you are careful that the parameters do not involve unknowns. See the set library.
To use Prolog, see the next section. You will want to use a term to represent a state. For example, term state(L,R) might be used, where list L indicates who or what is on the left bank, and R indicates who or what is on the right bank.
In prolog, you write [A|B] for the list whose head is A and whose tail is B.
Prolog has pseudo-predicates to perform actions. Use parameterless pseudo-predicate nl to print an end-of-line character, and write(k) to print term k. If you print a term, and the value is something like V001, then the term is an unbound variable (and so is unknown).
Be sure to put a period at the end of every axiom. In Prolog, variables start with upper case letters, and constants start with lower case letters. Be careful about that. Predicate names also start with lower case letters.
Comments in Prolog start with % and end at the end of a line.
Use the pl command on the machines in Austin 320 to run SWI Prolog. To use pl, first compile your file. If your Prolog program is in file myprog.pl, type
pl -o myprog -c myprog.plThis only compiles your program into an intermediate code. To run your program, use command
myprogYou will be prompted for goals. Each goal must end on a period. After a result is shown, you can type a semicolon to ask for more solutions.