xvi. River Crossings

Problem. Missionaries and cannibals (and relatives: wolf–goat–cabbage, jealous husbands, bridge and torch). Move everyone across a river with a boat of capacity $b$, never letting a forbidden configuration occur on either bank (or in the boat).

All of these are shortest path in a small state graph: a state is who is on the start bank plus the boat side; edges are legal crossings. BFS gives the minimum number of crossings, and the state space is tiny ($(M+1)(C+1)\cdot 2$ here).

int riverCrossing(int M, int Cn, int boat) {       // missionaries and cannibals: min crossings, -1 if impossible
    auto safe = [&](int m, int c) { return (m == 0 || m >= c) && (M - m == 0 || M - m >= Cn - c); };
    // state: (missionaries on the start bank, cannibals on the start bank, boat side)
    vector<int> dist((M + 1) * (Cn + 1) * 2, -1);
    auto id = [&](int m, int c, int s) { return (m * (Cn + 1) + c) * 2 + s; };
    queue<array<int, 3>> q; q.push({M, Cn, 0}); dist[id(M, Cn, 0)] = 0;
    while (sz(q)) {
        auto [m, c, s] = q.front(); q.pop(); int d = dist[id(m, c, s)];
        if (m == 0 && c == 0 && s == 1) return d;
        for (int dm = 0; dm <= boat; dm++) for (int dc = 0; dm + dc <= boat; dc++) {
            if (dm + dc == 0 || (dm > 0 && dm < dc)) continue;   // nobody rows / missionaries outnumbered in the boat
            int nm = s == 0 ? m - dm : m + dm, nc = s == 0 ? c - dc : c + dc;
            if (nm < 0 || nc < 0 || nm > M || nc > Cn || !safe(nm, nc)) continue;
            int t = id(nm, nc, 1 - s); if (dist[t] < 0) dist[t] = d + 1, q.push({nm, nc, 1 - s});
        }
    }
    return -1;
}

Instance	Minimum crossings
3 missionaries, 3 cannibals, boat 2	11
4 and 4, boat 2	impossible
4 and 4, boat 3	9
5 and 5, boat 3	11
wolf, goat, cabbage	7 (Wolf Goat Cabbage)
bridge and torch, times 1, 2, 5, 10	17 minutes (Bridge and Torch)

Proof: BFS gives the minimum

Every crossing is one edge of the state graph, and the constraints are checked on both banks and in the boat after each crossing, so paths from the start state to the goal state are exactly the legal schedules. BFS explores states in order of distance, so the first time it reaches the goal it has found the minimum number of crossings; if the queue empties first, the goal is unreachable. The values in the table were produced by this code.