» About     » Archive     » Cast     » Authors     » Submit     » Search     » Random     » Statistics     » Forum     » FAQ     » Video Game     » RSS Feed     Updates daily

No. 220:

First | Previous | 2009-07-15 | Next | Latest

First | Previous | 2009-07-15 | Next | Latest

Recited from memory by: Panpear

The author writes:

There's a classic logic puzzle that you've probably seen around. Well, I have at least... Let me explain it for those of you who haven't seen it.

You, a hard working farmer, need to take a wolf (all farmers breed wolves, I'm sure), a goat, and a very large cabbage to the market. To do so you need to cross a river that's not very big but too far to cross without a boat. Luckily, there's a boat, but it's only big enough for you and one of your items (yes, it's a very large cabbage). Let me illustrate the situation:

wolf, goat, cabbage

See? It's a large cabbage.

But here's the problem - if you're not there to supervise, the goat will eat the cabbage, and the wolf will eat the goat (though I'm not against things eating goats, with them closely related to cows). So how do you travel across the river?

I'll give you a minute to work it out.

... Solved it yet? No? Well here's the solution:

The first step is obvious - you need to take the goat, or otherwise eating will occur. So you row your boat across the river, drop off the goat, and row back.

step 1

Next you need to pick up either the wolf or cabbage - it doesn't matter which one. For this example we'll take the wolf to the other side of the river.

step 2

But now what? If you travel back to the other side with nothing in tow, the wolf will eat the goat! That means you should take one of the animals with you. Since you just brought the wolf over, it would make no sense to take it back - you would just end up in the same situation as before. So you need to travel back with the goat, like so:

step 3

Now it's straightforward; using the same reasoning as before, you take the cabbage to the other side, and leave the cabbage the wolf along together again.

step 4

And finally, you take the goat over once again, and the four of you head to the market.

There are many ways to solve this puzzle, such as guessing, or just deciding what the most logical move is. However, you could also try a brute force method. Computer programs might do something like this to solve a problem. For this particular problem, we could draw a state diagram to show each possible choice from every state. For example, the start state would be you (the farmer), the wolf, the goat, and the cabbage all on the left side of the river. That could spawn states where you and any single other item have travelled across the river.

Here is the complete state diagram for this problem:

state diagram

As you can see, many of the states lead back onto themselves, and most of them do not directly lead to the end state (all of you on the right side of the river). In fact, many of them lead to invalid states (a wolf and goat alone, or a goat and cabbage alone). Now you and I can easily tell when would be a good time to stop, or not continue along a certain route, but the way I created this diagram means it has to try every possible way to travel across the river, and only stop when it reaches an invalid state, or the end state.

It's okay it you're not following me; it took me a while to understand all of this stuff too. And I'm not good at explaining things. Maybe if I made a little program to show off how this puzzle works... after all I already got awesome graphics! ^_~

EDIT: Ughhh, it's too hard to make. Go find a site where someone already made a graphic version on the web, I'm sure someone has... So tired...