Farmer, Goat, Bag of Corn prolog problem.....

JRed33

unread,

Apr 28, 1998, 3:00:00 AM4/28/98

to

I'm having trouble w/ programming this classic puzzle in prolog. The puzzle(if
nobody already knows) deals w/ the farmer trying to get all of these three
items :
1. Farmer
2. Goat
3. Bag Of Corn
across from one side of the river, to the other. The only problem is that the
boat can only hold the farmer and one other item in it, at one time.

here's what i have so far(i'm using a Depth-First search):

dfsearch(Anspath) :- initial_state(Init), df([Init], Anspath).

extend([S | Path], S1) :-
next_state(S, S1),
not(member(S1, [S | Path])).

member(S, [S | Rest]).
member(S, [_ | Rest]) :-
member(S, Rest).

.....the only undefined predicates so far are my :
next_state, initial_state, and final_state.......

if anybody knows anything about this classic problem please reply to this post
ASAP... the project is due May 1st......thank you

Brett R. Selleck

unread,

Apr 28, 1998, 3:00:00 AM4/28/98

to

I had to do a farmer wolf goat and cabbage problem, that is very similar
to this one. I wrote a breadth first search that takes you through the
search space, then prints out the entire path.

Here is the code!

writelist([]).
writelist([H|T]):-
write(H), writelist(T).

empty_queue([]).
enqueue(E,[],[E]).
enqueue(E,[H|T],[H|Tnew]):- enqueue(E,T,Tnew).
dequeue(E,[E|T],T).
dequeue(E,[E|T],_).
member_queue(Element,Queue):-member(Element, Queue).
add_list_to_queue(List, Queue, Newqueue):-
append(Queue, List, Newqueue).

empty_set([]).
member_set(E,S):-
member(E,S).
add_if_not_in_set(X,S,S):-
member(X,S),!.
add_if_not_in_set(X,S,[X|S]).
union([],S,S).
union([H|T],S,S_new):-
union(T,S,S2),
add_if_not_in_set(H,S2,S_new),!.

unsafe(state(X,Y,Y,C)):-
opp(X, Y).
unsafe(state(X,W,Y,Y)):-
opp(X, Y).

move(state(X,X,G,C), state(Y,Y,G,C)):-
opp(X,Y), not(unsafe(state(Y,Y,G,C))),
writelist(['try farmer takes wolf ',Y,Y,G,C]),nl.

move(state(X,W,X,C), state(Y,W,Y,C)):-
opp(X,Y), not(unsafe(state(Y,W,Y,C))),
writelist(['try farmer takes goat ',Y,W,Y,C]),nl.

move(state(X,W,G,X), state(Y,W,G,Y)):-
opp(X,Y), not(unsafe(state(Y,W,G,Y))),
writelist(['try farmer takes cabbage ',Y,W,G,Y]),nl.

move(state(X,W,G,C), state(Y,W,G,C)):-
opp(X,Y), not(unsafe(state(Y,W,G,C))),
writelist(['try farmer takes self ',Y,W,G,C]),nl.

move(state(F,W,G,C), state(F,W,G,C)):-
writelist([' BACKTRACK from: ',F,W,G,C]),nl,fail.

path(Open_queue,_,_):-
empty_queue(Open_queue),
write('Graph searched, no solution found.').

path(Open_queue, Closed_set, Goal):-
dequeue([State, Parent], Open_queue,_), State=Goal,
write('The solution path is:'), nl,
printsolution([State, Parent], Closed_set).

path(Open_queue, Closed_set, Goal):-
dequeue([State, Parent], Open_queue, Rest_open_queue),
get_children(State, Rest_open_queue, Closed_set, Children),
add_list_to_queue(Children, Rest_open_queue, New_open_queue),
union([[State, Parent]], Closed_set, New_closed_set),
path(New_open_queue, New_closed_set, Goal),!.

opp(e,w).
opp(w,e).

get_children(State, Rest_open_queue, Closed_set, Children):-
(bagof(Child, moves(State, Rest_open_queue,
Closed_set, Child), Children);
Children = []).

moves(State, Rest_open_queue, Closed_set, [Next, State]):-
move(State, Next),
not(unsafe(Next)),
not(member_queue([Next,_], Rest_open_queue)),
not(member_set([Next,_], Closed_set)).

go(Start, Goal):-
empty_queue(Empty_open_queue),
enqueue([Start, nil],Empty_open_queue, Open_queue),
empty_set(Closed_set),
path(Open_queue, Closed_set, Goal).

test:-go(state(w,w,w,w), state(e,e,e,e)).

