Wolf, Sheep, Cabbage - River Crossing Puzzle
Updated: Oct 11, 2025
Problem
You are given three items — a wolf, a sheep and a cabbage — that are all initially on the left bank of a river along with a boat and a farmer. The farmer can use the boat to carry at most one item at a time across the river. If left alone without the farmer on a bank, the wolf will eat the sheep and the sheep will eat the cabbage. The goal is to transport all three items (wolf, sheep, cabbage) and the farmer to the right bank without any item being eaten.
Write a function that returns any valid sequence of moves (as a list of actions) that safely transports all items to the right bank. You may represent each move as the name of the object transported ("wolf", "sheep", "cabbage") or the action of crossing empty-handed ("boatman"). If no valid sequence exists, return an empty list.
Examples
Example 1
Input:
farmer = false # false = left bank, true = right bank
sheep = false
cabbage = false
wolf = false
Output: ["sheep", "boatman", "wolf", "sheep", "cabbage", "boatman"]
Explanation: One valid sequence is: farmer takes sheep across, returns alone, takes wolf across, brings sheep back, takes cabbage across, returns alone and finally takes sheep across.
Example 2
Input:
farmer = false # false = left bank, true = right bank
sheep = false
cabbage = false
wolf = false
Output: []
Explanation: If an extra constraint forbids the farmer from returning alone, there may be no valid solution; return an empty list.
Solution
Method 1 - Backtracking
Intuition
The state is small (four boolean flags for farmer, sheep, cabbage, wolf). We can explore the state-space of moves (farmer crosses alone or with one item) and only continue along branches that remain safe (no predator-prey pair left unattended). Because the branching factor is small and there are at most 2^4 = 16 possible states, DFS/backtracking with a visited set will quickly find a valid sequence.
Approach
- Represent a state as four booleans: farmer, sheep, cabbage, wolf (false = left bank, true = right bank).
- From a state, generate possible moves: the farmer crosses alone, or the farmer crosses with one item that's on the same side as the farmer.
- After each move, check safety: on each bank where the farmer is absent, ensure sheep and cabbage are not together and sheep and wolf are not together.
- Use DFS with a visited set to avoid cycles. Record the move sequence when a move transports an object ("wolf", "sheep", "cabbage", or "boatman").
- When reaching the goal state (all true), return the recorded sequence.
Code
C++
// C++ (google style) Solution class
#include <array>
#include <string>
#include <vector>
#include <unordered_set>
class Solution {
public:
using State = std::array<bool, 4>; // farmer, sheep, cabbage, wolf
std::vector<std::string> solve() {
State start = {false, false, false, false};
State goal = {true, true, true, true};
std::vector<std::string> path;
std::unordered_set<int> visited;
dfs(start, goal, path, visited);
return path;
}
private:
static int encode(const State &s) {
int v = 0;
for (int i = 0; i < 4; ++i) v |= (s[i] << i);
return v;
}
static bool safe(const State &s) {
bool farmer = s[0];
bool sheep = s[1];
bool cabbage = s[2];
bool wolf = s[3];
// If farmer absent on a bank, sheep+cabbage or sheep+wolf cannot be together
if (sheep == cabbage && sheep != farmer) return false;
if (sheep == wolf && sheep != farmer) return false;
return true;
}
bool dfs(State cur, const State &goal, std::vector<std::string> &path,
std::unordered_set<int> &visited) {
if (cur == goal) return true;
int key = encode(cur);
if (visited.count(key)) return false;
visited.insert(key);
bool farmer = cur[0];
// generate moves: farmer crosses alone
State next = cur;
next[0] = !next[0];
if (safe(next)) {
path.push_back("boatman");
if (dfs(next, goal, path, visited)) return true;
path.pop_back();
}
// farmer crosses with sheep, cabbage, or wolf if they are on same side
for (int i = 1; i <= 3; ++i) {
if (cur[i] == farmer) {
State n2 = cur;
n2[0] = !n2[0];
n2[i] = !n2[i];
if (safe(n2)) {
const char *names[] = {"farmer", "sheep", "cabbage", "wolf"};
path.push_back(names[i]);
if (dfs(n2, goal, path, visited)) return true;
path.pop_back();
}
}
}
return false;
}
};
Java
// Java Solution class
import java.util.*;
public class Solution {
private static class State {
boolean farmer, sheep, cabbage, wolf;
State(boolean f, boolean s, boolean c, boolean w) {
farmer = f; sheep = s; cabbage = c; wolf = w;
}
@Override public boolean equals(Object o) {
if (!(o instanceof State)) return false;
State s = (State) o;
return farmer == s.farmer && sheep == s.sheep && cabbage == s.cabbage && wolf == s.wolf;
}
@Override public int hashCode() {
int v = 0;
v |= (farmer ? 1 : 0);
v |= (sheep ? 2 : 0);
v |= (cabbage ? 4 : 0);
v |= (wolf ? 8 : 0);
return v;
}
}
public List<String> solve() {
State start = new State(false, false, false, false);
State goal = new State(true, true, true, true);
List<String> path = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
dfs(start, goal, path, visited);
return path;
}
private boolean safe(State s) {
if (s.sheep == s.cabbage && s.sheep != s.farmer) return false;
if (s.sheep == s.wolf && s.sheep != s.farmer) return false;
return true;
}
private int encode(State s) {
int v = 0;
if (s.farmer) v |= 1;
if (s.sheep) v |= 2;
if (s.cabbage) v |= 4;
if (s.wolf) v |= 8;
return v;
}
private boolean dfs(State cur, State goal, List<String> path, Set<Integer> visited) {
if (cur.equals(goal)) return true;
int key = encode(cur);
if (visited.contains(key)) return false;
visited.add(key);
// farmer crosses alone
State next = new State(!cur.farmer, cur.sheep, cur.cabbage, cur.wolf);
if (safe(next)) {
path.add("boatman");
if (dfs(next, goal, path, visited)) return true;
path.remove(path.size() - 1);
}
// farmer crosses with each item that's on same side
if (cur.sheep == cur.farmer) {
State n = new State(!cur.farmer, !cur.sheep, cur.cabbage, cur.wolf);
if (safe(n)) {
path.add("sheep");
if (dfs(n, goal, path, visited)) return true;
path.remove(path.size() - 1);
}
}
if (cur.cabbage == cur.farmer) {
State n = new State(!cur.farmer, cur.sheep, !cur.cabbage, cur.wolf);
if (safe(n)) {
path.add("cabbage");
if (dfs(n, goal, path, visited)) return true;
path.remove(path.size() - 1);
}
}
if (cur.wolf == cur.farmer) {
State n = new State(!cur.farmer, cur.sheep, cur.cabbage, !cur.wolf);
if (safe(n)) {
path.add("wolf");
if (dfs(n, goal, path, visited)) return true;
path.remove(path.size() - 1);
}
}
return false;
}
}
Python
from typing import List
class Solution:
# state: [farmer, sheep, cabbage, wolf]
def solve(self) -> List[str]:
start = (False, False, False, False)
goal = (True, True, True, True)
path: List[str] = []
visited = set()
self.dfs(start, goal, path, visited)
return path
def safe(self, s: tuple[bool, bool, bool, bool]) -> bool:
farmer, sheep, cabbage, wolf = s
if sheep == cabbage and sheep != farmer:
return False
if sheep == wolf and sheep != farmer:
return False
return True
def encode(self, s: tuple[bool, bool, bool, bool]) -> int:
v = 0
for i, b in enumerate(s):
if b:
v |= (1 << i)
return v
def dfs(self, cur, goal, path: List[str], visited: set) -> bool:
if cur == goal:
return True
key = self.encode(cur)
if key in visited:
return False
visited.add(key)
farmer = cur[0]
# farmer crosses alone
nxt = (not cur[0], cur[1], cur[2], cur[3])
if self.safe(nxt):
path.append("boatman")
if self.dfs(nxt, goal, path, visited):
return True
path.pop()
# farmer crosses with each item on same side
names = [None, "sheep", "cabbage", "wolf"]
for i in range(1, 4):
if cur[i] == farmer:
lst = list(cur)
lst[0] = not lst[0]
lst[i] = not lst[i]
n2 = tuple(lst)
if self.safe(n2):
path.append(names[i])
if self.dfs(n2, goal, path, visited):
return True
path.pop()
return False
Complexity
- ⏰ Time complexity:
O(1)– The state space is constant (at most 16 states), so the algorithm runs in constant time independent of input size. - 🧺 Space complexity:
O(1)– Visited set and recursion depth are bounded by a constant (<= 16 states).