Search code examples
prologwater-jug-problem

Jug Water Problem using DFS and State Space in Prolog


I'm solving the water jug problem using state space and dfs,jug 1 have capacity of 4,jug 2 have capacity of 3,show the path to make jug 2 have 2 in it

% Water Jug problem using DFS in Prolog

% Define the initial state
start(jug(0,0)).

% Define the goal state
goal(jug(_,2)).

% Define the actions that can be taken
action(fill1, jug(_,Y), jug(4,Y)).
action(fill2, jug(X,_), jug(X,3)).
action(empty1, jug(_,Y), jug(0,Y)).
action(empty2, jug(X,_), jug(X,0)).
action(pour1to2, jug(X,Y), jug(X1,Y1)) :- X > 0, Y < 3, X1 is 0, Y1 is min(3, X + Y).
action(pour2to1, jug(X,Y), jug(X1,Y1)) :- Y > 0, X < 4, Y1 is 0, X1 is min(4, X + Y).

% Define the DFS algorithm
dfs(State, [], _) :- goal(State).

dfs(State, [Action|Actions], Visited) :-
    action(Action, State, State1),
    State1 \= State,
    \+ member(State1, Visited),
    dfs(State1, Actions, [State1|Visited]).`

To run the program
start(State), dfs(State, Actions, [State]).

I have tried to print what inside

fill1
fill2
empty1
fill1
empty2
pour2to1
fill1
fill2
fill1
empty1
empty2
pour2to1
empty1
pour1to2
empty2
empty1

... but it make no sense,The program always return false. Could anyone help me to find what is wrong with it?


Solution

  • change the action pour2to1 and pour1to 2 to

    action(pour1to2, jug(X,Y), jug(X1,Y1)) :-
    X > 0, Y < 3, Y1 is X + Y, X1 is max(0, Y1 - 3). 
    action(pour2to1, jug(X,Y), jug(X1,Y1)) :- 
    Y > 0, X < 4, X1 is X + Y, Y1 is max(0, X1 - 4).
    

    because the old code have wrong logic, X1 or Y1 always 0 when pouring to another