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 goat will eat the cabbage if the man isn't there to stop it:
```
cabbage goat ~~ man wolf
```
The wolf will eat the goat if the man isn't there to stop it:
```
wolf goat ~~ man cabbage
```

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:

There are 4 things (man, cabbage, goat, wolf) and each thing has 2 states (either side of the river), so there are at most 16 vertices.
A complete graph with 16 vertices has 120 edges.

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:

I need to keep track of the location of the man, the cabbage, the goat, and the wolf.
There are two locations (each side of the river).
breadth_first_search uses a set to track discovered vertices, so the state has to be hashable.

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:

a starting state to begin the search from,
a predicate to check if we are at a goal state, and
a routine to generate all neighboring states for a given state.

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!

(If you spot any errors or typos on this post, contact me via my contact page.)