Missionaries and cannibals problem
From Wikipedia, the free encyclopedia
The missionaries and cannibals problem is a logic puzzle commonly used as an example of using abstract concepts to solve a problem. It was made famous within the field of artificial intelligence by Saul Amarel, who used the problem as an example in a paper on problem representation.
Contents |
[edit] The problem
A common version of the problem is as follows: Three missionaries and three cannibals stand on the bank of a river that they wish to cross. There is a boat available which can ferry up to two people across. The goal is to find a schedule for ferrying all the cannibals and all the missionaries safely across the river. The constraint is that, if at any point the cannibals outnumber the missionaries on either bank, the cannibals will eat the missionaries. Note that the boat cannot cross the river by itself with no people on board.
[edit] 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
[edit] Variations
- One variation is to start with 5 missionaries, 5 cannibals, and a boat that holds 3 people.
- The politically correct version of the problem is given with wolves and sheep as the subjects.
- A much less politically correct version is often told as a variety of ethnic joke, with one putatively dangerous group of people (for example, Italian men) preying on a helpless group (for example, virtuous French maids).
