Homework Assignment 6

CS 2360
Fall 1998
Homework Assignment 6
Due no later than 8:00am, Monday, November 9, 1998
 
Three married couples are enjoying a lovely picnic on the bank of a river.
After their picnic, they'd like to visit the other side of the river.  As
it turns out, there's a canoe nearby, but it can hold only two people at
one time.  Thus, crossing the river means that two people go across, one 
gets out of the canoe, the other goes back across the river, picks up 
another person, and so on.  So while getting everyone across the river is
a little bit tedious, it's pretty straightforward.  Or at least it would be
except for those suspicious wives!
 
As I said in class today, this particular puzzle isn't especially politically
correct, but try to cope.  Here are the constraints those pesky wives have
added to this problem (as quoted from the puzzle I brought to class today):
"Each wife has an objection to her husband crossing with any other woman
or with leaving her husband alone with them on either side of the river.
Remember, the boat holds only two people and someone has to bring the boat
back for the rest of the people to use it."
 
Now getting these six folks across the river is going to be more complicated
than first expected.  It's time for you to come to their rescue.  Your job
is to write a program using Common LISP that will solve the problem if getting
all three married couples from one side of the other without running afoul
of the wives' objections.  The program you write is to use depth-first state-
space search with backtracking to solve this river crossing problem.
 
The top-level function is to be called CROSS-THE-RIVER and will take four
arguments.  The first argument is the initial state of the problem, which
might look like this:
 
  ((MR_BLUE MR_RED MR_YELLOW MRS_RED MRS_YELLOW MRS_BLUE) (LEFT) ())
 
This list consists of three sublists.  The leftmost sublist contains
the names of all the people on the left bank of the river.  The order of
the names in this sublist or the other sublists is unimportant.  The middle
sublist contains the names of all the people in the canoe, plus an indicator
to tell you which bank the canoe is on (LEFT or RIGHT).  You can assume that
the symbols LEFT and RIGHT are reserved, and that no passenger in the boat
will ever be named "LEFT" or "RIGHT".  The rightmost sublist contains the 
names of all the people on the right bank of the river.
 
Note that while this is the start state described in the story above, we might 
want to give you a different start state, such as:
 
  ((MR_RED MR_YELLOW MRS_RED MRS_YELLOW) (MR_BLUE RIGHT) (MRS_BLUE))
 
so be ready to accept any "legal" state description as an initial state.
 
The second argument is the goal state and has the same syntax as the
initial state.  Again, any "legal" state description is acceptable here.
The goal state described in the story above looks like this (again,
order of names is unimportant):
 
  (() (RIGHT) (MR_YELLOW MRS_RED MR_BLUE MR_RED MRS_YELLOW MRS_BLUE))
 
The third argument is important information about these six people that
will help you write flexible code that enforces the constraints imposed by
the wives:
 
  ((MR_BLUE (GENDER MALE) (MARRIED-TO MRS_BLUE))
   (MRS_BLUE (GENDER FEMALE) (MARRIED-TO MR_BLUE))
   (MR_RED (GENDER MALE) (MARRIED-TO MRS_RED))
   (MRS_RED (GENDER FEMALE) (MARRIED-TO MRS_RED))
   (MR_YELLOW (GENDER MALE) (MARRIED-TO MRS_YELLOW))
   (MRS_YELLOW (GENDER FEMALE) (MARRIED-TO MR_YELLOW)))
 
Why do you need this extra information?  Doesn't "Mrs. Blue" implicitly
tell you that she's female and married to "Mr. Blue"?  Yes, but we like
to make knowledge explicit where we can, right?  That way, you don't have
to write code to extract that information from just a name.  Furthermore,
we can then give you a different set of names, like "Bob" and "Carol" and
"Ted" and "Alice" and your program will still be able to solve the problem,
given the appropriate information passed as the third argument.
 
The fourth argument is either nil or non-nil.  If the value is non-nil,
your program should print to the terminal a trace of the sequence of
states or moves being tried as the search progresses.  The trace should
also point out where the program runs into a dead end and has to
backtrack, as well as pointing out when the goal has been reached.  If
the second argument is nil, no trace should be printed.  You'll want to
look up some of the print I/O stuff in some Common LISP book to make
this pretty.  What the trace actually looks like is more or less up to
you, but it should be somehow informative to the TAs.
 
When the goal has been reached, CROSS-THE-RIVER should terminate and 
return a list of successive states that constitutes the path from the
initial state to the goal state.  If your program never finds the goal, 
it should merely return NIL.  Oh, keep in mind that not only can people 
cross from the left bank to the right bank, they can also leave the right
bank, hop in the boat, and cross back to the left bank.
 
You'll want to write your program to be general enough that we can
change the number of couples involved.  Grading will be based in part
on the degree of flexibility that your code exhibits, so aim to write
a program that can solve a general class of problems, not just this 
specific example.  If you can figure out a nice way to make it easy to
change the constraints on this problem, you'll get an even better score.
And note that we might have to change the specifications for this assignment
if we find out that we've overlooked something important, so don't forget
that abstraction.
 
Follow the same guidelines that we've used in the past:  lots of
well-abstracted, well-named, well-documented, cohesive, and readable 
functions, but no global variables, no assignment, and none of those 
traditional looping constructs that we haven't talked about yet---in 
short, use anything from LISP that doesn't take you outside the functional
programming paradigm (except for print operations).

 
 
Copyright 1998 by Kurt Eiselt.  All rights reserved.