The riddle comes with a boat, a river and a farmer who has to move three awkward passengers. He has a wolf, a goat and a cabbage, and a vessel that holds him plus one of them. Most people solve it by fiddling. They ferry the goat, wince at what they left behind, and start again. There is a tidier way to see it, and it involves no boat at all.
The riddle and its constraints
The rules fit in a breath. The boat carries the farmer and at most one of the three. Left alone together, the wolf eats the goat, and the goat eats the cabbage. Nothing in the rules says the wolf and the cabbage conflict, so that pairing is allowed.
Because the constraints are so short, the puzzle invites trial and error. You try a move, notice the damage, and back up. That works, but it leans on memory and a little luck. The graph approach, as set out in a course page from the RISC institute in Linz, swaps both for a full inventory of what can happen.
Modelling states as nodes
Start with the word state. A state is just a way of putting the objects on the left or right shore. List what stands on the left bank and the right bank follows by subtraction. The set of all such left-shore collections is the powerset of the objects. The source keeps the farmer in that set on purpose, so that every move has to carry him.
Count the objects: wolf, goat, cabbage and farmer make four. Four objects give 2^4, or 16, possible left-shore collections before any filtering.
Not every arrangement survives. A shore is safe if the farmer is on it, or if it does not hold the goat together with the wolf or the cabbage. Unsafe states are filtered out, and what remains becomes the nodes. The rule applies to both banks. A dangerous pairing on the far side is as fatal as one on the starting side, and a model that checked only one bank would approve a meal.
Here is a check from standard counting, not from the source. With the farmer on the left, the right bank holds some subset of the other three, and 3 of the 8 subsets are unsafe: wolf and goat, goat and cabbage, or all three. That leaves 5 safe. The mirror case gives another 5. Of the 16 states, 10 are safe.
Edges, successors and the search for a path
An edge is one legal crossing. The successor function generates them: the farmer goes alone, or he takes one object along. Any resulting state that is unsafe is discarded. When the farmer stands on the right bank, the shore order is flipped in the result, so the same logic serves both directions. One function covers both banks.
A worked edge shows the idea. In the start state everything is on the left. If the farmer takes the wolf, the goat and cabbage are left together, so that move is dropped. If he takes the goat, the wolf and cabbage remain on the left and the farmer and goat are on the right. That state is safe, so an edge connects the two.
With nodes and edges in hand, the puzzle changes character. It becomes a question about whether a route exists from the start state, everything on the left, to the goal state, everything on the right. The source builds this in Maple using the GraphTheory library, where a directed graph is assembled from a set of edges and then examined for a path between the two states. It presents this model as the main idea, in place of trial and error.
Build the graph yourself
The source does not print the full solution, but you can reach it on paper in a few steps. These are the steps in outline.
- Write each state as the set of objects on the left bank, with F for the farmer.
- Cross out any state where the goat shares a bank with the wolf or the cabbage and the farmer is elsewhere.
- Draw a line between two surviving states when one crossing turns one into the other.
- Trace a path from the all-left state to the empty-left state.
The rest comes from standard knowledge, not the source. The shortest route takes 7 crossings. The farmer takes the goat over and returns alone. He takes the wolf over and brings the goat back. He takes the cabbage over, returns alone, and takes the goat over last. Swapping the wolf and the cabbage gives a second route of the same length. On the graph, that is a loop with two ways around it.
What the sources do not settle
The material is quiet on several points. It does not state the minimum number of crossings or give a full solution sequence, so the 7 above is outside knowledge. It does not explain how a shortest-path method such as breadth-first search finds its route. It does not say how the model stretches to more objects or different rules.
Two further documents were listed with the research, a Nagoya University lecture PDF and a Duke project on vertex covers and river crossings. Their text could not be read here, so nothing in this piece rests on them. The graph model above comes from the RISC page alone.
Sources
- https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHx1Y7Jo3TZ3dy1V4cyxMSQ70v_iAz90gmlDm9RdvBPQN2JyYE3R7mhz6Bc0AZVNSQg-wfP0v_fHJr0ur-3qpb9kn6bplgv2gThTRg9DA_FRV8AzEi-HIBX4uLrmo-TPudCrlV61QFn7wsgcrL_56L1spTZvsKFADLvtO-A
- https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGkqdzVrhX5y360Ka2CX7qWw2wjDO9UWrQ3e3vYvn8mN-psPHy1zCajX0LyOpaKF5xqqD3J9gd90CkX4vX_-kMePM629HOg4KX_Do0NuIcudiaisHe4IBTmLQF8NeG5XJXuUsQi-NgLltHueJBH38eXHabxpmt2YjS2ISz81yaieZs6u0tX_pxpkEEqWCXgGJzpkcwOOw==
- Farmer, Goat, Wolf, and Cabbage
Marcus Adeyemi-Holt is a house writer for Deeperpectives, where he examines how ordinary routines reveal larger patterns in work, memory, and place. He draws on years of reporting on municipal records and oral histories to trace the quiet forces that shape everyday life.
