One thing about this particular problem is that the tree of possible valid (non-repeated) states doesn't branch away from the two solutions. For the first move, taking either the wolf or the cabbage across leads to an invalid state. For the return trip, taking the goat back leads to a previously seen state. Now the farmer has the choice of taking either the wolf or the cabbage. As is turns out, either choice works -- let's say he takes the wolf. For the return trip, taking the wolf back leads to a repeated state. Taking nothing back leads to an invalid state. The only possibility left is taking the goat. Similar resoning leads directly to the solution(s). At no point does the farmer have to look farther ahead than the end of upcoming boat trip to make the right decision at any point.
We could add a twist to this problem:
Each boat trip takes 4 minutes. The farmer knows that there is a group of hungry amoral vegetarian pacifists on the trail a mere 15 minutes behind him. If the farmer leaves the cabbage ungarded on the original side of the river, after the 15 minute mark, the HAVPs, the farmer believes, will eat his cabbage. In contrast, the wolf and/or the goat would be safe from consumption. Also, the farmer could defend his use of the boat from the HAVPs.
How does that affect the algorithm?
How about this one:
That night, four people want to cross this same river, but this time over a bridge. The bridge is only strong enough for two people at a time. Two people walking together, can walk only as fast as the slower of the pair. Lastly, the bridge has holes and loose boards, so one or two people need a flashlight to cross. They have only one flashlight. The flashlight cannot be thrown across the river -- someone has to carry it.
The four people can cross at different speeds:
Campbell can cross in 10 minutes.Preeti can corss in 5 minutes.Jim can cross in 2 minutes.Ryan can cross in 1 minute. (Of course I mean Mr. DeJana is the fastest walker. How vain do you think I am? ) One strategy would be for the fastest walker, Ryan, to hold onto the flashlight and act as a ferry for the three other people:
Can you find a strategy that takes only 17 minutes? The tricky part here is that the tree of valid states is quite branchy compared to the Cabbage/Goat/Wolf problem. You can't identify an invalid state until you get to the 17 minute mark and someone isn't on the right side of the river yet.
Also, each one of our travelers has a balance and three coins, one of which may be heavier or lighter than the rest... Oh wait, wrong problem.
[ December 03, 2007: Message edited by: Ryan McGuire ]