Missionaries and cannibals problem

[1] A system for solving the Missionaries and Cannibals problem whereby the current state is represented by a simple vector ⟨m, c, b⟩.

The state would reflect that there are still three missionaries and two cannibals on the wrong side, and that the boat is now on the opposite bank.

The five possible actions (⟨1,0,1⟩, ⟨2,0,1⟩, ⟨0,1,1⟩, ⟨0,2,1⟩, and ⟨1,1,1⟩) are then subtracted from the initial state, with the result forming children nodes of the root.

The algorithm continues alternating subtraction and addition for each level of the tree until a node is generated with the vector ⟨0,0,0⟩ as its value.

This is the goal state, and the path from the root of the tree to this node represents a sequence of actions that solves the problem.

The first known appearance of the jealous husbands problem is in the medieval text Propositiones ad Acuendos Juvenes, usually attributed to Alcuin (died 804).

The problem was later put in the form of masters and valets; the formulation with missionaries and cannibals did not appear until the end of the 19th century.[1], p.

Cadet de Fontenay considered placing an island in the middle of the river in 1879; this variant of the problem, with a two-person boat, was completely solved by Ian Pressman and David Singmaster in 1989.

Graphic of solution to Jealous Husbands River Crossing Problem.
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).
The solid red line optionally denotes the cannibal unable to row.
In the right figure, if a wife or cannibal staying on the boat counts as being by herself (circled), a shorter solution is possible.