Missionaries and Cannibals: Search Under Constraints

Three missionaries, three cannibals, one two-seat boat. The state representation that makes it tractable, why 12 of the 32 states are illegal, the full 11-move solution traced, and working BFS code.

Three missionaries and three cannibals stand on the west bank of a river. There is one boat, which holds at most two people and cannot cross empty. Get everyone to the east bank.

The catch: if cannibals ever outnumber missionaries on either bank, the missionaries are eaten.

This is the purest illustration of a constrained state space. The raw space is 32 states; the constraint kills half of them. What’s left is so small you can draw the entire graph — and seeing the whole thing at once teaches you something that a million-node search never will.

The problem

State representation

The naïve encoding — a list of which individual person is where — is a trap. Missionaries are interchangeable; so are cannibals. If you track individuals you multiply your state space by $3! \times 3! = 36$ for no gain.

Track counts on one bank only, plus where the boat is:

$\text{state} = (m, c, b)$

$m$ — missionaries on the west bank, $0 \le m \le 3$
$c$ — cannibals on the west bank, $0 \le c \le 3$
$b$ — boat side: $1$ = west, $0$ = east

The east bank follows for free: $(3 - m, 3 - c)$ . Storing it would let the two halves drift out of sync — a classic bug.

start = (3, 3, 1)     # everyone and the boat on the west bank
goal  = (0, 0, 0)     # everyone and the boat on the east bank

The constraint, stated precisely

A state is legal when, on each bank, either there are no missionaries at all, or missionaries are at least as many as cannibals:

$(m = 0 \lor m \ge c) \;\land\; (3 - m = 0 \lor 3 - m \ge 3 - c)$

The m = 0 escape clause is the part people forget. A bank with 0 missionaries and 3 cannibals is perfectly safe — there’s nobody to eat. The condition isn’t " $m \ge c$ ", it’s ” $m \ge c$ unless $m = 0$ ”.

def legal(state):
    m, c, _ = state
    if not (0 <= m <= 3 and 0 <= c <= 3):
        return False
    if m and m < c:              # west bank overrun
        return False
    if (3 - m) and (3 - m) < (3 - c):   # east bank overrun
        return False
    return True

Every state in the whole problem: $4 \times 4 \times 2 = 32$ . Run legal over all of them and 20 survive — the constraint deletes 12 states before the search takes a single step.

Where the pruning really pays is in the middle of the board. Work through the $(m, c)$ pairs and you find the space is nearly hollow:

Missionaries on the west bank	Legal cannibal counts	How many
0	0, 1, 2, 3	4 — no missionaries here to eat
1	1 only	1
2	2 only	1
3	0, 1, 2, 3	4 — the east bank is empty of missionaries

Ten $(m, c)$ pairs, doubled for the boat’s two positions, gives 20. But look at the rows for $m = 1$ and $m = 2$ : once the missionaries are split across the banks, the cannibals must be split identically. Every other arrangement is fatal. That’s the constraint doing real work — it collapses the interesting part of the space to a single thread, which is why the solution reads like a corridor rather than a search.

The habit to take away: legality isn’t a check you run at the end — it’s a pruning tool you apply when you generate each successor.

The operators

There are exactly five legal boat loads, since the boat carries 1 or 2 people and never crosses empty:

Load	$(\Delta m, \Delta c)$
1 missionary	(1, 0)
2 missionaries	(2, 0)
1 cannibal	(0, 1)
2 cannibals	(0, 2)
1 of each	(1, 1)

Apply them against the boat’s direction: if the boat is on the west ( $b = 1$ ), the load leaves the west bank, so subtract. If it’s on the east, the load returns, so add.

MOVES = [(1, 0), (2, 0), (0, 1), (0, 2), (1, 1)]

def successors(state):
    m, c, b = state
    sign = -1 if b == 1 else 1       # boat west → people leave west
    for dm, dc in MOVES:
        nxt = (m + sign * dm, c + sign * dc, 1 - b)
        if legal(nxt):
            yield nxt, f"{'→' if b == 1 else '←'} {dm}M {dc}C"

