thumb|upright|Graphic of solution to Jealous Husbands River Crossing Problem.
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing logic puzzles. 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.
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. And, in some variations, one of the cannibals has only one arm and cannot row.<sup>, p. 291.</sup>
thumb|Timeline solutions to both jealous husbands, and missionaries and cannibals problems, with the vertical axis denoting time, blue denoting husbands or missionaries, red denoting wives or cannibals, yellow denoting the boat, and lines of the same type denoting married couples (in the jealous husbands problem).<br />The solid red line optionally denotes the cannibal unable to row.<br />In the right figure, if a wife or cannibal staying on the boat counts as being by herself (circled), a shorter solution is possible.
{| class="wikitable"
! Trip number
! Starting bank
! Travel
! Ending bank
|-
| (start)
| αa βb γc
|
|
|-
|1
|βb γc
|αa →
|
|-
|2
|βb γc
|←α
|a
|-
|3
|α β γ
|bc →
|a
|-
|4
|α β γ
| ← a
|b c
|-
|5
|αa
| βγ →
|b c
|-
|6
|αa
|← βb
|γc
|-
|7
|a b
|αβ →
|γc
|-
|8
|a b
|← c
|α β γ
|-
|9
|b
|a c →
|α β γ
|-
|10
|b
|← β
|αa γc
|-
|11
|
|βb →
|αa γc
|-
|(finish)
|
|
|αa βb γc
|}
This is a shortest solution to the problem, but is not the only shortest solution.
If a woman in the boat at the shore (but not on the shore) counts as being by herself (i.e. not in the presence of any men on the shore), then this puzzle can be solved in 9 one-way trips:
{| class="wikitable"
! Trip number
! Starting bank
! Travel
! Ending bank
|-
| (start)
|αa βb γc
|
|
|-
|1
|βb γc
|αa →
|
|-
|2
|βb γc
|← a
|α
|-
|3
|β γc
|ab →
|α
|-
|4
|β γc
| ← b
|αa
|-
|5
|γc
| βb →
|αa
|-
|6
|γc
|← b
|αa β
|-
|7
|γ
|bc →
|αa β
|-
|8
|γ
|← c
|αa βb
|-
|9
|
|γc →
|αa βb
|-
|(finish)
|
|
|αa βb γc
|}
Variations
An obvious generalization is to vary the number of jealous couples (or missionaries and cannibals), the capacity of the boat, or both. If the boat holds 2 people, then 2 couples require 5 trips; with 4 or more couples, the problem has no solution. If the boat can hold 3 people, then up to 5 couples can cross; if the boat can hold 4 people, any number of couples can cross.
If an island is added in the middle of the river, then any number of couples can cross using a two-person boat. If crossings from bank to bank are not allowed, then 8n−6 one-way trips are required to ferry n couples across the river;
See also
- Wolf, goat and cabbage problem
- Circumscription (logic)