What's wrong with my prolog program for solving the 3 jugs of water puzzle?

Question

Can anyone find why I can't have any true answers with my 'go' at this code? For example, I write go(7,3,l) and I suppose that it should move 3 litres of water to the second jug, but it is false according to prolog. What's wrong?

:- dynamic go/3.
:- dynamic cur_state/1,init/5.
:- dynamic end_state/1, final/5.

cur_state(State):-State = state(10,0,0,7,l).
end_state(State):-State = state(0,3,3,0,r).

pour(state(D1,D2,D3,n,l),move(D,C,r),state(D,C,D3,n,r)) :-
        D is D1-n,
        C is D2+n.
pour(state(D1,D2,D3,n,r),move(D,C,l),state(D,C,D3,n,l)) :-
        D is D1-n,
        C is D2.
pour(state(D1,D2,D3,n,l),move(D,C,r),state(D,D2,C,n,r)) :-
        D is D1-n,
        C is D3+n.
pour(state(D1,D2,D3,n,l),move(D,C,r),state(D1,D,C,n,r)) :-
        D is D2-n,
        C is D3+n.
pour(state(D1,D2,D3,n,r),move(D,C,l),state(D1,D,C,n,l)) :-
        D is D2-n,
        C is D1+n.
pour(state(D1,D2,D3,n,r),move(D,C,l),state(D1,D,c,n,l)) :-
        D is D2-n,
        C is D3.
pour(state(D1,D2,D3,n,l),move(D,C,r),state(C,D2,D,n,r)) :-
        D is D3-n,
        C is D1.
pour(state(D1,D2,D3,n,r),move(D,C,l),state(D1,C,D,n,l)) :-
        D is D3-n,
        C is D2+n.
pour(state(D1,D2,D3,n,r),move(D,C,l),state(C,D2,D,n,l)) :-
        D is D3-n,
        C is D1+n.

carry(7,0).
carry(3,0).
carry(10,0).
carry(7,0).
carry(7,3).

legal(10,X,Y):-X+Y<10.
legal(X,Y,Z):-X+Y+Z<10.
legal(X,7,Y):-X+Y=<3.
legal(X,Y,3):-X+Y=<7.

newstate(state(D1,D2,D3,n,l),state(D11,D22,D33,n1,r)):-
        carry(M,C),
        M=<7,C=<3,
        D22 is D2+n,
        D11 is D1-n,
    D3 is D33,
    n1 is n,
        D2=<7,D1=<10,
    legal(D1,D2,D3).

newstate(state(D1,D2,D3,n,r),state(D11,D22,D33,n1,l)):-
        carry(M,C),
        M=<10,C=<100,
        D11 is D1-n,
    D22 is D2,
    D33 is D3,
        D1=<10,
    legal(D1,D2,D3).

newstate(state(D1,D2,D3,n,l),state(D11,D22,D33,n1,r)):-
        carry(M,C),
        M=<10,C<3,
        D11 is D1-n,
        D33 is D3+n,
    D22 is D2,
        D1=<10,D3=<3,
    legal(D1,D2,D3).

newstate(state(D1,D2,D3,n,r),state(D11,D22,D33,n1,l)):-
        carry(M,C),
        M=<7,C=<3,
        D22 is D2-n,
        D33 is D1+n,
        D11 is D1,
    D2=<7,D1=<10,
    legal(D1,D2,D3).

newstate(state(D1,D2,D3,n,l),state(D11,D22,D33,n1,r)):-
        carry(M,C),
        M=<7,C=0,
        D22 is D2-n,
        D33 is D3+n,
        D11 is D1,
    D2=<7,D3=<3,
    legal(D1,D2,D3).

newstate(state(D1,D2,D3,n,r),state(D11,D22,D33,n1,l)):-
        carry(M,C),
        M=<7,C=<100,
        D22 is D2-n,
    D33 is D3,
    D11 is D1,    
    D2=<7,
    legal(D1,D2,D3).

