Solving the Classic River Crossing Puzzle: Fox, Chicken, Grain

The "Smart Kit River Crossing Game" is a digital version of the classic wolf-goat-cabbage (or fox-chicken-grain) logic puzzle—a constraint satisfaction problem dating to at least 9th century Europe. The challenge: transport three items across a river with a boat that holds only one item plus the operator, without leaving conflicting pairs alone.

The Solution Sequence

Initial state: Fox, Chicken, Grain | Boat | (empty far bank)

1. Take Chicken across. (Fox and Grain safe together — fox doesn't eat grain)
2. Return alone.
3. Take Fox across.
4. Bring Chicken BACK. (Critical step — cannot leave Fox and Chicken together)
5. Take Grain across. (Fox and Grain safe together)
6. Return alone.
7. Take Chicken across.

Final state: (empty near bank) | Boat | Fox, Chicken, Grain

Why This Works: Constraint Analysis

Forbidden pairs (unattended): Fox+Chicken (predation), Chicken+Grain (consumption).
Safe pairs: Fox+Grain (no interaction).
Key insight: The Chicken conflicts with BOTH others—it's the "central node" in the conflict graph. Therefore, the Chicken must be the shuttle item: moved first, brought back, moved last. The Fox and Grain never interact directly.

Generalizable Problem-Solving Approach

1. Model constraints explicitly — list all forbidden states.
2. Identify the most constrained element — here, the Chicken.
3. Work backward from goal — final move must bring the last item.
4. Use state-space search — BFS/DFS finds optimal solution (7 moves minimum).
5. Verify no forbidden states occur — including during boat transit.

Variations and Extensions

Missionaries and cannibals (3 each, boat holds 2). Jealous husbands (3 couples, boat holds 2, no wife with other husband unless her husband present). Modern versions add time limits, multiple boats, or dynamic constraints. The core logic remains: constraint satisfaction through state-space search.