Easy River Crossing

By /

Three cannibals and three anthropologists have to cross a river. the boat they have is only big enough for two people. if at any point in time there are more cannibals on one side of the river than anthropologists, the cannibals will eat them. what plan can the anthropologists use for crossing the river so they don’t get eaten?

remember! the boat can’t cross the river by itself, someone has to be in it to row it across.

a much harder river crossing problem will appear later this week.

A - anthropologist
C - cannibal
++ - boat
 
        river
AAA |============|
    |++          |
CCC |============|
 
need to make it
        river
    |============| AAA
    |          ++|
    |============| CCC

note that if you violate the “anthropologists > cannibals” rule at any point in time, it is illegal.. for example if a boat with a cannibal and an anthropologist travels to a shore with one cannibal on it, then # cannibals > # anthropologists, even if you say the anthropologist immediately takes the boat back.

Solution

Let W be the west shore which they are all on. Let E be the east shore where they want to go.

1. A and C cross
W = { A, A, C, C }
E = { A, C }
 
2. A returns
W = { A, A, A, C, C }
E = { C }
 
3. C and C cross
W = { A, A, A }
E = { C, C, C }
 
4. C returns
W = { A, A, A, C }
E = { C, C }
 
5. A and A cross
W = { A, C }
E = { A, A, C, C }
 
6. A and C return
W = { A, A, C, C }
E = { A, C }
 
7. A and A cross
W = { C, C }
E = { A, A, A, C }
 
8. C returns
W = { C, C, C }
E = { A, A, A }
 
9. C and C cross
W = { C }
E = { A, A, A, C, C }
 
10. C returns
W = { C, C }
E = { A, A, A, C }
 
11. C and C cross
W = true
E = { A, A, A, C, C, C }

2026 Update: Constraint Satisfaction — The Graph Search Formulation

River crossing puzzles (farmer, fox, chicken, grain) are textbook constraint satisfaction problems (CSP) that model real software challenges: dependency resolution, distributed transaction coordination, and resource allocation with mutual exclusion constraints.

The BFS state-space search approach (general solution):

from collections import deque

def solve_river_crossing(items, constraints, boat_capacity=1):
    """
    Generic river crossing solver via BFS.
    items: list of item names
    constraints: list of (item_a, item_b) pairs that can't be left alone
    boat_capacity: max items farmer can carry per trip (besides farmer)
    """
    from itertools import combinations

    n = len(items)
    # State: frozenset of items on right bank (farmer position implicit)
    # Farmer starts on left (0), moves to right (1)
    start = (frozenset(), False)  # (right_bank_items, farmer_on_right)
    goal_items = frozenset(range(n))

    def is_safe(right_items, farmer_on_right):
        left_items = set(range(n)) - right_items
        # Check constraints on the bank without farmer
        unguarded = right_items if not farmer_on_right else left_items
        for a, b in constraints:
            if a in unguarded and b in unguarded:
                return False
        return True

    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        (right, farmer_right), path = queue.popleft()
        if right == goal_items and farmer_right:
            return path

        # Generate moves: farmer crosses with 0 to boat_capacity items
        source = right if farmer_right else set(range(n)) - right
        new_farmer = not farmer_right

        for size in range(0, boat_capacity + 1):
            for cargo in combinations(source, size):
                new_right = (right | set(cargo)) if not farmer_right else (right - set(cargo))
                new_state = (frozenset(new_right), new_farmer)
                if new_state not in visited and is_safe(frozenset(new_right), new_farmer):
                    visited.add(new_state)
                    queue.append((new_state, path + [new_state]))

    return None

Engineering parallel in 2026: Kubernetes pod scheduling faces the same constraint — certain pods can’t co-locate (like fox and chicken). The Kubernetes scheduler solves this as a CSP with affinity/anti-affinity rules. Understanding river crossing helps you reason about these constraints.

Scroll to Top