Harvey Mudd College
Computer Science 60
Assignment 9, Due Friday, November 10, by midnight

Prolog Puzzles

This assignment introduces some of the more impressive capabilities of prolog (and to convince prolog to exhibit them). Problems 1-3 are prolog "programs" (really predicates). They should be submitted all together in a file named puzzles.pl . There is a (small) file named /cs/cs60/as/a9/puzzles.pl with a few predicates to start you out.

Problem 1

Write a prolog clause (or a number of clauses) that implement remove, where remove(E, LBefore, LAfter) indicates that LAfter is the same as list LBefore, except that the first occurrence (if there is one) of element E is removed from LAfter. If E is not in LBefore, then LAfter is identical to LBefore.

For example, possible runs of remove might include 

?- remove(1, [2, 1, 3, 1], [2, 3, 1]).

yes


?- remove(X, [2, 1, 3, 1], [2, 1, 1]).

X = 3 ;
no


?- remove(1, [1, 2, 3, 1, 2], X).

X = [2,3,1,2] ;
no


?- remove(1, X, [2, 3, 4]).

X = [1,2,3,4] ;
X = [2,1,3,4] ;
X = [2,3,1,4] ;
X = [2,3,4] ;
X = [2,3,4,1] ;
no
You may want to use the member predicate we discussed in class as an example. Note that depending on your exact implementation of remove, the order in which the answers appear (in the examples above) may be different.

Problem 2

Pattern matching is an important task in many applications such as cryptography and DNA sequencing. This problem asks you to find a sublist wherever it might appear within a larger list. Write the predicate find(Pattern, Target, Index) that takes two lists Pattern and Target and a non-negative integer Index as input. This predicate is true if and only if Pattern occurs inside list Target beginning at position Index. Note that there may be more than one Index at which the pattern is located.

For example, here is a Prolog query and response: 

      | ?- find([1, 2], [1, 2, 1, 2, 1], 0).
      yes
Notice that pattern [1, 2] occurs in target [1, 2, 1, 2, 1] beginning at position 0 of the target (that is, the very beginning of the target list). 
    [1, 2, 1, 2, 1]
     ^
     |
     The pattern [1, 2] appears beginning right here at location 0.
     I'm looking for a 1 followed immediately by a 2 and I find it
     beginning here!
It also occurs again at position 2 of the target. 
    [1, 2, 1, 2, 1]
           ^
           |
           The pattern [1, 2] appears beginning right here at location 2.
Thus, here's another Prolog query and response: 
      | ?- find([1, 2], [1, 2, 1, 2, 1], 2).        
      yes
In fact, these are the only two occurences as indicated by the following Prolog query and response: 
      | ?- find([1, 2], [1, 2, 1, 2, 1], X).   

      X = 0 ;
      X = 2 ;
      no
Write the rules for the predicate find. You may want to write some helper predicates to make find easier. Here are a couple of other example runs from find: 
      | ?- find( P, [1,2,3,4], 1 ).

      P = [] ;
      P = [2] ;
      P = [2,3] ;
      P = [2,3,4] ;
      no


      | ?- find( P, [a,b], X ).

      P = [],
      X = 0 ;
      
      P = [a],
      X = 0 ;
      
      P = [a,b],
      X = 0 ;
      
      P = [],
      X = 1 ;
      
      P = [b],
      X = 1 ;
      
      P = [],
      X = 2 ;
      
      no
find will not be able to answer queries like 
      | ?- find( [1,2], L, 0 ).
because prolog has no idea what to put after the 1 and 2 into the list L. (It will give some internal variable name and then, perhaps, head off into an infinite loop looking for more things to include.)

Problem 3

In this problem you will be solving (or writing prolog predicates to solve) the general Missionaries and Cannibals problem. You may want to use the example puzzles -- particularly the towers of Hanoi problem -- done in class as a guide.

In this problem, there are some number of missionaries and cannibals on the banks of a river and only one boat available. The goal is to achieve some desired configuration of missionaries and cannibals on the two sides of the river, but you are subject to two constraints. First, the number of cannibals can never be greater than the number of missionaries on either side of the river. If, however, there are no missionaries at all on one riverbank, then there may be any number of cannibals there. The second constraint is that there is only one boat available. Thus, it has to go back and forth across the river. The boat must have at least one person to navigate it (either a missionary or a cannibal) and can fit at most two people (any combination of missionaries and cannibals).

The problem is to write a prolog predicate solveMC that will enable queries to solve arbitrary missionaries and cannibals problems. Write solveMC with the following arguments: 

solveMC( MoveList, StateList, StartState, EndState ) :- ...
the first argument MoveList is the list of legal moves that will get the missionaries and cannibals from their initial configuration (StartState) to their final configuration (EndState). The second argument StateList is a list of all of the configurations that have been seen "so far." The states in this list must be avoided (to avoid loops).

