I'm trying to solve the 2-water jug problem in swi-prolog: Given 2 jugs of capacities 4 and 3 gallons respectively, I want to find the steps to obtain 2 gallons in jug of capacity 4 and 0 in the other.
I wrote programs for this problem in C++ using both bfs and dfs: http://kartikkukreja.wordpress.com/2013/10/11/water-jug-problem/. Now, I'm trying to solve the problem in prolog. I'm completely new to the language and my code doesn't terminate.
Here's the code I have so far:
% state(0, 0) is the initial state
% state(2, 0) is the goal state
% Jugs 1 and 2 have capacities 4 and 3 respectively
% P is a path to the goal state
% C is the list of visited states
solution(P) :-
path(0, 0, [state(0, 0)], P).
path(2, 0, [state(2, 0)|_], _).
path(0, 2, C, P) :-
not(member(state(2, 0), C)),
path(2, 0, [state(2, 0)|C], R),
P = ['Pour 2 gallons from 3-Gallon jug to 4-gallon.'|R].
path(X, Y, C, P) :-
X < 4,
not(member(state(4, Y), C)),
path(4, Y, [state(4, Y)|C], R),
P = ['Fill the 4-Gallon Jug.'|R].
path(X, Y, C, P) :-
Y < 3,
not(member(state(X, 3), C)),
path(X, 3, [state(X, 3)|C], R),
P = ['Fill the 3-Gallon Jug.'|R].
path(X, Y, C, P) :-
X > 0,
not(member(state(0, Y), C)),
path(0, Y, [state(0, Y)|C], R),
P = ['Empty the 4-Gallon jug on ground.'|R].
path(X, Y, C, P) :-
Y > 0,
not(member(state(X, 0), C)),
path(X, 0, [state(X, 0)|C], R),
P = ['Empty the 3-Gallon jug on ground.'|R].
path(X, Y, C, P) :-
X + Y >= 4,
X < 4,
Y > 0,
NEW_Y = Y - (4 - X),
not(member(state(4, NEW_Y), C)),
path(4, NEW_Y, [state(4, NEW_Y)|C], R),
P = ['Pour water from 3-Gallon jug to 4-gallon until it is full.'|R].
path(X, Y, C, P) :-
X + Y >=3,
X > 0,
Y < 3,
NEW_X = X - (3 - Y),
not(member(state(NEW_X, 3), C)),
path(NEW_X, 3, [state(NEW_X, 3)|C], R),
P = ['Pour water from 4-Gallon jug to 3-gallon until it is full.'|R].
path(X, Y, C, P) :-
X + Y =< 4,
Y > 0,
NEW_X = X + Y,
not(member(state(NEW_X, 0), C)),
path(NEW_X, 0, [state(NEW_X, 0)|C], R),
P = ['Pour all the water from 3-Gallon jug to 4-gallon.'|R].
path(X, Y, C, P) :-
X + Y =< 3,
X > 0,
NEW_Y = X + Y,
not(member(state(0, NEW_Y), C)),
path(0, NEW_Y, [state(0, NEW_Y)|C], R),
P = ['Pour all the water from 4-Gallon jug to 3-gallon.'|R].
Any help is appreciated.
The 'equal' operator in Prolog doesn't perform arithmetic, but unifies its two arguments. Try (for instance) to replace this
NEW_Y = Y - (4 - X)
with
NEW_Y is Y - (4 - X)
OT: also Prolog, like any other language, benefits from code factoring: most path/4 rules expose the same pattern, thus the code could be more clean with an helper predicate: again, for instance
path(0, 2, C, P) :-
not(member(state(2, 0), C)),
path(2, 0, [state(2, 0)|C], R),
P = ['Pour 2 gallons from 3-Gallon jug to 4-gallon.'|R].
could be
path(0, 2, C, ['Pour 2 gallons from 3-Gallon jug to 4-gallon.'|R]) :-
upd_path(2, 0, C, R).
given
upd_path(X, Y, C, R).
not(member(state(X, Y), C)),
path(X, Y, [state(X, Y)|C], R).
edit: another OT hint: use memberchk/2 instead of member/2. It's more efficient and could make easier to trace the execution, being deterministic.
edit Also, the base case of recursion doesn't close the descriptions' list: try
path(2, 0, [state(2, 0)|_], []).