The Puzzle: A farmer needs to cross a river with a Wolf, a Goat, and a Cabbage.
- His boat can only carry him and one other item.
- If left alone: Wolf eats Goat, and Goat eats Cabbage. How can he get all three across safely?
1. The Strategy
The key is realizing that you can bring things back across the river to prevent a disaster.
The Steps:
- Take the Goat across. (Safe: Wolf and Cabbage stay together).
- Return alone.
- Take the Wolf across.
- Take the Goat back. (IMPORTANT! Don’t leave Wolf and Goat together).
- Take the Cabbage across. (Now Wolf and Cabbage are on the other side).
- Return alone.
- Take the Goat across.
2. Result
All three are across. No one was eaten.
Interview-Focused Questions
Q: What is the ‘Aha!’ moment in this puzzle?
A: Most people get stuck at Step 4. They think they must always bring something new across. Realizing you can “undo” a previous step by bringing the Goat back is the key to solving constraint-based problems.
Q: What if the boat was larger?
A: If the boat can hold two items, the puzzle becomes trivial. This puzzle is specifically designed to test how you handle a bottleneck in a system.
Key Takeaway
This is a lesson in State Space Search. In software engineering, this is similar to handling transactional dependencies.
Premium Content
Unlock Wolf, Goat & Cabbage and all premium lessons with a subscription.
From ₹199.99/year — See plans