Reverse Puzzling

George is a great puzzler, so I was extremely surprised when he didn't immediately know the answer to a really famous puzzle. It's a puzzle that you probably did years ago, and have heard so often you can do it from memory rather than working it out. It's also not really that difficult, so I was also surprised when it appeared to be stumping him.

"Come on, surely you know this one." I said.

"I don't. And don't call me Shirley." He answered grumpily. I could tell his mood was declining rapidly, but like any great puzzler he was down and not out, and I watched his facial expression change as he reached into his mental bag of tricks. He nodded towards a conveniently located white board. "Have you got a marker for that?"

I handed him one, and he drew up the following diagram:

He stepped back, admiring his work, beaming proudly. "Well, now the solution is very obvious!" he commented.

And indeed it was.

The question for you is:

what was the puzzle?

• 42! …wait, no, hold on… Commented Dec 23, 2015 at 8:25
• I've actually learnt something from this. I'd never thought of how to do a formal proof for this puzzle so now having seen the answer I reckon I can solve any puzzle of this type. :) Commented Dec 23, 2015 at 9:11
• @Chris For your benefit puzzling.stackexchange.com/questions/18/… , altough it seems like you've already worked it out from the graph above :) Commented Dec 23, 2015 at 9:34
• I assume C*|FC is a typo for B|*FC? Commented Dec 23, 2015 at 11:17
• I think I found another typo - B*|FC should be B|*FC Commented Dec 23, 2015 at 16:38

I don't know if the puzzle has an established name, but it should be something similar to this:

A man has to get a Fox, a Chicken, and a sack of Barley across a river.
He has a rowboat, and it can only carry him and one other thing.
If the fox and the chicken are left together, the fox will eat the chicken.
If the chicken and the barley are left together, the chicken will eat the barley.
How does the man do it?

.

All nodes in the graph represent all the LEGAL states in the puzzle (where nothing can eat anything else). Each line between each pair of nodes represents a single move (i.e. the man crossing the river).

.

F represents the Fox, C represents the Chicken, B represents the Barley, * represents the man, and | represents the river.

The puzzle starts at the top left node, and the goal state is at the bottom right node.

(On second thought, the reverse could be true as well, if the man starts on the right side of the river instead.)

• This doesn't explain connection between FB*|C and C*|FC. And what is C*|FC at all? Commented Dec 23, 2015 at 11:06
• @klm123: A typo for B|*FC.
– Deusovi
Commented Dec 23, 2015 at 11:13
• Congratulations! You were extremely quick on this. I was hoping that it would be a bit more baffling. Glad to see that it was an enjoyable puzzle though - I'll have to think about similar ones... Commented Dec 23, 2015 at 20:19
• @DrXorile Thanks for the puzzle! It was really enjoyable and I was super fortunate to have visited the site the second you posted the question :P I think what made it easier was your insistence that it was a famous puzzle - that instantly narrowed it down quite a bit :) Commented Dec 24, 2015 at 0:43

It looks to me like:

You (represented by *) have a fox (F), cat (C) and a bird (B) which you have to get over a river (|). and there's an error C*|FC should be B|*FC

• Foxes eat more birds then cats I think.. Commented Dec 23, 2015 at 14:18
• @DrunkWolf Not if it's a Tweety-like bird in a cage with a Sylvester-like cat and just a plain fox that can't open cages :) ) Commented Dec 23, 2015 at 14:24