The branching factor is at most 5, and the constraint typically cuts it to 2 or 3. That’s why this problem is solvable by hand.

The whole solution, drawn out

With only 20 legal states the search barely has room to wander. Here is the entire 11-move solution — every state the boat passes through, both banks at once.

Two things pop out of the picture:

The state space is a corridor, not a web. With the constraint applied there are rarely more than two or three legal moves at any point, which is why a person can solve this by trial and error in a few minutes, and why BFS finds the answer after touching almost nothing.
The boat is never on the same side twice in a row. Every crossing must be followed by a return trip, so eleven moves means six trips east and five back — you spend nearly half your moves undoing distance.

The 11-move solution, traced

#	Boat load	West bank	East bank	Note
—	start	3M 3C 🚤	—
1	→ 1M 1C	2M 2C	1M 1C 🚤	balanced both sides
2	← 1M	3M 2C 🚤	1C	missionary returns alone
3	→ 0M 2C	3M 0C	3C 🚤	east is all cannibals — legal, no missionaries to eat
4	← 0M 1C	3M 1C 🚤	2C
5	→ 2M 0C	1M 1C	2M 2C 🚤	balanced both sides
6	← 1M 1C	2M 2C 🚤	1M 1C	the counter-intuitive move
7	→ 2M 0C	0M 2C	3M 1C 🚤	west is all cannibals — legal
8	← 0M 1C	0M 3C 🚤	3M 0C
9	→ 0M 2C	0M 1C	3M 2C 🚤
10	← 0M 1C	0M 2C 🚤	3M 1C
11	→ 0M 2C	—	3M 3C 🚤	✅ goal

Move 6 is where humans get stuck. After move 5 you have two missionaries and two cannibals safely across, and every instinct says send the boat back with one person. But rowing back a missionary and a cannibal — undoing apparent progress — is the only legal continuation. Any other return move either leaves cannibals outnumbering missionaries somewhere, or walks straight into a dead end.

This is the problem’s real lesson: in a constrained space, the greedy move is frequently illegal, and the correct move often looks like going backwards. A greedy or hill-climbing search — “maximise people on the east bank” — fails here. BFS, which has no notion of progress at all, succeeds.

There are exactly four distinct optimal solutions, all 11 moves. The one above and its mirror (start with 2 cannibals instead of 1 of each) are the two you’ll see in textbooks.

Full working code

from collections import deque

M_TOTAL = C_TOTAL = 3
MOVES = [(1, 0), (2, 0), (0, 1), (0, 2), (1, 1)]


def legal(state):
    m, c, _ = state
    if not (0 <= m <= M_TOTAL and 0 <= c <= C_TOTAL):
        return False
    if m and m < c:                                    # west bank
        return False
    em, ec = M_TOTAL - m, C_TOTAL - c
    if em and em < ec:                                 # east bank
        return False
    return True


def successors(state):
    m, c, b = state
    sign = -1 if b == 1 else 1
    for dm, dc in MOVES:
        nxt = (m + sign * dm, c + sign * dc, 1 - b)
        if legal(nxt):
            arrow = '→' if b == 1 else '←'
            yield nxt, f'{arrow} {dm}M {dc}C'


def solve():
    start, goal = (M_TOTAL, C_TOTAL, 1), (0, 0, 0)
    frontier = deque([(start, [])])
    seen = {start}
    while frontier:
        state, path = frontier.popleft()
        if state == goal:
            return path
        for nxt, action in successors(state):
            if nxt not in seen:
                seen.add(nxt)
                frontier.append((nxt, path + [action]))
    return None


def count_legal_states():
    return sum(legal((m, c, b))
               for m in range(M_TOTAL + 1)
               for c in range(C_TOTAL + 1)
               for b in (0, 1))


