# Hard River Crossing

Source: https://www.techinterview.org/post/523919913/hard-river-crossing/
Updated: 2026-04-16 · techinterview.org

a disfunctional family has to cross the river. on one side of the river are a mom and 2 daughters, dad and 2 sons, the maid and the dog. there is a boat only big enough to hold 2 people (counting the dog as 1 person). only the adults are capable of operating the boat. everyone has to get to the other side, without anything bad happening.

difficulties: if the dog is left with anyone and the maid isn’t there to control him, he’ll bite. the dad can’t be left with any of the daughters when the mom isn’t there. likewise, the mom can’t be trusted alone with either of the sons when the dad isn’t there.

remember! only an adult can operate the boat, AND the boat can’t drive itself.

### Solution

we start with a mother (m), two daughters (d1, d2), a father (f), two sons (s1, s2), a housemaid (h), and a dog (c - canine) on the west (W) shore, and they all want to get to the east (E) shore.


```
W = {m, d1, d2, f, s1, s2, h, c} // everyone on the west shoreE = {} // no one on the east shore
```

let’s move everyone, over…

housemaid and canine go east, and the housemaid comes back:


```
W = {m, d1, d2, f, s1, s2, h}E = {c}
```

housemaid and s1 go east, h and c come back:


```
W = {m, d1, d2, f, s2, h, c}E = {s1}
```

father and s2 go east, father comes back:


```
W = {m, d1, d2, f, h, c}E = {s1, s2}
```

mother and father go east, mother comes back:


```
W = {m, d1, d2, h, c}E = {f, s1, s2}
```

h and c go east, father comes back:


```
W = {m, d1, d2, f}E = {s1, s2, h, c}
```

father and mother go east, mother comes back:


```
W = {m, d1, d2}E = {f, s1, s2, h, c}
```

mother and d1 go east, housemaid and c come back:


```
W = {d2, h, c}E = {m, d1, f, s1, s2}
```

h and d2 go east, h comes back


```
W = {h, c}E = {m, d1, d2, f, s1, s2}
```

h and c go east


```
W = {}E = {m, d1, d2, f, s1, s2, h, c}
```

done!

## 2026 Update: Constraint Satisfaction and Search Problems

River crossing puzzles — where you must transport items across a river subject to constraints (fox, chicken, grain can't be left together) — are a classic example of constraint satisfaction problems (CSP) and state-space search. They remain asked at Google, Microsoft, and in CS graduate program interviews.

**The BFS solution generalizes to any such puzzle:**


```
from collections import deque

def solve_river_crossing():
    """
    Classic: farmer transports fox, chicken, grain.
    State: (farmer_side, fox_side, chicken_side, grain_side) where 0=left, 1=right.
    """
    def is_valid(state):
        farmer, fox, chicken, grain = state
        # Fox and chicken alone (without farmer) is invalid
        if fox == chicken and farmer != fox:
            return False
        # Chicken and grain alone (without farmer) is invalid
        if chicken == grain and farmer != chicken:
            return False
        return True

    items = ["fox", "chicken", "grain"]
    start = (0, 0, 0, 0)  # All on left bank
    goal  = (1, 1, 1, 1)  # All on right bank
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        state, path = queue.popleft()
        if state == goal:
            return path

        farmer = state[0]
        # Options: farmer crosses alone, or with one item
        for move in [None, 0, 1, 2]:  # None = alone, 0-2 = take item index
            new_state = list(state)
            new_state[0] = 1 - farmer  # Farmer always crosses
            if move is not None:
                if state[move + 1] != farmer:
                    continue  # Item not on farmer's side
                new_state[move + 1] = 1 - farmer
            new_state = tuple(new_state)
            if new_state not in visited and is_valid(new_state):
                visited.add(new_state)
                queue.append((new_state, path + [new_state]))

    return None  # No solution

solution = solve_river_crossing()
for step in solution:
    print(step)
```


**Modern relevance:** This BFS-over-states approach is exactly how robot motion planning, packet routing, and dependency resolution work. The constraint satisfaction formulation appears in compiler register allocation, exam scheduling, and SAT solvers.