newstate(state(D1,D2,D3,n,r),state(D11,D22,D33,n1,l)):-
        carry(M,C),
        M=<3,C=<7,
        D22 is D2+n,
        D33 is D3-n,
        D11 is D1,
    D3=<3,D2=<7,
    legal(D1,D2,D3).

newstate(state(D1,D2,D3,n,r),state(D11,D22,D33,n1,l)):-
        carry(M,C),
        M=<3,C=<100,
        D11 is D1+n,
        D33 is D3-n,
        D22 is D2,
    D3=<3,D1=<10,
    legal(D1,D2,D3).

newstate(state(D1,D2,D3,n,l),state(D11,D22,D33,n1,r)):-
        carry(M,C),
        M=<3,C=<100,
        D33 is D3-n,
        D22 is D2,
    D11 is D1,  
    D3=<3,
    legal(D1,D2,D3).


eisodos(_):- cur_state(State),write(State),nl.

init(S1,S2,S3,S4,S5):-assert(cur_state(State):-State = state(S1,S2,S3,S4,S5)),write('Arxikh:'),
   write(state(S1,S2,S3,S4,S5)),retractall(init(S1,S2,S3,S4,S5)),nl.

final(S1,S2,S3,S4,S5):-assert(end_state(State):-State = state(S1,S2,S3,S4,S5)),write('Telikh:'),
   write(state(S1,S2,S3,S4,S5)),retractall(init1(S1,S2,S3,S4,S5)),nl.

go(Move1,Move2,Move3):-cur_state(State),newstate(State,NextState),
        pour(State,move(Move1,Move2,Move3), NextState),
        retractall(cur_state(State):-State = state(_,_,_,_,_)),asserta(cur_state(NextState)),
        ((end_state(NextState),write('Bravo!!!!')) ;(write(' ---*Eiste sthn katastash --- :'),write(NextState))),nl.

Seing that code does not give me the taste to learn prolog, sorry. — Luc M, Jan 05 '12 at 20:03
I can't find why your go predicate doesn't work but I kinda have to admit I can't find why your go predicate should work either... What are you trying to achieve here ? — m09, Jan 05 '12 at 21:00
i'm tyring to write a programm that simulates the problem of 3 jugs of water and the possible moves of water between them — tetartos, Jan 05 '12 at 21:04

score 3 · Answer 1 · answered Jan 06 '12 at 00:36

Expanding on @Mog's answer, I suggest to use iterative deepening if you want to find a shortest solution. The following is based on the code posted by @Mog (and thus solves the same problem that is slightly different from the one posted by OP). As we want to describe a list (of moves), DCG notation is convenient:

solution(Path) :- length(Path, _), phrase(path([0-3, 0-5, 8-8]), Path).

path(State) --> { equivalent(State, [0-3, 4-5, 4-8]) }.
path(State0) --> [From-To],
        { move(State0, State), State = [_-From, _-To, _] },
        path(State).

equivalent(State1, State2) :- forall(member(X, State1), member(X, State2)).

move(State, [NewX-From, NewY-To|NewRest]) :-
    select(X-From, State, Rest),
    X \== 0,
    select(Y-To, Rest, NewRest),
    Fillable is To - Y,
    ToFill is min(X, Fillable),
    NewY is Y + ToFill,
    NewX is X - ToFill.

Sample query:

?- solution(Ps).
Ps = [8-5, 5-3, 3-8, 5-3, 8-5, 5-3, 3-8] .

m09 · Answer 2 · 2012-01-06T01:03:12.120

Well so as I said in my comment, I kinda wouldn't know how to help you with your current work since there are so many wrong things in it. I'd advise you to read a nice tutorial about Prolog (such as Learn Prolog now) so that you can grab the language basics. Here is a simple way to solve your problem if you're interested. If you don't want your problem to be spoiled, just don't read further : ] (the one I posted is about a 3/5/8 jugs and a 4/4 split).

go(Path) :-
    solve([0-3, 0-5, 8-8], [], [], Temp),
    reverse(Temp, Path).

