[Math] Bringing the fox, the goose and the cereal across the river unharmed

Question

Solve puzzle algebraically? I can't come up elegant and algebraical solution.

There are man, fox, goose, and cereals. If the man is not beside the fox, the fox will eat the goose. If the man is not beside the goose, the goose will eat the cereal. The man wants to bring them all to a land across river. Unfortunately there is only a small ship. The ship can contain only man and fox or man and goose or man and cereal.

How to solve this puzzle with algebra? Or anything mathematical concept except brute forcing approach.

Any idea? Thanks.

Answer 1

I would approach this as a problem in graph theory. Let the configurations of the fox, goose, cereal, and boat be the vertices of a graph. Each vertex records a position, and we are trying to find a path through the graph from the starting position (marked in green) to the end position (marked in blue):

A node labeled bg_cf means that the boat (and the man) and goose are on the left bank of the stream, the cereal and fox are on the right bank. The initial position, in green, is bcfg_ with all four entities on the left bank; the goal position, in blue, is _bcfg with all four entities on the right bank. Red positions are forbidden. Then we need to find a path through the graph from the green to the blue, avoiding all the red nodes.

Since the red nodes don't help, we may as well just remove them:

Represented this way, we can solve the puzzle by eyeball, or we can use a standard graph-searching algorithm to find a solution. For example, if we want the shortest possible solution, we can use the usual breadth-first search algorithm. But once the graph is drawn, the solution is completely obvious, and it's just as clear that there are two equally-short minimal solutions, and an infinite family of longer ones obtained by going around the loop one or more times.