How to Solve the Missionaries and Cannibals Problem

The classic missionaries and cannibals puzzle asks how to move three missionaries and three cannibals across a river without ever leaving missionaries outnumbered by cannibals on a bank. The usual version has a boat that carries one or two people. Under those rules, everyone can cross in 11 one-way trips.

The solution depends on tracking both banks and the boat’s location. A bank with no missionaries is safe, even if cannibals are present; otherwise, it must have at least as many missionaries as cannibals.

Rules and notation

This solution uses the standard assumptions: there are three people of each kind, the boat holds one or two passengers, and every passenger can operate it. The boat cannot cross empty. The safety rule applies to both banks, not only the starting bank.

Write the number of missionaries and cannibals left on the starting bank as (M, C). The other bank contains 3 − M missionaries and 3 − C cannibals. For example, (2, 1) means two missionaries and one cannibal remain on the starting bank.

In the table, M means a missionary, C means a cannibal, an arrow to the right means crossing to the far bank, and an arrow to the left means returning. The counts shown are those left on the starting bank after the trip.

The 11-crossing solution

Trip	Passengers	Left-bank count after trip
Start	—	(3, 3)
1	CC →	(3, 1)
2	C ←	(3, 2)
3	CC →	(3, 0)
4	C ←	(3, 1)
5	MM →	(1, 1)
6	MC ←	(2, 2)
7	MM →	(0, 2)
8	C ←	(0, 3)
9	CC →	(0, 1)
10	C ←	(0, 2)
11	CC →	(0, 0)

The last row means everyone is on the far bank. Each crossing carries at least one person, and none carries more than two.

Why the sequence is safe

Check each bank after every trip. If a bank has missionaries, its cannibal count must not be greater than its missionary count. If it has no missionaries, the cannibals there cannot harm anyone, so that bank is safe.

For instance, after trip 5, the starting bank has one missionary and one cannibal, while the far bank has two of each. After trip 7, the starting bank has no missionaries and two cannibals; that is allowed. Trip 8 temporarily returns a cannibal, leaving three cannibals on the starting bank, but still no missionaries there. The other bank has three missionaries and no cannibals. The same check works for every row in the table.

The first four trips move cannibals across and back so that the missionaries can cross as a pair. The mixed return on trip 6 resets the distribution: two missionaries and two cannibals are on the starting side, while one of each is on the far side. From there, the missionaries cross, and the remaining cannibals are shuttled until everyone is across.

Why 11 trips is minimal

The table gives a solution, but it is also possible to check that a shorter one does not exist. Represent a situation by the number of missionaries and cannibals on the starting bank and the boat’s side. There are at most 4 × 4 × 2 = 32 such states, and some are invalid because they break the safety rule.

From each valid state, try every possible boatload—one missionary, one cannibal, two missionaries, two cannibals, or one of each—provided those passengers are on the bank with the boat. Keep only moves that leave both banks safe. A breadth-first search explores states in order of crossing count, so the first time it reaches the all-across state, it has found a shortest solution. For the standard rules, that first distance is 11 crossings.

Common mistakes

• Checking only the starting bank: The far bank must satisfy the same safety rule.
• Treating an empty-missionary bank as unsafe: The usual rule forbids cannibals from outnumbering missionaries only when missionaries are present.
• Forgetting the boat’s position: Only people on the boat’s current bank can board it.
• Allowing an empty crossing: Each trip must carry at least one passenger.
• Assuming every version has the same answer: If the boat capacity, number of people, or safety rule changes, the solution and shortest crossing count may change.