Problem History
River crossing puzzles are a genre of logic puzzles often attributed to Alcuin of York (735-804) although versions of this puzzle have been found throughout Europe and Africa. In our sequences, we have retained two of the classics - wolf/goat/cabbage and adult/child puzzles - and added two more. Zombies and Humans is our spin on the dated cannibal-missionary puzzles and Monsters is our fun, novel puzzle that adds an arithmetic aspect.
Mathematical Theory
State Transition Graphs
At the heart of every river crossing puzzle is a collection of legal arrangements (or states) and transitions from one state to another. A natural way to represent a puzzle is as a graph, taking these states as vertices and transitions as edges. In the classic wolf-goat-cabbage puzzle, there are 16 possible states, divided into legal and illegal:
Legal
Illegal
We can then examine the 10 legal states and diagram the possible transitions:
The far left vertex is the starting state and the far right is the desired end state, so solving the puzzle now amounts to finding a path from the start to end following the edges. We can see there are two shortest paths (the upper path and the lower path), each requiring 7 crossings.
Vertex Covers
In a generalized version of the wolf-goat-cabbage problem, imagine that you have a large collection of objects where each pair can either be left together unsupervised or not. If there are n objects, then the puzzle can always be solved if there are n spaces in the boat, since the ferry person can keep an eye on all of them with a single trip. However, the puzzle may not be solvable if the boat only has room for a single item. There is a smallest boat that can be used to solve the puzzle, and the number of items this boat can ferry is called the Alcuin number. By the above discussion, the Alcuin number is always between 1 and n, inclusive.
For more details on the history and theory behind River Crossings puzzles, see here!