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.

This puzzle is apparently best known with a bag of beans instead of cereal: Wikipedia. — TMM, Mar 12 '14 at 01:27
The version I'm most familiar with (also apparently the earliest one, according to Wikipeda) is "The wolf, the goat and the cabbage". — ShreevatsaR, Mar 12 '14 at 01:30
@ShreevatsaR That's also what came to my mind first, but since the page is titled "...bag of beans..." I thought I'd mention that. — TMM, Mar 12 '14 at 01:36
By the way, apparently the Spanish version of the wikipedia-page does have cabbage instead of bag of beans in the title... — TMM, Mar 12 '14 at 01:37
In mathematics, we like to deal with generalities. Therefore, we should refer to the carnivore, the herbivore and the vegetable. :-) — David Richerby, Mar 12 '14 at 08:24
+David Richerby If you really want to make it generic, you should then not consider even herbivores, but elements with relative constraints. That suspiciously sounds like "turning the problem into a graph", which happens to yield a solution. However, it makes the problem pretty arid, which was the original problem that caused the presence of a cute fox in the first place ;) — Kheldar, Mar 12 '14 at 13:32

MJD · Accepted Answer · 2014-03-12T01:59:43.540

24

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

graph of all positions

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:

graph of only legal positions

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.

edited Mar 12 '14 at 01:59

answered Mar 12 '14 at 01:31

MJD

65,394
39
298
580

Very nice! Could you post the code you used to generate these graphs? (Unless you wrote them by hand, which is impressive as well.) – ShreevatsaR Mar 12 '14 at 01:46
2

@ShreevatsaR I wrote a computer program to generate descriptions of the graphs in the "dot" language, then the dot program from GraphViz to render the graphs. The code is at https://github.com/mjdominus/perl-misc/tree/master/fox-goose-cereal – MJD Mar 12 '14 at 01:53
1

Very helpful diagrams. – qwr Mar 12 '14 at 02:55
Code has moved to https://github.com/mjdominus/perl-misc/tree/master/search/fox-goose-cereal – MJD Oct 22 '14 at 19:36
How could you even expand the red states when they are already invalid? Is the next state from the red state a random state you made up? That's what I don't understand. – TwilightSparkleTheGeek Feb 12 '15 at 17:34
1

A move in the game means: you (optionally) load one item from the shore into the boat, cross the river, and unload the item (if there was one) on the opposite shore. You can do this whether or not the fox eats the goose. So imagine a version of the game where the fox does not eat the goose and the goose does not eat the cereal; you could move stuff back and forth all day. That's the first graph. But then the real puzzle adds the restriction that you may not leave the fox alone with the goose, or the goose with the cereal, so some positions are forbidden. Those are red. – MJD Feb 12 '15 at 18:21
1

So for example consider the node in the middle labeled c_bfg; the boat, fox, and goose are on the right and the cereal on the left. We could carry either the fox or the goose to the left, obtaining bcf_g or bcg_f, or we could bring the boat over empty, obtaining bc_fg, which is forbidden, and red in the diagram. But having done that, we could then bring the boat back empty, to c_bfg again, or with the cereal, to _bcfg, which would win, except that the win doesn't count because we got there by passing through the forbidden red node bc_fg. – MJD Feb 13 '15 at 15:38

2'5 9'2 · Answer 2 · 2014-03-12T01:33:15.790

Graph theory, sort of, can help you see a solution.

Make a bipartite graph. Vertices off to the left mean the boat (and the man) is on the left bank. Vertices off to the right mean the boat is on the right bank. Each of the two sets has $8$ vertices, one for each of the possible subsets that could be on the corresponding bank. Make edges by just methodically connecting vertices on one side legally to vertices on the other, where a legal connection is one that doesn't let anyone/anything get eaten. Actually, there won't be so many as 8 vertices on each side, since some states will never occur, like (left,fox,goose) and (left, man, fox).

The solution will be visible as a path from the vertex (left, man, fox, goose, cereal) to (right, man, fox, goose, cereal).

enter image description here

score 3 · Answer 3 · answered Mar 12 '14 at 09:26

But perhaps graph theory is overkill; in this case, we can just solve the problem by reasoning about it. This is not brute force as we do not consider all possibilities. Far from it! – in fact, at all stages it turns out that there's only really one move to consider. To pre-empt any accusations of a lack of mathematics in this solution, the mathematics is in the symmetry observation in step 3.

I'll write positions as things like FG-Cb, where the letters stand for fox, goose, cereal, boat and the dash indicates what's on what side. Thus, the initial position is FGCb-.

Unless we move the goose, something gets eaten while we're away. So move to FC-Gb.
Bringing the goose back to the left is pointless, so return empty: FCb-G.
By symmetry, it doesn't matter what we cross with next – the puzzle doesn't change if we move to a universe where cereal eats geese and geese eat foxes. Toss a coin, it comes up heads, we take the fox: C-FGb.
Bringing the fox back is pointless, so we must return with the goose to avoid her being eaten: CGb-F.
Bringing the goose back is pointless, so we must take the cereal to avoid it being eaten: G-FCb.
Now it's obvious that the solution is to go get the goose: Gb-FC, then -FGCb and we're done.

