Skip navigation

You’ve probably heard of this puzzle before. A farmer went to the market and bought a fox, a goose, and a bag of beans, on his way home he realizes that he has to cross a river, there’s a boat that can take him from one side to the other, but there’s a problem: The boat is only big enough for him and one of his belongings, How can the farmer cross the river knowing that he cannot leave the fox and the goose alone (because the fox will eat the goose) nor the goose and the bag of beans (because the goose will eat the beans)?

This is just one of many river-crossing puzzles, and they can all be solved using a very similar approach to what I’m going to show you:

First, let’s define the state of the puzzle at anytime:
st([Farmer, Fox, Goose, Beans])
where Farmer Fox Goose and Beans are variables that can take values of “left” or “right” whether that element is on the left or right side of the river.

Let’s tell Prolog what our initial and final states are:

initial(st([left, left, left, left])).

final(st([right, right, right, right])).

Solving these kind of puzzles is a matter of finding a node in a graph where each state of our puzzle is a node and the line between a node and another node is determined by a transition rule. The transition rule is nothing but a function that given a certain state will return a possible “next” state, say for example our initial state is st([left, left, left, left]), a valid next state could be st([right, left, right, left]) which means the farmer took the goose and crossed the river.

We define the transition rules as follows:

crossing(st([left,X,Y,Z]),st([right,X,Y,Z]), farmer_crosses_river).
crossing(st([right,X,Y,Z]),st([left,X,Y,Z]), farmer_comes_back).

crossing(st([left,X,left,Z]),st([right,X,right,Z]), bring_goose_over).
crossing(st([right,X,right,Z]),st([left,X,left,Z]), bring_goose_back).

crossing(st([left, left, X, Y]),st([right, right, X, Y]), bring_fox_over).
crossing(st([right, right, X, Y]),st([left, left, X, Y]), bring_fox_back).

crossing(st([left, X, Y, left]),st([right, X, Y, right]), bring_beans_over).
crossing(st([right, X, Y, right]),st([left, X, Y, left]), bring_beans_back).

The rules are pretty self-explanatory, crossing st([left,X,Y,Z]),st([right,X,Y,Z] means “farmer_crosses_river”, as you can see, the farmer variable changed from left to right and the rest was left intact.

Now, all those transitions are valid but we are tied down to certain restrictions, for example, the farmer can’t leave everything on one side or they will eat each other. For that reason we have to create a rule “not_allowed” that will be true whenever a state we transitioned to is illegal do to the circumstances of the puzzle. I mentioned earlier that crossing will match all possible states where we can move to, but after generating it we will use “not_allowed” to check if the state is legal.

not_allowed(st([X, Y, Y, _])) :- X \== Y.

not_allowed(st([X, _, Y, Y])) :- X \== Y.

Basically, the state that represents that the farmer is on one side and both the fox and the goose on the other is not allowed. Same for the goose and the bag of beans.

Now we have almost everything we need to solve the puzzle, we define the rule river(P) where P is a list of crossings,

river(P) :-
initial(Start), final(End),
river_aux(Start, End, [Start], P).

river_aux(A,B,V,P) is a rule that will be true when you can go to A from B by the crossings defined by P. V is the list of previously visited nodes on the graph, if we didn’t have V we would loop through the graph infinitely. To summarize, river_aux looks for a node in a graph, leaving from A, and after P transitions ends in B.

river_aux(A,A,_,[]). % To go from A to A the crossing is empty meaning that we do not cross at all, this will be true when we reach our destination.

river_aux(A,B,V,P) :-
crossing(A,C,Action),
not(not_allowed(C)),
not(member(C,V)),
river_aux(C,B,[C|V],Plan),
P = [Action | Plan].

As I mentioned earlier, crossing will try to match a node in the graph where we can go to from A called C by doing a certain crossing “Action”, later we check whether C is allowed, if it is we check that it has not been visited before by using “member” (to avoid loops), finally, we go from C to our final destination, adding C to the list of previously visited nodes and making P the previous actions plus the recent one.

We finally ask Prolog to look for a path from the initial state to the final one.

?- river(P).
P = [bring_goose_over, farmer_comes_back, bring_fox_over, bring_goose_back, bring_beans_over, farmer_comes_back, bring_goose_over] ;
P = [bring_goose_over, farmer_comes_back, bring_beans_over, bring_goose_back, bring_fox_over, farmer_comes_back, bring_goose_over] ;
false.

About these ads

One Comment

  1. why do people always put maths into this…the fox & the goose can both swim, so you tether them to each side of the boat, and travel across with the beans in the boat.. rapid solution.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: