Water Jug Problem

[Inny Akpabio]

Hello guys, I got this solution to the Water Jug Problem online... can any one please assist me on how to run it in SWIProlog, am new to Prolog. Thanks in anticipation

database

    rstate(integer,integer)

predicates

    state(integer,integer)

    

clauses

        

    state(2,_).

    state(0,0):-

        not(rstate(0,0)),

        assert(rstate(0,0)),    

        state(0,0).

        

    state(X,Y):-

    

        X < 4,

        not(rstate(4,Y)),

        assert(rstate(4,Y)),

        write("\n Rule 1 => (4,",Y,")"),

        state(4,Y).

        

    state(X,Y):-

    

        Y < 3,

        not(rstate(X,3)),

        assert(rstate(X,3)),

        write("\n Rule 2 => (",X,",3)"),

        state(X,3).

    

    state(X,Y):-

    

        X>0,

        not(rstate(0,Y)),

        assert(rstate(0,Y)),

        write("\n Rule 5 => (0,",Y,")"),

        state(0,Y).

    

    state(X,Y):-

    

        Y>0,

        not(rstate(X,0)),

        assert(rstate(X,0)),

        write("\n Rule 6 => (",X,",0)"),

        state(X,0).

    

    state(X,Y):-

    

        X+Y >= 4,

        Y > 0,

        Z=Y-(4-X),

        not(rstate(4,Z)),

        assert(rstate(4,Z)),

        write("\n Rule 7 => (4,",Z,")"),

        state(4,Z).

    

    state(X,Y):-

    

        X+Y >= 3,

        X>0,

        Z=X-(3-Y),

        not(rstate(Z,3)),

        assert(rstate(Z,3)),

        write("\n Rule 8 => (",Z,",3)"),

        state(Z,3).

    

    state(X,Y):-

    

        X+Y <= 4,

        Y > 0,

        Z=X+Y,

        not(rstate(Z,0)),

        assert(rstate(Z,0)),

        write("\n Rule 9 => (",Z,",0)"),

        state(Z,0).

        

    state(X,Y):-

    

        X+Y <= 3,

        X>0,

        Z=X+Y,

        not(rstate(0,Z)),

        assert(rstate(0,Z)),

        write("\n Rule 10 => (0,",Z,")"),

        state(0,Z).

        

    state(X,Y):-

    

        X=0,

        Y=2,

        not(rstate(2,0)),

        assert(rstate(2,0)),

        write("\n Rule 11 => (2,0)"),

        state(2,0).

    

    state(X,Y):-

    

        X=2,

        assert(rstate(0,Y)),

        write("\n Rule 12 => (0,",Y,")"),

        state(0,Y).

goal

    makewindow(1,2,3,"Water Jug Problem",0,0,25,80),

    write("Initially state(0,0)"),

    state(0,0),

    save("output.txt").

[John McCulloch]

I see that no-one has replied to this, so I thought I would give my advice, for what it's worth.  This code looks like Visual Prolog (derived from Turbo Prolog),  It would take a lot of modification to make this work in swipl.  I don't think that would be a job for a newcomer to prolog.

Sorry to present the bad news but the syntax in this code is much different that standard prolog.  SWI Prolog is much closer to the edinburrg and iso standards.  See if you can find the code for the same problem in a more standard prolog.

[Costa]

Hey:

Just played with the same problem the other day. I have another code based on the The Art of Prolog - Advanced Programming Techniques, Second Edition book by Leon Sterling and Ehud Shapiro.

Save the code below into a file with the extension pl, then open it in swi-prolog and compile it. Then you can run it from the console using: test_dfs(jugs, Moves). Press ; repeatedly to display each solution. Each solution will be contained in the Moves variable.

In the example below, there are two jugs, one of 10 and one of 7 and the program finds the solutions to get 6 in one of jugs.

solve_dfs(State, History, []) :- final_state(State).
solve_dfs(State, History, [Move|Moves]) :-
    move(State, Move),
    update(State, Move, State1),
    legal(State1),
    not(member(State1, History)),
    solve_dfs(State1, [State1|History], Moves).

test_dfs(Problem, Moves) :-
    initial_state(Problem, State), solve_dfs(State, [State], Moves).

capacity(1, 10).
capacity(2, 7).

initial_state(jugs, jugs(0, 0)).
final_state(jugs(0, 6)).
%final_state(jugs(4, 0)).

legal(jugs(V1, V2)).

move(jugs(V1, V2), fill(1)) :- capacity(1, C1), V1 < C1, capacity(2, C2), V2 < C2.
move(jugs(V1, V2), fill(2)) :- capacity(2, C2), V2 < C2, capacity(1, C1), V1 < C1.

move(jugs(V1, V2), empty(1)) :- V1 > 0.
move(jugs(V1, V2), empty(2)) :- V2 > 0.
move(jugs(V1, V2), transfer(1, 2)).
move(jugs(V1, V2), transfer(2, 1)).

adjust(Liquid, Excess, Liquid, 0) :- Excess =< 0.
adjust(Liquid, Excess, V, Excess) :- Excess > 0, V is Liquid - Excess.

update(jugs(V1, V2), fill(1), jugs(C1, V2)) :- capacity(1, C1).
update(jugs(V1, V2), fill(2), jugs(V1, C2)) :- capacity(2, C2).
update(jugs(V1, V2), empty(1), jugs(0, V2)).
update(jugs(V1, V2), empty(2), jugs(V1, 0)).

update(jugs(V1, V2), transfer(1, 2),jugs(NewV1, NewV2)) :-
    capacity(2, C2),
    Liquid is  V1 + V2,
    Excess is Liquid - C2,
    adjust(Liquid, Excess, NewV2, NewV1).

update(jugs(V1, V2), transfer(2, 1),jugs(NewV1, NewV2)) :-
    capacity(1, C1),
    Liquid is  V1 + V2,
    Excess is Liquid - C1,
    adjust(Liquid, Excess, NewV1, NewV2).

[Markus Triska]

Hi Costa,

thank you for sharing!

I would like to suggest the following food for thought: With a slightly different state representation, you can shorten the code significantly, because it lets you treat the cases more uniformly.

Consider the following description of the exact same task:

:- use_module(library(clpfd)).

jug_capacity(a, 10).
jug_capacity(b, 7).

moves(Jugs) -->
        { memberchk(jug(a,0), Jugs),
          memberchk(jug(b,6), Jugs) }.
moves(Jugs0) --> [fill(Jug)],
        { select(jug(Jug,_), Jugs0, Jugs),
          jug_capacity(Jug, C) },
        moves([jug(Jug,C)|Jugs]).
moves(Jugs0) --> [empty(Jug)],
        { select(jug(Jug,_), Jugs0, Jugs) },
        moves([jug(Jug,0)|Jugs]).
moves(Jugs0) --> [from_to(AID,BID)],
        { AF #> 0, select(jug(AID,AF), Jugs0, Jugs1),
          BF #< BC, select(jug(BID,BF), Jugs1, Jugs2),
          jug_capacity(BID, BC),
          Move #= min(AF,BC-BF),
          AF1 #= AF - Move,
          BF1 #= BF + Move },
        moves([jug(AID,AF1),jug(BID,BF1)|Jugs2]).

That's all. Notice that I am using DCG notation (see http://www.metalevel.at/dcg.html for more information) to describe lists of moves very naturally and conveniently.

Using iterative deepening lets you readily find the shortest solution:

?- length(Moves, _), phrase(moves([jug(a,0),jug(b,0)]), Moves).
Moves = [fill(a), from_to(a, b), empty(b), from_to(a, b), fill(a), from_to(a, b), empty(b),    from_to(a, b)] .

A bit more material about such puzzles and related search tasks is available at:

http://www.metalevel.at/tist/

I hope you find it useful.

All the best!
Markus

[Paulo Moura]

> On 16/11/2015, at 00:03, Markus Triska <tri...@logic.at> wrote:
>
> Hi Costa,
>
> thank you for sharing!
>
> I would like to suggest the following food for thought: With a slightly different state representation, you can shorten the code significantly, because it lets you treat the cases more uniformly.

> ...

Another way to simplify the code for this puzzles, which are examples of state space search, is to recognize the representation of a state space and a search method as two orthogonal abstractions and to define a framework for these problems where you can apply any search method to a given problem and use a given method to solve (or attempt to solve) any problem. Logtalk materializes these ideas in its "searching" example:

https://github.com/LogtalkDotOrg/logtalk3/blob/master/examples/searching/NOTES.md

For the particular case of the water jug puzzle see:

https://github.com/LogtalkDotOrg/logtalk3/blob/master/examples/searching/water_jug.lgt

This example also illustrates a nice programming principle: sometimes the best way to solve a specific problem is to first generalize it.

Cheers,

Paulo

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

Email: <mailto:pmo...@logtalk.org>
Web: <http://logtalk.org/>
-----------------------------------------------------------------