Graphing the Ferryman Problem

Hello again, blog. It’s been a while. I had a lot of topics that I wanted to write about the past year, but in the end I never managed to finish and publish anything. I think I’m generally ok with that though.

In the german lesson I had this week, we came across the “Ferryman problem” as part of an exercise. I found the following English explanation on the Mathswork website.

A man needs to cross a river with a wolf, a goat and a cabbage. His boat is only large enough to carry himself and one of his three possessions, so he must transport these items one at a time. However, if he leaves the wolf and the goat together unattended, then the wolf will eat the goat; similarly, if he leaves the goat and the cabbage together unattended, then the goat will eat the cabbage. How can the man get across safely with his three items?

During the lesson I then spent way too much time trying to draw a graph of all the different states. So instead I made a script using python and the graphviz library to draw this graph for me.

The different states are represented by a tuple of three. The leftmost value of the tuple is the set of who are on the initial (left) bank of the river. The second or middle value is the set for who are on the boat. The rightmost value is the destination bank of the river. Each character of the problem is identified by the letters. W is the wolf, S is the (Schafe), K is the cabbage (Kohl) and F is the ferryman.

Some example states:

('FKSW', '', '') # Our initial starting state with everyone the first riverbank.
('KW', 'FS', '') # The cabbage and the wolf are on the first bank. The ferryman and the sheep are on the boat in the river.

Anyhow, too much writing for something that is overkill. I’m pretty sure there are much simpler solutions to this. You can find the graph below.