Return to Blog

Solving the Cabbage-Goat-Wolf problem using Python

By John Lekberg on January 01, 2020.


Here is the Cabbage-Goat-Wolf problem: there is a river (~~). On one side are a man, a cabbage, a goat, and a wolf:

man cabbage goat wolf ~~

The man can bring up to one thing across the river using his boat. For example, he can bring the wolf across:

cabbage goat ~~ man wolf

The goal is to move everything to the other side of the river:

~~ man cabbage goat wolf

This problem has two constraints:

The man has to be careful about the order in which he moves things across the river.

To solve this problem, I will represent the solution as a graph path from the start state to the goal state:

man cabbage goat wolf ~~   
cabbage wolf ~~ man goat    (man brings goat over)
man cabbage wolf ~~ goat    (man returns)
cabbage ~~ man wolf goat    (man brings wolf over)
...
~~ man cabbage goat wolf

There are many graph path-finding algorithms to choose from and their effectiveness depends on the structure of the graph. For this graph:

This graph is small, so I don't think algorithm choice matters. I will use Breadth First Search (BFS) because I'm comfortable implementing it. Here is a Python implementation of BFS:

def breadth_first_search(*, start, is_goal, get_neighbors):
    parent = dict()
    to_visit = [start]
    discovered = set([start])

    while to_visit:
        vertex = to_visit.pop(0)

        if is_goal(vertex):
            path = []
            while vertex is not None:
                path.insert(0, vertex)
                vertex = parent.get(vertex)
            return path

        for neighbor in get_neighbors(vertex):
            if neighbor not in discovered:
                discovered.add(neighbor)
                parent[neighbor] = vertex
                to_visit.append(neighbor)

Next, I need to decide how to model the state:

Because the state needs to be hashable, I will use an Enum to model the locations and a namedtuple to keep track of everything:

State = namedtuple("State", ["man", "cabbage", "goat", "wolf"])
Location = Enum("Location", ["A", "B"])

To use breadth_first_search I need to define:

Here is the starting state:

start_state = State(
    man=Location.A,
    cabbage=Location.A,
    goat=Location.A,
    wolf=Location.A,
)

Here is the goal state:

goal_state = State(
    man=Location.B,
    cabbage=Location.B,
    goat=Location.B,
    wolf=Location.B,
)

The predicate to check for the goal is goal_state.__eq__.

To create a routine that generates neighboring states, I first create an auxiliary routine to validate a potential state. This validation takes into account the constraints given earlier (goat-eating-cabbage and wolf-eating-goat). Here is the validation routine:

def is_valid(state):
    goat_eats_cabbage = (
        state.goat == state.cabbage
        and state.man != state.goat
    )
    wolf_eats_goat = (
        state.wolf == state.goat and state.man != state.wolf
    )
    invalid = goat_eats_cabbage or wolf_eats_goat
    return not invalid

To generate the neighboring states, I try all potential moves and filter out the invalid ones:

def next_states(state):
    if state.man == Location.A:
        other_side = Location.B
    else:
        other_side = Location.A

    move = partial(state._replace, man=other_side)

    candidates = [move()]

    for thing in ["cabbage", "goat", "wolf"]:
        if getattr(state, thing) == state.man:
            candidates.append(move(**{thing: other_side}))

    yield from filter(is_valid, candidates)

Now, we call breadth_first_search using our model:

breadth_first_search(
    start = start_state,
    is_goal = goal_state.__eq__,
    get_neighbors = next_states,
)

Calling this outputs

[State(man=<Location.A: 1>, cabbage=<Location.A: 1>, goat=<Location.A: 1>, wolf=<Location.A: 1>),
 State(man=<Location.B: 2>, cabbage=<Location.A: 1>, goat=<Location.B: 2>, wolf=<Location.A: 1>),
 State(man=<Location.A: 1>, cabbage=<Location.A: 1>, goat=<Location.B: 2>, wolf=<Location.A: 1>),
 State(man=<Location.B: 2>, cabbage=<Location.B: 2>, goat=<Location.B: 2>, wolf=<Location.A: 1>),
 State(man=<Location.A: 1>, cabbage=<Location.B: 2>, goat=<Location.A: 1>, wolf=<Location.A: 1>),
 State(man=<Location.B: 2>, cabbage=<Location.B: 2>, goat=<Location.A: 1>, wolf=<Location.B: 2>),
 State(man=<Location.A: 1>, cabbage=<Location.B: 2>, goat=<Location.A: 1>, wolf=<Location.B: 2>),
 State(man=<Location.B: 2>, cabbage=<Location.B: 2>, goat=<Location.B: 2>, wolf=<Location.B: 2>)]

This output is hard for me to read, so I created a routine to nicely report the solution:

def describe_solution(path):
    for old, new in zip(path, path[1:]):
        boat = [
            thing
            for thing in ["man", "cabbage", "goat", "wolf"]
            if getattr(old, thing) != getattr(new, thing)
        ]
        print(old.man, "to", new.man, boat)

Here is its explanation of the solution:

Location.A to Location.B ['man', 'goat']
Location.B to Location.A ['man']
Location.A to Location.B ['man', 'cabbage']
Location.B to Location.A ['man', 'goat']
Location.A to Location.B ['man', 'wolf']
Location.B to Location.A ['man']
Location.A to Location.B ['man', 'goat']

And that's how you solve the Cabbage-Goat-Wolf problem using Python.

If you want to run this code, include these import statements:

from enum import Enum
from collections import namedtuple
from functools import partial

See you next week!