Missionaries and cannibals problem: Difference between revisions
Spacepotato (talk | contribs) →Solution: expand, fix numbering |
Spacepotato (talk | contribs) →Solution: fix ref |
||
| Line 8: | Line 8: | ||
==Solution== |
==Solution== |
||
The earliest solution known to the jealous husbands problem, using 11 one-way trips, is as follows. The married couples are represented as ''A'' (male) and ''a'' (female), ''B'' and ''b'', and ''C'' and ''c''.<ref name=b>p. 291, Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia, |
The earliest solution known to the jealous husbands problem, using 11 one-way trips, is as follows. The married couples are represented as ''A'' (male) and ''a'' (female), ''B'' and ''b'', and ''C'' and ''c''.<ref name=b>p. 291, Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia, |
||
Raffaella Franci, pp. 289–306, ''From China to Paris: 2000 Years |
Raffaella Franci, pp. 289–306, ''From China to Paris: 2000 Years Transmission of Mathematical Ideas'', edited by Yvonne Dold-Samplonius et al., |
||
Transmission of Mathematical Ideas'', edited by Yvonne Dold-Samplonius et al., |
|||
Franz Steiner Verlag: 2002, ISBN 3515082239.</ref> |
Franz Steiner Verlag: 2002, ISBN 3515082239.</ref> |
||
Revision as of 00:34, 9 February 2008
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems.[1] The missionaries and cannibals problem is a well-known toy problem in artificial intelligence, where it was used by Saul Amarel as an example of problem representation.[2][3]
The problem
In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board.[1]
In the jealous husbands problem, the missionaries and cannibals become three married couples, with the constraint that no woman can be in the presence of another man unless her husband is also present. Under this constraint, there cannot be both women and men present on a bank with women outnumbering men, since if there were, some woman would be husbandless. Therefore, upon changing women to cannibals and men to missionaries, any solution to the jealous husbands problem will also become a solution to the missionaries and cannibals problem.[1]
Solution
The earliest solution known to the jealous husbands problem, using 11 one-way trips, is as follows. The married couples are represented as A (male) and a (female), B and b, and C and c.[4]
| Trip number | Starting bank | Travel | Ending bank |
|---|---|---|---|
| (start) | Aa Bb Cc | ||
| 1 | Bb Cc | Aa → | |
| 2 | Bb Cc | ← A | a |
| 3 | A B C | bc → | a |
| 4 | A B C | ← a | b c |
| 5 | Aa | BC → | b c |
| 6 | Aa | ← Bb | Cc |
| 7 | a b | AB → | Cc |
| 8 | a b | ← c | A B C |
| 9 | b | a c → | A B C |
| 10 | b | ← B | Aa Cc |
| 11 | Bb → | Aa Cc | |
| (finish) | Aa Bb Cc |
This is a shortest solution to the problem, but is not the only shortest solution.[4]
As mentioned previously, this solution to the jealous husbands problem will become a solution to the missionaries and cannibals problem upon replacing men by missionaries and women by cannibals. In this case we may neglect the individual identities of the missionaries and cannibals. The solution just given is still shortest, and is one of four shortest solutions.[5]
Variations
- One variation is to start with 5 missionaries, 5 cannibals, and a boat that holds 3 people.
- Some variations have no solutions, such as starting with 4 missionaries, 4 cannibals and a boat that holds 2 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).
- In his novel With a Tangled Skein, Piers Anthony includes a version where the cannibals are lecherous demons, the missionaries are a human woman and two demons disguised as women, and the river is the Lethe.
See also
References
- ^ a b c "The Jealous Husbands" and "The Missionaries and Cannibals", Ian Pressman and David Singmaster, The Mathematical Gazette, 73, #464 (June 1989), pp. 73–81.
- ^ On representations of problems of reasoning about actions, Saul Amarel, pp. 131–171, Machine Intelligence 3, edited by Donald Michie, Amsterdam, London, New York: Elsevier/North-Holland, 1968.
- ^ p. 9, Searching in a Maze, in Search of Knowledge: Issues in Early Artificial Intelligence, Roberto Cordeschi, pp. 1–23, Reasoning, Action and Interaction in AI Theories and Systems: essays dedicated to Luigia Carlucci Aiello, edited by Oliviero Stock and Marco Schaerf, Lecture Notes in Computer Science #4155, Berlin/Heidelberg: Springer, 2006, ISBN 978-3-540-37901-0.
- ^ a b p. 291, Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia, Raffaella Franci, pp. 289–306, From China to Paris: 2000 Years Transmission of Mathematical Ideas, edited by Yvonne Dold-Samplonius et al., Franz Steiner Verlag: 2002, ISBN 3515082239.
- ^ Cannibals and missionaries, Ruby Lim, pp. 135–142, Conference proceedings: APL '92, the International Conference on APL, 6-10 July 1992, St. Petersburg, Russia, edited by Lynne C. Shaw, et al., New York: Association for Computing Machinery, 1992, ISBN 0-89791-477-5.