title: 2-Water jug in prolog
body: <p>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.</p>
  
  <p>I wrote programs for this problem in C++ using both bfs and dfs: <a href="http://kartikkukreja.wordpress.com/2013/10/11/water-jug-problem/" rel="nofollow">http://kartikkukreja.wordpress.com/2013/10/11/water-jug-problem/</a>. Now, I'm trying to solve the problem in prolog. I'm completely new to the language and my code doesn't terminate. </p>
  
  <p>Here's the code I have so far:</p>
  
  <pre><code>% 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 &lt; 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 &lt; 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 &gt; 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 &gt; 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 &gt;= 4,
  X &lt; 4,
  Y &gt; 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 &gt;=3,
  X &gt; 0,
  Y &lt; 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 =&lt; 4,
  Y &gt; 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 =&lt; 3,
  X &gt; 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].
  </code></pre>
  
  <p>Any help is appreciated.</p>