Due: Aug 2, 11:59pm.
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 Prolog for the Missionaries/Cannibals problem. It should print solutions that do not involve reaching the same state twice. Print the solution 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 predicate follows(S,T) that is true if state T can follow state S in the sequence of states. The change from S to T might involve a missionary and a cannibal paddling across the river, for example.
Do not worry about whether state T is a good state. That will be handled by a different predicate.
Note that follows is a predicate, and I have described it as if it is a pure test. But it will be used in mode follows(in,out).
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. You will find it convenient to represent plans backwards, so that a the first state is at the end of the list and the last state is at the beginning of the list.
Say that plan Y is an extension of plan X if there is a list Z such that Y = Z ++ X (where ++ is concatenation of lists) and no state in Z also occurs in X. Think of X as a start of a plan to solve the problem. Remembering that plans are backwards, an extension has zero or more additional states added to the end of the plan (the beginning of the list), without returning to a state that has already been visited.
Write a predicate plan(X,G,L) that takes a list of states X, a goal state G and a list of states L, and is true if L is an extension of X that begins with state G. It is intended to be used in mode plan(in,in,out).
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. A goal is not required to be on one line. If you forget the period and type a carriage-return, just type the period on the next line. After a result is shown, you can type a semicolon to ask for more solutions. When there are no more solutions the system will respond "no".
Many of the concepts of Prolog are the same as those that we have done in class, but there are some important notational differences. Lists are written in square brackets, as in Astarte. Write [A|B] for the list whose head is A and whose tail is B. Notation [A,B|C] indicates a list of the form [A,B,...] where the ... is list C.
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. A single underscore stands for an anonymous, or don't-care, variable.
Comments in Prolog start with % and end at the end of a line.
If you use numbers in the representation of the state, then you will need to perform arithmetic. Prolog is not really designed for arithmetic, and it is a little awkward. You can write X is E to ask for X to be unified with the result of evaluating expression E. For example, W is 3 + 4 binds W to 7. You can perform order tests using operators < and >.
You will find it simpler to represent numbers as lists. For example, the list [a,a,a] might represent the number 3. To test that a number is at least 2, all you have to do is a pattern match to see that it has the form [A,B|C]. This will result in shorter and simpler Prolog code than direct use of numbers.
Hand your program in using the handin utility as assignment 8.