There are three missionaries and three cannibals on the west bank of a river. There is a boat on the west bank that can hold no more than two people. The missionaries wish to cross to the east bank. But they have a problem: If on either bank the cannibals ever outnumber the missionaries, the outnumbered missionaries will be eaten.

**Question:** Is there a way for the missionaries to get their wish--to get to the
east bank without losing anyone?

**Application:** This puzzle is vaguely reminiscent of scheduling problems. For
example, a number of meetings must be held, some of which must run in parallel. Various
constraints exist on scheduling all the meetings. Some must precede others, while some
must not be held in parallel. Certain speakers have prior travel arrangements, and so must
give various talks consistent with their prior plans. The question is: With all of the
constraints, does a schedule exist that conforms to the requirements?

**A detailed discussion** of this puzzle and others is given in *Automated
Reasoning: Introduction and Applications,* by Larry Wos, Ross Overbeek, Ewing Lusk,
and Jim Boyle. The book, published by McGraw-Hill, includes a diskette of the automated
reasoning program OTTER, which can be used to solve puzzles as well as extremely
challenging problems in mathematics and logic.

Those who have OTTER already may simply take the input and start experimenting. The clauses are explained separately.