--- title: "Farmer, goat, wolf, cabbage puzzle" subject: "Artificial Intelligence" chapter: 2 key: "semester_6/artificial_intelligence:farmer-goat-wolf-cabbage" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/farmer-goat-wolf-cabbage site: BCT Engineering --- # Farmer, goat, wolf, cabbage puzzle Artificial Intelligence · Chapter 2: Problem Solving - Asked in: 2073 Magh, 8 marks - Video: [Artificial Intelligence - Farmer Crosses River Puzzle](https://www.youtube.com/watch?v=qboEZ_WrNZA) — TutorialsPoint - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/farmer-goat-wolf-cabbage - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-2 ## Question 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. ## 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. ## Answer #### 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. ```text 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.) ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is a state represented in the formulation? A. The bank (west/east) of each of farmer, wolf, goat, cabbage B. Only the boat's position C. The number of animals D. The crossing count Answer: A. The state tuple (F, W, G, C) records each item's bank, 0 west and 1 east. (Key point: State representation) 2. When is a state illegal? A. Wolf and cabbage are together without the farmer B. Farmer is absent from a bank where wolf and goat, or goat and cabbage, are together C. Farmer is on the east bank D. The boat is empty Answer: B. Wolf eats goat and goat eats cabbage; wolf and cabbage are safe. (Key point: Illegal states) 3. Why is taking the goat across the only safe first move? A. The goat is lightest B. The goat rows the boat C. Any other first move leaves goat with wolf or cabbage D. Wolf cannot cross Answer: C. Taking the wolf or cabbage, or going alone, leaves an unsafe pair. (Key point: First move) 4. Why is the goat brought back in step 4? A. To save time B. To eat the cabbage C. To reset the state D. To avoid leaving the goat with the wolf when the farmer returns Answer: D. Leaving the goat with the wolf would let it be eaten; bringing it back lets the farmer swap in the cabbage safely. (Key point: Bringing the goat back) 5. How many crossings does the shortest solution need? A. 7 B. 5 C. 9 D. 11 Answer: A. BFS shows the shortest solution has 7 crossings. (Key point: Solution length) ## Related in other subjects - [Chainage of R across a river](https://www.bctengineer.com/question.md?key=semester_3%2Fsurveying_i%3Aobstacle-river-chainage-of-r) — Surveying I, chapter 3 - [Reciprocal levelling across river, 250 m](https://www.bctengineer.com/question.md?key=semester_3%2Fsurveying_i%3Areciprocal-leveling-river-250m-eyepiece-height) — Surveying I, chapter 5 - [Skid numerical: A from North, B from West](https://www.bctengineer.com/question.md?key=semester_7%2Ftransportation_engineering_ii%3Askid-collision-north-west-47-56) — Transportation Engineering II, chapter 1, asked 3× - [Skid numerical: A from West, B from South (45, 50)](https://www.bctengineer.com/question.md?key=semester_7%2Ftransportation_engineering_ii%3Askid-collision-west-south-45-50) — Transportation Engineering II, chapter 1, asked 2×