printsolution([State, nil],_):-
write(State),nl.
printsolution([State, Parent], Closed_set):-
member_set([Parent, Grandparent], Closed_set),
printsolution([Parent, Grandparent], Closed_set),
write(State), nl.

Brett R. Selleck

unread,

Apr 29, 1998, 3:00:00 AM4/29/98

to

sory Ididn't realize you wanted a depth first search

here is a depth first search of the farmer wolf goat and cabbage problem

% Farmer, goat, wolf, and cabbage problem.

writelist([]).
writelist([H|T]):-
write(H), writelist(T).

empty_stack([]).
stack(Top, Stack, [Top|Stack]).
member_stack(Element, Stack):-
member(Element, Stack).

reverse_print_stack(S):-
empty_stack(S).
reverse_print_stack(S):-
stack(E, Rest, S),
reverse_print_stack(Rest),
write(E), nl.

unsafe(state(X,Y,Y,C)):-
opp(X, Y).
unsafe(state(X,W,Y,Y)):-
opp(X, Y).

move(state(X,X,G,C), state(Y,Y,G,C)):-
opp(X,Y), not(unsafe(state(Y,Y,G,C))),
writelist(['try farmer takes wolf ',Y,Y,G,C]),nl.

move(state(X,W,X,C), state(Y,W,Y,C)):-
opp(X,Y), not(unsafe(state(Y,W,Y,C))),
writelist(['try farmer takes goat ',Y,W,Y,C]),nl.

move(state(X,W,G,X), state(Y,W,G,Y)):-
opp(X,Y), not(unsafe(state(Y,W,G,Y))),
writelist(['try farmer takes cabbage ',Y,W,G,Y]),nl.

move(state(X,W,G,C), state(Y,W,G,C)):-
opp(X,Y), not(unsafe(state(Y,W,G,C))),
writelist(['try farmer takes self ',Y,W,G,C]),nl.

move(state(F,W,G,C), state(F,W,G,C)):-
writelist([' BACKTRACK from: ',F,W,G,C]),nl,fail.

path(Goal, Goal, Been_stack):-
nl, write('Solution Path is: '), nl,
reverse_print_stack(Been_stack).

path(State, Goal, Been_stack):-
move(State, Next_state),
not(member_stack(Next_state, Been_stack)),
stack(Next_state, Been_stack, New_been_stack),
path(Next_state, Goal, New_been_stack),!.

opp(e,w).
opp(w,e).

go(Start, Goal):-
empty_stack(Empty_been_stack),
stack(Start, Empty_been_stack, Been_stack),
path(Start, Goal, Been_stack).

test:-go(state(w,w,w,w), state(e,e,e,e)).

--

arik...@gmail.com

unread,

Jun 14, 2014, 4:28:29 PM6/14/14

to

I am having problem with this Code,When i run it in SWi prolog it shows error.
Please tell me how can i run it and query on it

/*
* This is the code for the Farmer, Wolf, Goat and Cabbage Problem
* using the ADT Stack.
*
* Run this code by giving PROLOG a "go" goal.
* For example, to find a path from the west bank to the east bank,
* give PROLOG the query:
*
* go(state(w,w,w,w), state(e,e,e,e)).
*/

:- [adts]. /* consults (reconsults) file containing the
various ADTs (Stack, Queue, etc.) */

go(Start,Goal) :-
empty_stack(Empty_been_stack),
stack(Start,Empty_been_stack,Been_stack),
path(Start,Goal,Been_stack).

/*
* Path predicates
*/

path(Goal,Goal,Been_stack) :-
write('Solution Path Is:' ), nl,
reverse_print_stack(Been_stack).

path(State,Goal,Been_stack) :-
move(State,Next_state),
not(member_stack(Next_state,Been_stack)),
stack(Next_state,Been_stack,New_been_stack),
path(Next_state,Goal,New_been_stack),!.

/*
* Move predicates
*/

move(state(X,X,G,C), state(Y,Y,G,C))
:- opp(X,Y), not(unsafe(state(Y,Y,G,C))),

writelist(['try farmer takes wolf',Y,Y,G,C]).

move(state(X,W,X,C), state(Y,W,Y,C))
:- opp(X,Y), not(unsafe(state(Y,W,Y,C))),

writelist(['try farmer takes goat',Y,W,Y,C]).

move(state(X,W,G,X), state(Y,W,G,Y))
:- opp(X,Y), not(unsafe(state(Y,W,G,Y))),

writelist(['try farmer takes cabbage',Y,W,G,Y]).

