The Farmer, Wolf, Goat, and Cabbage riddle is an ancient puzzle found in medieval manuscripts dating back to the 8th century (attributed to Alcuin of York, advisor to Charlemagne).

In modern computer science, this is the classic introduction to State-Space Search in Artificial Intelligence:

• A farmer needs to ferry a wolf, a goat, and a cabbage across a river from the left bank to the right bank.
• The boat is small: it can carry only the farmer and at most one passenger (wolf, goat, or cabbage).
• Dangerous Combinations:
  • If the farmer leaves the wolf alone with the goat, the wolf will eat the goat!
  • If the farmer leaves the goat alone with the cabbage, the goat will eat the cabbage!
• The wolf does not eat the cabbage. When the farmer is present on the bank, all animals and items behave safely.

Instead of manual trial-and-error, we represent the world as a logical state: $$\text{state}(\text{Farmer}, \text{Wolf}, \text{Goat}, \text{Cabbage})$$ and let Prolog's depth-first search discover the optimal crossing sequence automatically!

Move the mouse over a dotted box for more information.

• State-Space Graph: The problem has $2^4 = 16$ possible configurations. Six of these are dangerous, leaving 10 valid states connected by legal river crossings.
• Loop Prevention: As Prolog searches the graph, it keeps a history of visited states to prevent rowing back and forth in an infinite loop.
• Minimum Crossings: The puzzle requires a minimum of 7 river crossings. The crucial insight is that on trip #4, the farmer must bring the goat back to the left bank!