Hard River Crossing

By /
⏱ 3 min read

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 shore
E = {} // 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.

💡Strategies for Solving This Problem

Optimization and State Space Search

Got this at Palantir in 2023. Classic river crossing puzzle that tests graph search, state representation, and constraint satisfaction. Good for showing systematic problem-solving.

The Problem

A farmer needs to cross a river with a fox, chicken, and bag of grain. The boat can only hold the farmer and one other item. Constraints:

  • If left alone: fox eats chicken
  • If left alone: chicken eats grain
  • Farmer must be in boat to row

Find sequence of moves to get everything across safely.

State Representation

Each state = [farmer, fox, chicken, grain] where each is 0 (left) or 1 (right)

Initial: [0, 0, 0, 0] (all on left)
Goal: [1, 1, 1, 1] (all on right)

Approach 1: Trial and Error

Try random moves, backtrack when stuck. Inefficient and may not find optimal solution.

Approach 2: BFS (Breadth-First Search) ✓

Explore all possible moves systematically. Guarantees shortest solution.

Algorithm:

  1. Start with initial state in queue
  2. For each state, generate all valid moves
  3. Check if move violates constraints (fox eats chicken, etc.)
  4. Add valid new states to queue
  5. Track visited states to avoid cycles
  6. Stop when reach goal state

Valid Moves

From each state, farmer can:

  • Cross alone
  • Cross with fox
  • Cross with chicken
  • Cross with grain

But only if farmer and item are on same side.

Constraint Checking

After each move, check if state is safe:

  • If fox and chicken on same side without farmer → invalid
  • If chicken and grain on same side without farmer → invalid

Approach 3: DFS with Backtracking

Try each path deeply before backtracking. Can find solution but not guaranteed to be shortest.

The Solution Sequence

Optimal solution (7 moves):

  1. Take chicken across →
  2. Return alone ←
  3. Take fox across →
  4. Return with chicken ←
  5. Take grain across →
  6. Return alone ←
  7. Take chicken across →

Key insight: Must bring chicken back to prevent it eating grain while bringing fox over.

At Palantir

Interviewer asked me to code the solution. Started with state representation, then implemented BFS with constraint checking. He asked "Why BFS over DFS?" I explained BFS finds shortest path. Then he asked about space complexity and how to optimize.

Scroll to Top