Wolf, Goat and Cabbage

Problem. A farmer must ferry a wolf, a goat and a cabbage across a river. The boat holds the farmer plus at most one item. Left unattended, the wolf eats the goat, and the goat eats the cabbage. Get everything across.

The solution

1. Take the goat across          (wolf + cabbage safe together)
2. Return empty
3. Take the wolf across
4. Bring the GOAT back           <- the non-obvious step
5. Take the cabbage across
6. Return empty
7. Take the goat across

Seven crossings. The counter-intuitive step 4 — carrying something backwards — is what makes the puzzle interesting, and it is exactly why a naive forward-only greedy fails.

As a graph search

State: which of {farmer, wolf, goat, cabbage} are on the far bank — a 4-bit mask, so 16 states. The farmer’s position is one of the bits.

const int F = 1, W = 2, G = 4, C = 8;
 
bool safe(int s) {
    bool farmerLeft = !(s & F);
    // an item is in danger if it is alone with its predator on the other bank
    if (((s & W) != 0) == ((s & G) != 0) && (((s & G) != 0) != ((s & F) != 0))) return false;
    if (((s & G) != 0) == ((s & C) != 0) && (((s & G) != 0) != ((s & F) != 0))) return false;
    return true;
}
 
int bfs() {
    vector<int> dist(16, -1);
    queue<int> q;
    dist[0] = 0; q.push(0);                                // everything on the near bank
    while (!q.empty()) {
        int s = q.front(); q.pop();
        for (int item : {0, W, G, C}) {                    // 0 = cross alone
            if (item && (((s & item) != 0) != ((s & F) != 0))) continue;  // must be with the farmer
            int t = s ^ F ^ item;
            if (!safe(t) || dist[t] != -1) continue;
            dist[t] = dist[s] + 1;
            q.push(t);
        }
    }
    return dist[15];                                       // everything across
}

BFS over 16 states finds the 7-move solution instantly — and proves it is optimal, which the hand solution does not.

The lesson: model, then search

This puzzle is the smallest possible instance of a pattern that solves an entire family:

Puzzle	State	Constraint
Wolf, goat, cabbage	4 bits	no unsupervised predator/prey pair
Missionaries and cannibals	(missionaries, cannibals, boat) per bank	cannibals never outnumber missionaries
Jealous husbands	who is on each bank	no wife with another husband unaccompanied
Bridge and torch	who has crossed + torch side	the torch must accompany crossings
Water jugs	$(x, y)$ litres	capacities
15-puzzle	board configuration	adjacency
Sokoban	boxes + player	PSPACE-complete
Rubik’s cube	cube state	legal turns

Whenever a puzzle asks for the minimum number of moves and the state space is small, it is a BFS on an implicit graph.

The only real work is (1) encoding the state compactly, and (2) writing the safe / valid predicate. Everything else is boilerplate.

Missionaries and cannibals

Three missionaries and three cannibals, a boat holding two, and cannibals must never outnumber missionaries on either bank (or in the boat’s presence). State: $(m, c, boat side)$ with $m, c \in [0, 3]$ — 32 states, BFS gives the optimal 11 crossings.

Notably, the 4-and-4 version with a 2-person boat is unsolvable, which BFS discovers immediately and which is tedious to argue by hand.

Scaling up

When the state space is too large for plain BFS:

Size	Technique
$\leq 1 0^{7}$ states	BFS with a hash set or a bitset of visited states
$\leq 1 0^{14}$	bidirectional BFS
Larger, with a good heuristic	A* / IDA*
Symmetric states	canonicalise before hashing
Very large	pattern databases, or accept a heuristic solution

Canonicalisation deserves emphasis: if the state has symmetries (interchangeable items, board reflections), mapping each state to a canonical representative before inserting into the visited set can shrink the search by a large constant factor.

Why it is worth knowing

It is the “hello world” of state-space search, and it makes the central point cleanly: the hard part is choosing the state representation, not the search. Once the state is a small integer and the validity predicate is a function, BFS is fifteen lines and the answer is provably optimal.

See also: BFS · Water Jug · Implicit Graphs

whoashish's cp notes

Directory