solve(State, _Visited, Path, Path) :-
    equivalent(State, [0-3, 4-5, 4-8]).
solve(State, Visited, Acc, Path) :-
    move(State, NewState),
    NewState = [_-From, _-To|_],
    forall(member(Past, Visited), \+ equivalent(Past, NewState)),
    solve(NewState, [NewState|Visited], [From-To|Acc], Path).

equivalent(State1, State2) :-
    forall(member(X, State1), member(X, State2)).

move(State, [NewX-From, NewY-To|NewRest]) :-
    select(X-From, State, Rest),
    X \== 0,
    select(Y-To, Rest, NewRest),
    Fillable is To - Y,
    ToFill is min(X, Fillable),
    NewY is Y + ToFill,
    NewX is X - ToFill.

If you need explanations about the code once you've read a little more about prolog, don't hesitate!

Firts of all thank you! But my problem is that i want the user to 'write' the path by calling a 'function' that's what i was trying to do. For example i wanted in my programm the user to write go(7,3,0,3,r) and 3 litres to go in the second jug.Any ideas on that?? — tetartos, Jan 17 '12 at 22:01

score 0 · Accepted Answer · answered Jan 06 '12 at 10:17

The first thing you need to correct it's basic syntax: variables must begin with uppercase, so for instance you must change this rule

pour(state(D1,D2,D3,n,l),move(D,C,r),state(D,C,D3,n,r)) :-
    D is D1-n,
    C is D2+n.

to

pour(state(D1,D2,D3,N,l),move(D,C,r),state(D,C,D3,N,r)) :-
    D is D1-N,
    C is D2+N.

and

newstate(state(D1,D2,D3,n,l),state(D11,D22,D33,n1,r)):-
        carry(M,C),
        M=<7,C=<3,
        D22 is D2+n,
        D11 is D1-n,
    D3 is D33,
    n1 is n,
        D2=<7,D1=<10,
    legal(D1,D2,D3).

to

newstate(state(D1,D2,D3,N,l),state(D11,D22,D33,N1,r)):-
    carry(M,C),
    M=<7,C=<3,
    D22 is D2+N,
    D11 is D1-N,
    D3 is D33,
    N1 is N,
    D2=<7,D1=<10,
    legal(D1,D2,D3).

You should realize that N1 is valorized just in the first newstate/2 procedure: then correct the other instances of that rule.

Then you should remove the useless dynamic assertions: think about your actual assert/retractall usage: what you need is to change the state moving 'water' between 'jugs' at any step: so you should assert/retract state/5 while looping in go, from an initial state (assert this at start program), to a final acceptable state, to be tested in go to stop the cycle.

But this style based on state change leads to very difficult debugging. Try instead to remove altogheter the dynamic,assert/retractall, and pass around the state in your cycle.

Thank you for your answers but if you don't mind read the comment i wrote @Mog and any ideas except of these will be usefull... — tetartos, Jan 17 '12 at 22:05
Did you tried to correct your program using the hints I wrote? Because any step I'd try would go along that way. Of course the simpler way to solve your problem could be to adapt (after understanding :) any of the correct solutions from Mog or mat. To be true I haven't tried these, but appears much more plausible than your code. The key to solve combinatorial problems (by brute force) is often the use of select/3 with an appropriate state representation — CapelliC, Jan 18 '12 at 07:09
Firstly thanks for your answer.I did tha changes you suggested and i have this when i'm trying go(7,3,r).:ERROR: is/2: Arguments are not sufficiently instantiated Exception: (7) newstate(state(10, 0, 0, 7, l), _G212) ? But i'm not sure that i have explained correctly what i want from my programma to do..It's a programm that solves the water jugs problem but a programm that the user 'says' what to do and if the user says the right moves the problem is solved without algorithms etc.. — tetartos, Jan 23 '12 at 07:13

What's wrong with my prolog program for solving the 3 jugs of water puzzle?

3 Answers3

Linked