Bringing the fox, the goose and the cereal across the river unharmed 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.
 A: 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).

A: 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.

A: 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.
A: 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.
A: 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.
