The missionaries and cannibals problem is a logic game or puzzle commonly used as an example of using abstract concepts to solve a problem. It was made famous within the field of Artificial Intelligence research by Dr. Saul Amarel, who used the problem as an example in a paper on problem representation.

The Problem

The setup is generally as follows: A number of missionaries and a number of cannibals stand on the bank of a river. There is a boat available which can ferry up to two people across. The problem is that, if at any point the cannibals outnumber the missionaries on the bank, the cannibals will eat the missionaries. The goal is to find a schedule for ferrying all the cannibals and all the missionaries safely across the river.

Solution

One solution (the three numbers representing the number of missionaries, cannibals, and boats on the near bank) is as follows:

331, 310, 321, 300, 311, 110, 221, 020, 031, 010, 021, 000

Variations

• The politically correct version of the problem is given with wolves and sheep as the subjects.
• Other variations include more than two different types of player. In one variation, there is a wolf, a goat, and a cabbage on one side; the wolf will eat the goat if unattended, and the goat will eat the cabbage.

External Links

Amarel, S. (1968). On representations of problems of reasoning about actions, Machine Intelligence (http://www.cc.gatech.edu/~jimmyd/summaries/amarel1968-1.html)