if __name__ == '__main__':
    print(f'Legal states: {count_legal_states()} of '
          f'{(M_TOTAL+1)*(C_TOTAL+1)*2} possible\n')

    plan = solve()
    m, c, b = M_TOTAL, C_TOTAL, 1
    print(f'   start           West: {m}M {c}C {"🚤" if b else "  "}   '
          f'East: {M_TOTAL-m}M {C_TOTAL-c}C {"  " if b else "🚤"}')
    for i, action in enumerate(plan, 1):
        dm, dc = int(action.split()[1][0]), int(action.split()[2][0])
        sign = -1 if b == 1 else 1
        m, c, b = m + sign * dm, c + sign * dc, 1 - b
        print(f'{i:>4}. {action:<10}  West: {m}M {c}C {"🚤" if b else "  "}   '
              f'East: {M_TOTAL-m}M {C_TOTAL-c}C {"  " if b else "🚤"}')
    print(f'\nSolved in {len(plan)} moves.')

Output:

Legal states: 20 of 32 possible

   start           West: 3M 3C 🚤   East: 0M 0C
   1. → 0M 2C     West: 3M 1C      East: 0M 2C 🚤
   2. ← 0M 1C     West: 3M 2C 🚤   East: 0M 1C
   3. → 0M 2C     West: 3M 0C      East: 0M 3C 🚤
   4. ← 0M 1C     West: 3M 1C 🚤   East: 0M 2C
   5. → 2M 0C     West: 1M 1C      East: 2M 2C 🚤
   6. ← 1M 1C     West: 2M 2C 🚤   East: 1M 1C
   7. → 2M 0C     West: 0M 2C      East: 3M 1C 🚤
   8. ← 0M 1C     West: 0M 3C 🚤   East: 3M 0C
   9. → 0M 2C     West: 0M 1C      East: 3M 2C 🚤
  10. ← 1M 0C     West: 1M 1C 🚤   East: 2M 2C
  11. → 1M 1C     West: 0M 0C      East: 3M 3C 🚤

Solved in 11 moves.

Note that this is not the solution traced above — BFS opened 2 cannibals before 1 of each, so it found a different 11-move path. Both are optimal. Which one a search returns depends entirely on the order you list the operators in MOVES, and that’s worth internalising: when several optimal solutions exist, BFS gives you an arbitrary one, not a canonical one. If you need reproducible output, fix the operator order and say so.

Variants and what breaks

The problem scales in an interesting way:

Missionaries / Cannibals	Boat capacity	Solvable?	Optimal moves
3 / 3	2	✅	11
4 / 4	2	❌ impossible	—
4 / 4	3	✅	9
5 / 5	3	✅	11
$n$ / $n$ ( $n \ge 4$ )	2	❌ impossible	—

4 and 4 with a two-seat boat has no solution. Nothing about the problem statement warns you; the impossibility only shows up when your BFS exhausts the frontier and returns None. Change one number and a solvable puzzle becomes unsolvable — which is an excellent reason to always handle the “search completed, no solution” case rather than assuming a path exists.

The related jealous husbands problem uses the same boat and river but different constraint: no wife may be with another man unless her husband is present. Because individuals are no longer interchangeable, you can’t compress to counts, and the state space is much larger.

Why this problem matters

River-crossing puzzles date to Alcuin of York around 800 AD — the wolf, goat and cabbage version. They survived into AI textbooks because they isolate one idea perfectly: the constraint is the problem.

Real systems where this exact shape appears:

Transaction scheduling — some operations must never be interleaved; the legal-state test is your isolation level.
Resource allocation with safety invariants — a chemical plant where certain reagent ratios must hold at all times, or a bank’s transfer sequence where no account may go negative mid-batch.
Air-traffic and dock scheduling — the boat is a runway or a berth; the constraint is separation minima.
Model checking — verifying a concurrent system is exactly “explore all reachable states, check the invariant holds in each”. Half the states being illegal is the normal case, and pruning them early is what makes verification possible.

And the practical takeaway for writing search code: test legality when you generate a successor, not when you pop it. Filtering at generation keeps illegal states out of the frontier entirely. It’s one line either way, and it halves your memory.

Where to go next

Problem Solving with AI: The State-Space Framework — the shared framework
Water Jug Problem — the other tiny-state-space classic
The 8-Puzzle — when the space is too big to draw
BFS Shortest Path — the algorithm doing the work here