move(state(X,W,G,C), state(Y,W,G,C))
:- opp(X,Y), not(unsafe(state(Y,W,G,C))),

writelist(['try farmer takes self',Y,W,G,C]).

move(state(F,W,G,C), state(F,W,G,C))
:- writelist([' BACKTRACK from:',F,W,G,C]), fail.

/*
* Unsafe predicates
*/

unsafe(state(X,Y,Y,C)) :- opp(X,Y).
unsafe(state(X,W,Y,Y)) :- opp(X,Y).

/*
* Definitions of writelist, and opp.
*/

writelist([]) :- nl.
writelist([H|T]):- print(H), tab(1), /* "tab(n)" skips n spaces. */
writelist(T).

opp(e,w).
opp(w,e).

Jan Burse

unread,

Jun 15, 2014, 1:13:39 PM6/15/14

to

Hi,

Your code looks similar to:
http://stackoverflow.com/questions/22214381/farmer-goat-wolf-and-cabbage-in-prolog-via-breadth-first-search

Except that you try something with a stack data type.
It looks like that the stack is defined as:

empty_stack([]).
stack(X,Y,[Y|X]).
etc..

I guess you are doing depth first with loop checking.

What error do you get?

Bye

arik...@gmail.com schrieb:

graham...@gmail.com

unread,

Jun 28, 2014, 11:43:17 PM6/28/14

to

On Sunday, June 15, 2014 10:13:39 AM UTC-7, Jan Burse wrote:
> Hi,
>
>
>
> Your code looks similar to:
>
> http://stackoverflow.com/questions/22214381/farmer-goat-wolf-and-cabbage-in-prolog-via-breadth-first-search
>
>
>
> Except that you try something with a stack data type.
>
> It looks like that the stack is defined as:
>
>
>
> empty_stack([]).
>
> stack(X,Y,[Y|X]).
>
> etc..
>
>
>
> I guess you are doing depth first with loop checking.
>
>
>
> What error do you get?
>
>
>
> Bye

The solution isn't more than 9 river crossings is it?

move n Y Z to s Y Z
move n n Z to s s Z
move n Y n to s Y s
move s Y Z to n Y Z
move s s Z to n n Z
move s Y s to n Y n

go A B C to X Y Z [ t TIME ] :-
move A B C to D E F
go D E F to X Y Z TIME

-------- 1 STEP --------

TRACE
go n n n to s s s 1?

go n n n to s s s 1?
NOT FOUND!

-------- 2 STEPS --------

TRACE
go n n n to s s s [t 1] ?

TRY 1
RULE 7
go A B C to X Y Z [ t TIME ]
| TAIL 1
| move A B C to D E F
| move { n } { n } { n } to D E F
| TRY 1
| RULE 1
| move n Y Z to s Y Z
| | TAIL 2
| | go D E F to X Y Z TIME
| | go { s } { n } { n } to { s } { s } { s } { 1 }
| | FALSE 2
| FAIL
| TRY 2
| RULE 2
| move n n Z to s s Z
| | TAIL 2
| | go D E F to X Y Z TIME
| | go { s } { s } { n } to { s } { s } { s } { 1 }
| | FALSE 2
| FAIL
| TRY 3
| RULE 3
| move n Y n to s Y s
| | TAIL 2
| | go D E F to X Y Z TIME
| | go { s } { n } { s } to { s } { s } { s } { 1 }
| | FALSE 2
| FAIL
| FALSE 1
FAIL

go n n n to s s s [t 1] ?
NOT FOUND!

-------- 3 STEPS --------

TRACE
go n n n to s s s [t[t 1]] ?

