                                waterjug.pro


/* This is the jug problem using simple depth-first search of a graph.
   The modified water-jug problem is as follows:
   Jug A holds 4 liters, and jug B holds 3 liters.
   There is a pump which can be    used to fill either
   jug.  How can you get exactly 2 liters of water into the 4-liter jug? 
*/
?-op(100,yfx,':').  /* define : as a left-associative operator */

/* The major predicate is
  solve(Current_state, Goal_state, Traversed_path, Solution_path).
   where Traversed_path is a list of pourings made so far.     */

solve(Goal, Goal, Path, Path).  /* If the current state is the
          goal state, then output the path to the 4th argument */

solve(Current, Goal, Path, Solution) :-
      edge(Step, Current, New),  /* 'Step' involves either pouring
                                     or filling up from pump */
      not marked(solve(New, Goal, _, _)),  /* Graph search requires
                    checking whether we've searched this node before */
      solve(New, Goal, Path:Step, Solution). /* Use recursion to do
                  depth-first search.  On failure, backup to 'pour'. */

edge(fill_up_a, A:B, S:B) :- size(a,S), A<S.
edge(fill_up_b, A:B, A:S) :- size(b,S), B<S.
edge(pour_a_down_drain, A:B , 0:B).
edge(pour_b_down_drain, A:B , A:0).
edge(pour_a_into_b, A:B, C:D) :-
      size(b,S), A>0, B<S, T is A+B,
      (T>=S, C is T-S, D=S ; T<S, C=0, D=T) .
edge(pour_b_into_a, A:B, C:D) :-
       size(a,S), B>0, A<S, T is A+B,
       (T>=S, D is T-S, C=S ; T<S, C=T, D=0) .

/*Check whether a node was already searched.  The rule
    marked(X) :- asserta((marked(X):- !)), fail.
causes a node to be marked if it was not marked before, and fails.
The next time it checks this node, it will succeed since that node
had been asserted to be marked.  Reset_marked permits the
depth-first search to be done several times.   */

reset_marked :- retractall(marked(_)),
      asserta( (marked(X) :- asserta((marked(X):- !)), fail) ).

mod_jug_problem(X,Y,Z) :- reset_marked, solve(X,Y,start,Z).

size(a,4).
size(b,3).
?- mod_jug_problem(0:0, 2:B, Solution).

?-retractall(size(_ , _)).

size(a,5).
size(b,2).

?-mod_jug_problem(5:0, A:1, Solution).

