Wolf, Goat, and Cabbage Minimal River Crossing

Scenario

A farmer must transport a wolf, a goat, and a large cabbage from the left bank to the right bank of a river using a small rowboat. The boat can hold at most the farmer and one item. If left unattended on either bank without the farmer:

• The wolf will eat the goat.
• The goat will eat the cabbage.
• The wolf does not eat the cabbage.

Your Task

1. Model the problem as state-space graph search over 4-tuples $(F, W, G, C) \in \{0, 1\}^4$.
2. Identify the illegal states on either river bank.
3. Prove that the minimal number of river crossings required is exactly 7 and list the unique optimal sequence of trips.

Constraints

• Boat capacity = Farmer + 1 passenger/item.
• Farmer must row the boat on every crossing.

Examples Trip 1 must take the Goat across, because leaving Wolf with Goat or Goat with Cabbage results in immediate loss.