TRY 1
RULE 7
go A B C to X Y Z [ t TIME ]
| TAIL 1
| move A B C to D E F
| move { n } { n } { n } to D E F
| TRY 1
| RULE 1
| move n Y Z to s Y Z
| | TAIL 2
| | go D E F to X Y Z TIME
| | go { s } { n } { n } to { s } { s } { s } { t 1 }
| | TRY 1
| | RULE 7
| | go A B C to X Y Z [ t TIME ]
| | | TAIL 1
| | | move A B C to D E F
| | | move { s } { n } { n } to D E F
| | | TRY 1
| | | RULE 4
| | | move s Y Z to n Y Z
| | | | TAIL 2
| | | | go D E F to X Y Z TIME
| | | | go { n } { n } { n } to { s } { s } { s } { 1 }
| | | | FALSE 2
| | | FAIL
| | | FALSE 1
| | FAIL
| | FALSE 2
| FAIL
| TRY 2
| RULE 2
| move n n Z to s s Z
| | TAIL 2
| | go D E F to X Y Z TIME
| | go { s } { s } { n } to { s } { s } { s } { t 1 }
| | TRY 1
| | RULE 7
| | go A B C to X Y Z [ t TIME ]
| | | TAIL 1
| | | move A B C to D E F
| | | move { s } { s } { n } to D E F
| | | TRY 1
| | | RULE 4
| | | move s Y Z to n Y Z
| | | | TAIL 2
| | | | go D E F to X Y Z TIME
| | | | go { n } { s } { n } to { s } { s } { s } { 1 }
| | | | FALSE 2
| | | FAIL
| | | TRY 2
| | | RULE 5
| | | move s s Z to n n Z
| | | | TAIL 2
| | | | go D E F to X Y Z TIME
| | | | go { n } { n } { n } to { s } { s } { s } { 1 }
| | | | FALSE 2
| | | FAIL
| | | FALSE 1
| | FAIL
| | FALSE 2
| FAIL
| TRY 3
| RULE 3
| move n Y n to s Y s
| | TAIL 2
| | go D E F to X Y Z TIME
| | go { s } { n } { s } to { s } { s } { s } { t 1 }
| | TRY 1
| | RULE 7
| | go A B C to X Y Z [ t TIME ]
| | | TAIL 1
| | | move A B C to D E F
| | | move { s } { n } { s } to D E F
| | | TRY 1
| | | RULE 4
| | | move s Y Z to n Y Z
| | | | TAIL 2
| | | | go D E F to X Y Z TIME
| | | | go { n } { n } { s } to { s } { s } { s } { 1 }
| | | | FALSE 2
| | | FAIL
| | | TRY 2
| | | RULE 6
| | | move s Y s to n Y n
| | | | TAIL 2
| | | | go D E F to X Y Z TIME
| | | | go { n } { n } { n } to { s } { s } { s } { 1 }
| | | | FALSE 2
| | | FAIL
| | | FALSE 1
| | FAIL
| | FALSE 2
| FAIL
| FALSE 1
FAIL

go n n n to s s s [t[t 1]] ?
NOT FOUND!

graham...@gmail.com

unread,

Jun 29, 2014, 12:05:12 AM6/29/14

to

> move n Y Z to s Y Z
>
> move n n Z to s s Z
>
> move n Y n to s Y s
>
> move s Y Z to n Y Z
>
> move s s Z to n n Z
>
> move s Y s to n Y n
>
>
>
> go A B C to X Y Z [ t TIME ] :-
>
> move A B C to D E F
>
> go D E F to X Y Z TIME
>

the color trace for anyone interested!

http://magicbook.com/mypix/farmer-goat.png

Message has been deleted

mazharv...@gmail.com

unread,

Jun 3, 2016, 1:52:23 AM6/3/16

to

I was work at Former,wolf,goat and corn problem solving by Depth first search but I am stuck.Therefore anybody have code of this problem in C++ or java?

Barb Knox

unread,

Jun 4, 2016, 5:18:11 AM6/4/16

to

On 3/06/2016 17:51, mazharv...@gmail.com wrote:
> On Tuesday, April 28, 1998 at 12:00:00 PM UTC+5, JRed33 wrote:
--------------

>> I'm having trouble w/ programming this classic puzzle in prolog. The puzzle(if
>> nobody already knows) deals w/ the farmer trying to get all of these three
>> items :
>> 1. Farmer
>> 2. Goat
>> 3. Bag Of Corn

4. Wolf

>> across from one side of the river, to the other. The only problem is that the
>> boat can only hold the farmer and one other item in it, at one time.
>>
>> here's what i have so far(i'm using a Depth-First search):

>> [...]

A depth-first search is a good choice for Prolog, since you can let the
automagic backtracking do a lot of the work.

A key decision you need to make is how to represent the current state.
You have 4 stateful items (the boat always stays with the farmer, so
they count as just 1).

It is usually best to represent states without redundancy: each state
has just one coding in the representation, and each coding in the
representation represents just one state.

One way to do this would be terms of the form:
state(Farmer, Goat, Corn, Wolf)
with each of the variable having the value 'left' or 'right' bank of the
river.

Then have:
illegal(state(Farmer, Goat, Corn, Wolf)) :-
Goat = Corn, Farmer \= Goat
; Wolf = Goat, Farmer \= Wolf.

Then:
move(FromState, ToState) :-
% Construct plausible ToState from FromState.
...
% Insure ToState is valid.
+\ illegal(ToState).

