- 2073 Magh · 8 marks
Farmer, goat, wolf, cabbage puzzle
Short answer
Formulate with state as positions of farmer, wolf, goat, cabbage; operators are crossings; illegal if wolf/goat or goat/cabbage left without farmer. BFS gives 7 crossings: goat over, back alone, wolf over, goat back, cabbage over, back alone, goat over.
A farmer has a goat, a wolf and a cabbage on the west side of a river. He wants to get all of his animals and his cabbage across the river onto the east side. The farmer has a row boat but he only has enough room for himself and one other thing. The wolf will eat the goat if they are left together alone. The goat will eat the cabbage if they are left together alone. How can the farmer get everything on the east side? i) Formulate this puzzle as search. ii) Solve this problem using search (any method). Draw the search tree and show the final solution.
i) Formulation as a search problem
Use letters F = Farmer, W = Wolf, G = Goat, C = Cabbage.
- State: the bank (West/East) of each of F, W, G, C, written as WEST | EAST, e.g.
WC | FG. The state tuple is (F, W, G, C), each 0 (west) or 1 (east). - Initial state:
FWGC | -= (0,0,0,0). - Goal state:
- | FWGC= (1,1,1,1). - Operators: the farmer rows the boat across to the other bank carrying (a) nothing, (b) the wolf, (c) the goat, or (d) the cabbage. The passenger must be on the farmer's side.
- Constraints (illegal states): the farmer is absent from a bank where {W, G} are together or {G, C} are together.
- Path cost: 1 per crossing.
Checking all combinations by BFS (verified with a Python program) gives only 10 legal reachable states, and the shortest solution has 7 crossings.
ii) Solution using breadth-first search (search tree)
Unsafe children are pruned (marked X); repeated states are not expanded again.
FWGC | - START
|-- take wolf -> G,C left alone X (goat eats cabbage)
|-- take cabbage -> W,G left alone X (wolf eats goat)
|-- go alone -> W,G,C left X
|-- take goat
v
WC | FG
|-- take goat back -> start (repeat)
|-- go alone
v
FWC | G
|-- take wolf |-- take cabbage
v v
C | FWG W | FGC
|-- bring goat back |-- bring goat back
v v
FGC | W FGW | C
|-- take cabbage |-- take wolf
v v
G | FWC <-------------> G | FWC (same state)
|-- go alone
v
FG | WC
|-- take goat
v
- | FWGC GOAL
(From C | FWG the farmer cannot return alone, because the wolf would be left with the goat; the same holds for W | FGC.)
Final solution (7 steps)
| Step | Move | West bank | East bank |
|---|---|---|---|
| 0 | start | F W G C | - |
| 1 | take goat across | W C | F G |
| 2 | return alone | F W C | G |
| 3 | take wolf across | C | F W G |
| 4 | bring goat back | F G C | W |
| 5 | take cabbage across | G | F W C |
| 6 | return alone | F G | W C |
| 7 | take goat across | - | F W G C |
Answer: goat over, back alone, wolf over, goat back, cabbage over, back alone, goat over. (Exchanging the wolf and the cabbage gives the other equally short solution.)
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Chainage of R across a river · Surveying I, chapter 3
- Reciprocal levelling across river, 250 m · Surveying I, chapter 5
- Skid numerical: A from North, B from West · Transportation Engineering II, chapter 1 · asked 3×
- Skid numerical: A from West, B from South (45, 50) · Transportation Engineering II, chapter 1 · asked 2×