The StartState and EndState are lists of exactly five elements: 

  [ #M's-left,  #C's-left,  #M's-right,  #C's-right , boatLocation ]
which you may want to pattern-match as 
  [ ML, CL, MR, CR, left ]    or    [ ML, CL, MR, CR, right ]
In fact, since you have both "before" and "after" lists, you might want to pattern match with something like 
  [ MLb, CLb, MRb, CRb, left ]      and     [ MLa, CLa, MRa, CRa, right ]
to indicate Missionaries vs. Cannibals, Left vs. Right, and before vs. after. The position of the boat will change depending on what particular move is being made (see the list of 10 possible moves below.) Because of this representation, the StartState at the very beginning of the 3-missionaries, 3-cannibals puzzle is 
  [ 3, 3, 0, 0, left ]
the corresponding EndState is 
  [ 0, 0, 3, 3, right ] .

Other tips

You will want to use the member predicate (gone over in class and in /cs/cs60/as/a10/puzzles.pl). You will also want to write your own "helper" predicates -- for example, a predicate named valid that checks that a each river bank (left and right) is valid under the problem's constraints. Another helpful predicate might be move that describes each of the legal moves. There are 10 legal moves, listed below. Please use these names (to make checking your work easier): 

mToL      - one missionary from right to left
cToL      - one cannibal from right to left
mmToL     - two missionaries from right to left
ccToL     - two cannibals from right to left
cmToL     - one missionaries and one cannibal from right to left

mToR      - one missionary from left to right
cToR      - one cannibal from left to right
mmToR     - two missionaries from left to right
ccToR     - two cannibals from left to right
cmToR     - one missionaries and one cannibal from left to right

Example runs

Here are some example runs of the solveMC predicate -- keep in mind that, depending on the order of things in your implementation, your solutions may come in different order and they may be repeated several times. This is absolutely OK. (It does make it difficult to automate grading, however, which is why the submission script does not run tests this week.) 

/* Here is the original 3-missionaries, 3-cannibals problem */



?- solveMC( MoveList, [], [ 3, 3, 0, 0, left ], [ 0, 0, 3, 3, right ] ).

MoveList = [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR]; 

<plus others, you may have a different initial solution>






/* Just getting one missionary and one cannibal across */



?- solveMC( MoveList, [], [ 1, 1, 0, 0, left ], [ 0, 0, 1, 1, right ] ).

MoveList = [cmToR] ;
<plus repeats, though there are no other solutions>
<that do not repeat states.>








/* There is no solution that gets 4 missionaries and 4 cannibals across. */

?- solveMC( MoveList, [], [ 4, 4, 0, 0, left ], [ 0, 0, 4, 4, right ] ).

no


You can also use setof to get all distinct solutions. 

/* There are four distinct solutions to the original */

a(S) :- setof(Moves, solveMC(Moves, [], [ 3, 3, 0, 0, left ], [ 0, 0, 3, 3, right ] ), S).  

?- a(S).

S = [[ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR],
     [ccToR,cToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR],
     [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,cToL,ccToR],
     [cmToR,mToL,ccToR,cToL,mmToR,cmToL,mmToR,cToL,ccToR,mToL,cmToR]] ;
     
no


/* There is only one solution to the single missionary, single cannibal problem */

b(S) :- setof(Moves, solveMC(Moves, [], [ 1, 1, 0, 0, left ], [ 0, 0, 1, 1, right ] ), S).  

?- b(S).

S = [[cmToR]] ;

no
Note that all of theses solutions do not allow repeated states (otherwise whenever there was one solution, there would be infinitely many, because a cannibal could cross the river any number of times after the initial solution was found).



Testing

Prolog doesn't offer the kinds of redirection that rex does, so there are no test files to use this week. However, I would suggest testing your prolog predicates with the examples given in the problem descriptions above.

Reading

Prolog, Predicate logic, and proving programs correct are all covered in Chapter 10 of the book.

Submission

The puzzles.pl file with your prolog solutions should be submitted in the usual way, i.e., with 

% cs60submit 9
The submission script will also look for a fours.pl problem, in case you tried the extra credit.

Extra Credit

For optional bonus credit (up to 20%), write a prolog predicate (you will need helper predicates to do this) that "solves" the four fours problem. This is a very open-ended extra credit -- all solutions are necessarily partial solutions. You should consider solving the problem from 0 to 100 an absolute success. Martin Gardener (a long-time columnist for Scientific American) claimed that solving it for the integer 113 was impossible, though it's not proven one way or the other! If you do try it, submit your prolog code in a separate file named fours.pl.

The four fours problem is the following challenge: for each nonnegative integer, write that integer as an arithmetic combination of exactly four fours. Some of the many possible examples for the first few (nonnegative) integers are these: 

0 =  4 + 4 - 4 -4

1 =  44 / 44

2 =  (4/4) + (4/4)
  
3 =  4 - (4/4) - sqrt(4)
  
4 =  .4 * (4 + 4 + sqrt(4))
etcetera.

The permitted operations are

As odd as it may seem, this problem has received a lot of attention in the formal (and not so formal) mathematical literature. Feel free to develop your own representations for sequences of operators and for the predicates you use. (Additional information on prolog is available from this site.)