Due: TBA
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. (Note that it is ok for there to be some positive number of cannibals and no missionaries on a bank, since then there are no missionaries to be eaten.)
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 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.
You can write the program either in Prolog or Astarte, but if you use Astarte you must use a logic programming style. Define predicates. Prolog is described in Chapter 31. Logic programming in Astarte is described in Chapter 32.
Use the Farmer/Wolf/Goat/Cabbage program in the book as a guide. Solutions to that are shown in a simple backtracking style (Section 28.3) and in a logic programming style (Section 32.3). Here are some suggestions.
Decide on a reasonable notion of a state. What do you need to know about a snapshot? 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. Here is a suggestion for representing a state.
Prolog. Make a state have the form state(L,R,B) where L describes who is on the left bank of the river, R describes who is on the right bank, and B is either left (indicating that the boat is on the left bank) or right (indicating that the boat is on the right bank). A bank can be described by a tree of the form bank(MS,CS) where MS is a list of m's and CS is a list of c's. For example, bank([m,m],[c]) indicates that this bank has two missionaries and one cannibal. The complete initial state is state(bank([m,m,m],[c,c,c]), bank([], []), left), assuming that all are initially on the left bank.
Astarte. Make a state have the form (L,R) where L describes who is on the left bank, R describes who is on the right bank. Describe a bank by a triple (m,c,b) where m is the number of missionaries, c is the number of cannibals and b is true if the boat is on this bank and false if the boat is not on this bank. For example, the initial state is ((3,3,true), (0,0,false)), showing 3 missionaries, 3 cannibals and the boat on the left bank; and 0 missionaries, 0 cannibals and no boat on the right bank.
Write a predicate follows(S,T) that is true if state T can immediately 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. You will find the definition of follows to be rather long. A simple approach is to used 10 axioms, one for each kind of move that can be made. (There are five kinds of moves from left to rignt, and five moves from right to left.)
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). That is, you will give follows a state and ask it to produce the next state.
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. You will find it useful to have a helper predicate that checks whether a given bank is admissible. Be sure to allow the case where there are no missionaries, even though there are more cannibals than missionaries. In a Prolog version, you might just want to use pattern matching in lists to test whether a bank is admissible. In an Astarte version, you will probably want to do the test by comparing numbers.
A plan is a list of states. You will find it convenient to represent plans backwards, so that 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. That is, in terms of the lists, L = Y ++ X and L = [G | Z] for some Z. It is intended to be used in mode plan(in,in,out). That is, you give it the desired partial plan and the desired goal, and it extends that partial to reach the goal
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".
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 decide not to follow my advice and, instead, to 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 >, but you must ensure that the things that you are comparing are numbers, not terms. Do not write X < Y + 1, since Y + 1 is not a number. (Y + 1 is an application of the + operator to Y and 1.)