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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7
8

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

  1. Represent a state as four booleans: farmer, sheep, cabbage, wolf (false = left bank, true = right bank).
  2. 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.
  3. 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.
  4. Use DFS with a visited set to avoid cycles. Record the move sequence when a move transports an object (“wolf”, “sheep”, “cabbage”, or “boatman”).
  5. When reaching the goal state (all true), return the recorded sequence.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

// 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;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

// 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;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

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).