Then make successive moves in a recursive loop, starting with
state(left,left,left,left), ending with state(right,right,right,right),
and accumulating the successive states in a list, which is your result.

HTH.

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | ,008015L080180,022036,029037
| B B a a r b b | ,047045,L014114L4.
| BBB aa a r bbb |
-----------------------------

Markus Triska

unread,

Jun 5, 2016, 3:59:32 AM6/5/16

to

Barb Knox <s...@sig.below> writes:

> illegal(state(Farmer, Goat, Corn, Wolf)) :-
> Goat = Corn, Farmer \= Goat
> ; Wolf = Goat, Farmer \= Wolf.

In addition to what Barbara wrote, I would like to suggest using the
dif/2 predicate to make your solution more general. If your Prolog
system provides this constraint, you can use it to express disequality
of terms in a sound way, usable in all directions. Simply replace (\=)/2
by dif/2 to obtain more general programs, for example in the above case:

illegal(state(Farmer, Goat, Corn, Wolf)) :-

Goat = Corn, dif(Farmer, Goat)
; Wolf = Goat, dif(Farmer, Wolf).

The advantage is clear: We can now use this predicate also to generate
answers, also if some or all parts of the term are uninstantiated:

?- illegal(state(Farmer, Goat, c, w)).
%@ Goat = c,
%@ dif(Farmer, c) ;
%@ Goat = w,
%@ dif(Farmer, w).

?- illegal(S).
%@ S = state(_G1028, _G1029, _G1029, _G1031),
%@ dif(_G1028, _G1029) ;
%@ S = state(_G1028, _G1029, _G1030, _G1029),
%@ dif(_G1028, _G1029).

whereas we previously had the logically unsound answers:

?- illegal(state(Farmer, Goat, c, w)).
%@ false.

?- illegal(S).
%@ false.

This is unsound because in both cases, a _more specific_ query succeeds.

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

abdulrahma...@gmail.com

unread,

Dec 2, 2016, 11:55:55 AM12/2/16

to

On Tuesday, 28 April 1998 02:00:00 UTC-5, JRed33 wrote:
> I'm having trouble w/ programming this classic puzzle in prolog. The puzzle(if
> nobody already knows) deals w/ the farmer trying to get all of these three
> items :
> 1. Farmer
> 2. Goat
> 3. Bag Of Corn

> across from one side of the river, to the other. The only problem is that the
> boat can only hold the farmer and one other item in it, at one time.
>
> here's what i have so far(i'm using a Depth-First search):
>

> dfsearch(Anspath) :- initial_state(Init), df([Init], Anspath).
>
> df([S | Path], [S]) :- final_state(S), ! .
> df([S | Path], [S | AnsPath]) :-
> extend([S | Path], S1),
> df([S1, S | path], AnsPath).
>
> extend([S | Path], S1) :-
> next_state(S, S1),
> not(member(S1, [S | Path])).
>
> member(S, [S | Rest]).
> member(S, [_ | Rest]) :-
> member(S, Rest).
>
>
>
> .....the only undefined predicates so far are my :
> next_state, initial_state, and final_state.......
>
> if anybody knows anything about this classic problem please reply to this post
> ASAP... the project is due May 1st......thank you

Does anyone have an expert system(EXSHELL in prolog) and a knowledge base that can be used to solve the farmer, wolf, goat and cabbage puzzle?

jadenm...@gmail.com

unread,

Jan 3, 2020, 3:08:34 PM1/3/20

to

Just wondering whether you found an expert system and knowledge base that finds the solution to the farmer problem?

R Kym Horsell

unread,

Jan 6, 2020, 6:16:33 AM1/6/20

to

As a geriatric I allays like some of the early code for this.
David Warren had a prog called "Warplan" to solve these kinds of
planning problems (i.e. sequence of actions /state transforms to go
from a start state to an end state).

You declared properties of states that were "always" true;
"never" true; and what transformation of the state each action made.

Actions were parametized with Porlog Vars so it was quite flexible.

I'm sure it's still out there somewhere but it dates back to the 70s.

The version I extracted from an old conference proceedsing included
a number of nifty examples to help you tinker up other things.

The version in the book has "a number" of little problems, but there is
by now (I hope) a fully debuged version somewhere.

There used to be AI archives various places. May be a place to start the
google search. :)
--
Hohn, Michaelis, Hinterstoisser
p478
simulation gearbox with 1.8 MW capacity with different
lubricants with same viscosity
power loss (loaded)
gears bearings
(kw)
reference 15 30 45
PAO 15 25 40
PAG 15 20 35