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