2

I am an AI and Prolog newbie. I was trying to implement the 2 Water Jug problem in SWI Prolog. However, my solution is returning a global stack overflow.

I know this question has been asked in the past and has had numerous answers/solutions, as a complete newbie my approach is a bit naive, hence I wanted to know what am I doing wrong.

Problem:

There are two jugs, one has a capacity of 4 gallons while the other can hold up to 3 gallons. I need 2 gallons in the 4 gallon jug and the other one should be empty.

Here's the code:

member(X, [X|R]).
member(X, [Y|R]) :- member(X,R).

append([X|Y], Z, [X|W]) :- append(Y,Z,W).
append([], X, X).

/*                                                                                                                                            
production rules for the water jug problem                                                                                                    
*/
maneuver(X, Y, Z):-X=:=2, Y=:=0, write('done').
maneuver(X, Y, Z):-X<4, \+ member(Z, (4,Y)), append(Z, [(4,Y)], A), write('Fill 4 gallon jug\n'), maneuver(4,Y,A).
maneuver(X, Y, Z):-Y<3, \+ member(Z, (X,3)), append(Z, [(X,3)], A), write('Fill 3 gallon jug\b'), maneuver(X,3,A).
maneuver(X, Y, Z):-X>0, \+ member(Z, (0,Y)), append(Z, [(0,Y)], A), write('Empty the 4 gallon jug\n'), maneuver(0,Y,A).
maneuver(X, Y, Z):-Y>0, \+ member(Z, (X,0)), append(Z, [(X,0)], A), write('Empty the 3 gallon jug\n'), maneuver(X,0,A).
maneuver(X, Y, Z):-X+Y>=4, Y>0, \+ member(Z, (4,Y-(4-X))), append(Z, [(4,Y-(4-X))], A), write('Pour from 3 gallon jug to 4 gallon jug\n'), ma$
maneuver(X, Y, Z):-X+Y>=3, X>0, \+ member(Z, (X-(3-Y),3)), append(Z, [(X-(3-Y),3)], A), write('Pour from 4 gallon jug to 3 gallon jug\n'), ma$
maneuver(X, Y, Z):-X+Y=<4, Y>0, \+ member(Z, (X+Y, 0)), append(Z, [(X+Y, 0)], A), write('Pour the water in the 3 gallon jug into the 4 gallon$
maneuver(X, Y, Z):-X+Y=<4, Y>0, \+ member(Z, (0, X+Y)), append(Z, [(0, X+Y)], A), write('Pour the water in the 4 gallon jug into the 3 gallon$

Here's the output.

Fill 4 gallon jug
Fill 3 gallon juEmpty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
...
false
  • 10,264
  • 13
  • 101
  • 209
Utsav
  • 536
  • 2
  • 6
  • 18

2 Answers2

1

in Prolog, it make little sense to output the action 'description', because any sequence of actions that will fail will be undone, thus trying any available alternative. Then the first step I would take is a 'cosmetic one' : move away the description, that can be inferred from two adjacent steps of a solution (the list Z), and add a Solution argument to maneuver.

Another important improvement: all your steps repeat the same - wrong - pattern: for instance 

\+ member(Z, (4,Y)), append(Z, [(4,Y)], A)

make a 'subroutine' (and correct the mistake, that - I think - leads to the loop):

update(State, Step, Updated) :-
   \+ member(Step, State),
   append(State, [Step], Updated).
CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • 1
    You can also avoid `append/3` by using the `Updated` argument as a stack instead of as a queue. That will give a solution in reverse order, however. – Paulo Moura Aug 04 '13 at 10:24
1

There are 2 mistakes that need to be corrected in your code.

  1. you cannot directly write or refer Y-(4-X) kinda equations,

for example: if X=3,Y=5. It will consider it as 5-(4-3) but it will not take it as 3. So, you need to take extra variables to get the value.

  1. You don't need to write append function, as you're adding only one element you can directly attach it to

Z as [(4,Y)|Z].

The modified code will be like this:

member(X,[X|_]).
member(X,[Y|Z]):-member(X,Z).

move(X,Y,_):-X=:=2,Y=:=0,write('done'),!.
move(X,Y,Z):-X<4,\+member((4,Y),Z),write("fill 4 jug"),nl,move(4,Y,[(4,Y)|Z]).
move(X,Y,Z):-Y<3,\+member((X,3),Z),write("fill 3 jug"),nl,move(X,3,[(X,3)|z]).
move(X,Y,Z):-X>0,\+member((0,Y),Z),write("pour 4 jug"),nl,move(0,Y,[(0,Y)|Z]).
move(X,Y,Z):-Y>0,\+member((X,0),Z),write("pour 3 jug"),nl,move(X,0,[(X,0)|Z]).
move(X,Y,Z):-P is X+Y,P>=4,Y>0,K is 4-X,M is Y-K,\+member((4,M),Z),write("pour from 3jug to 4jug"),nl,move(4,M,[(4,M)|Z]).
move(X,Y,Z):-P is X+Y,P>=3,X>0,K is 3-Y,M is X-K,\+member((M,3),Z),write("pour from 4jug to 3jug"),nl,move(M,3,[(M,3)|Z]).
move(X,Y,Z):-K is X+Y,K<4,Y>0,\+member((K,0),Z),write("pour from 3jug to 4jug"),nl,move(K,0,[(K,0)|Z]).
move(X,Y,Z):-K is X+Y,K<3,X>0,\+member((0,K),Z),write("pour from 4jug to 3jug"),nl,move(0,K,[(0,K)|Z]).

if input is:

move(0,0,[(0,0)]).

output is:

fill 4 jug
fill 3 jug
pour 4 jug
pour 3 jug
fill 4 jug
pour from 4jug to 3jug
pour 3 jug
pour from 4jug to 3jug
fill 4 jug
pour from 4jug to 3jug
pour 3 jug
done
Strange
  • 1,460
  • 1
  • 7
  • 18