This is precisely depth-first / breadth-first search. In this graph, there are only two nodes that have more than two neighbours (i.e., more than one neighbour other than the one you visited it from), and you argued by symmetry in step 3, and argued that "going back is pointless" in step 4. — ShreevatsaR, Mar 12 '14 at 11:50
@ShreevatsaR I agree that the effect is exactly the same but it avoids having to set up any of the graph-theoretic concepts. — David Richerby, Mar 12 '14 at 11:56
You could make another use of symmetry. At the middle of step 4, you're in the boat with the goose in the middle of the river; the fox is on the target bank and the cereal is on the starting bank. This situation is symmetrical under interchanging fox with cereal (as you did) and interchanging the two banks of the river. The rest of the solution, going forward from this moment, is obtained from what you've already done (steps 1,2,3, and half of 4) by applying this symmetry and reversing time. — Andreas Blass, Mar 18 '14 at 14:59

score 1 · Answer 4 · edited Apr 13 '17 at 12:20

The solutions by MJD and alex.jordan both use graph theory. However, MJD's is only solvable "by eyeball" because his graph-drawing software has made the paths obvious and alex.jordan's is rather hard (but by no means impossible) to solve by eye because the graph was drawn by hand and came out a bit messy. So, the question becomes, "How can I produce a graph by hand that looks more like MJD's and less like alex's?"

The first thing to do is to check how large the search space is. If the search space is small, we can work by hand without needing to be too smart; if it's of moderate size, we can solve it by computer without being too smart; if it's large, we need to use a computer and be smart. Rough estimate: we have a boat, a fox, a goose and some cereal, each of which can be on the left or right side of the river, so the number of states is at most $2^4=16$, which is small. In fact, there are fewer states than this because several potential states leave the goose unattended with either the fox or the cereal.

We should also get a handle on the branching factor: how many legal moves are there in each position? There are never more than four options (cross with nothing, with the fox, with the goose or with the cereal) but, actually, there can't be more than three that don't result in something being eaten since, if all three cargoes are on the same side, we must move the goose. Also, in any position except the initial one, one of our available moves is to undo the move we just did, which is pointless. So the branching factor is, in fact, at most two for every position; again, we don't need to do anything smart.

Since the search space and branching factor are both small, we can proceed by breadth-first search. Depth-first runs the risk of going down long side-branches and wasting lots of time investigating any long solutions that might exist. To help the breadth-first search, we also have the following key observation which we have, in fact, already used: an optimal (shortest) solution never repeats a position. If a solution repeats a position, you could get a shorter solution by skipping the steps between the two occurrences of that position. Therefore, in our search, if we ever come across a branch we've seen before, we can discard it immediately. Likewise, discard any position where something gets eaten.

Now, if you start drawing out the breadth-first search tree, you'll see something that looks very much like MJD's diagrams and it will be easy to see that there is a solution.

By the way, even with depth-first search, you don't visit states more than once (that's part of the definition of depth-first search), and as there are less than $16$ states (as you observed), a depth-first search will do just as well. (It just may not give the shortest path.) (Though in this case, there are exactly two paths, and so all (both) paths are of equal length.) — ShreevatsaR, Mar 12 '14 at 11:44
I also would like to point out that although OP specifically asks for “anything except brute force”, my solution is exactly brute force, exhaustively searching the space of possible moves. But this problem is so tiny that there is no way to solve it without "brute force", simply because there are only ten positions and the smallest solution visits eight of them. — MJD, Mar 12 '14 at 15:01

camel · Answer 5 · 2014-03-18T14:01:43.277

If you want to avoid logic and graphical proofs, another way to go about is is by noticing the following: fox and cereal are +- the same, they pose problems when placed together with the goose but they don't harm eachother.

You can then construct the following states:

----------------
| left | right | (fox/cereal)
----------------
| left | right | (goose)
----------------
| left | right | (man)
----------------

If you then write down all allowed positions with the man at the left, the symmetrie of the rules tells you that if you swap left and right, you have the whole set of allowed positions.

You can then define the following states :

A     B     C     D
2|0   2|0   1|1   0|2
1|0   0|1   1|0   1|0
1|0   1|0   1|0   1|0

and define the operator * as swapping left and right, we basically have to go from A->A* to solve this riddle.

You can then construct the following matrix:

         state1*     state2*    ...
state1   possible?   possible?
state2   possible?   possible?
...

Applied to the states we defined, this matrix would look something like this (let's name him Y) Also notice, Y is symmetric.

     A* B* C* D*
A    0  0  0  1
B    0  0  1  1
C    0  1  1  0
D    1  1  0  0

It is then possible to find the least amount of steps it takes to go from A->A* by finding the smallest n (n a natural value) for which Y^(2*n+1)[0][0] is not zero, then the smallest path is 2*n+1. In our case it's n=3 => the smallest path is 7 steps

Now on to finding the path. If you do

(Y^7).1 = 1
      0   6
      0   14
      0   14

We realize that there is only 1 way to go from A to A* in 7 steps, this means that in every step along the way, there should only be one way to reach it. Now to reconstruct this path, we should take Y^6, Y^5, Y^4 ... and multiply it by [1,0,0,0] (we already had to do this to realize 7 steps is the least). If you see a 1 in the resulting matrix, it was a point our solution went past. (odd exponents of Y means we're going to the right side, even exponents means we're going to the left side)

For example:

(Y^6).1 = 5
      0   9
      0   5
      0   1

so the step before the last one, was at state D. An example for the last few steps : A* <= D <= B* <= ... <= A

--------------------------------------------------

I do not think this is the best solution at all, but you requested an algebraic solution. This is the most algebraic I could make it with the least amount of brute force / enumerating solutions. This puzzle is however so small that every single step along the way is essentially forced, and you could simply use logic...

I don't think those graphs were correct solutions, because they were plain brute force of the search-space.

Bringing the fox, the goose and the cereal across the river unharmed

5 Answers5