The "Water-jugs Problem"

"You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a tap that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?".
E. Rich & K. Knight, Artificial Intelligence, 2nd edition, McGraw-Hill, 1991

"Perfection is achieved not when there is nothing more to add, but when there is nothing more to take away." Antoine de Saint-Exupéry

Entry Point

water_jugs :-
    SmallCapacity = 3,
    LargeCapacity = 4,
    Reservoir is SmallCapacity + LargeCapacity + 1,
    volume( small, Capacities, SmallCapacity ),
    volume( large, Capacities, LargeCapacity ),
    volume( reservoir, Capacities, Reservoir ),
    volume( small, Start, 0 ),
    volume( large, Start, 0 ),
    volume( reservoir, Start, Reservoir ),
    volume( large, End, 2 ),
    water_jugs_solution( Start, Capacities, End, Solution ),
    phrase( narrative(Solution, Capacities, End), Chars ),
    put_chars( Chars ).

water_jugs_solution( Start, Capacities, End, Solution ) :-
    solve_jugs( [start(Start)], Capacities, [], End, Solution ).

solve_jugs( [Node|Nodes], Capacities, Visited, End, Solution ) :-
    node_state( Node, State ),
    ( State = End ->
        Solution = Node
    ; otherwise ->
        findall(
            Successor,
            successor(Node, Capacities, Visited, Successor),
            Successors
            ),
        append( Nodes, Successors, NewNodes ),
        solve_jugs( NewNodes, Capacities, [State|Visited], End, Solution )
    ).

successor( Node, Capacities, Visited, Successor ) :-
    node_state( Node, State ),
    Successor = node(Action,State1,Node),
    jug_transition( State, Capacities, Action, State1 ),
    \+ member( State1, Visited ).

jug_transition( State0, Capacities, empty_into(Source,Target), State1 ) :-
    volume( Source, State0, Content0 ),
    Content0 > 0,
    jug_permutation( Source, Target, Unused ),
    volume( Target, State0, Content1 ),
    volume( Target, Capacities, Capacity ),
    Content0 + Content1 =< Capacity,
    volume( Source, State1, 0 ),
    volume( Target, State1, Content2 ),
    Content2 is Content0 + Content1,
    volume( Unused, State0, Unchanged ),
    volume( Unused, State1, Unchanged ).
jug_transition( State0, Capacities, fill_from(Source,Target), State1 ) :-
    volume( Source, State0, Content0 ),
    Content0 > 0,
    jug_permutation( Source, Target, Unused ),
    volume( Target, State0, Content1 ),
    volume( Target, Capacities, Capacity ),
    Content1 < Capacity,
    Content0 + Content1 > Capacity,
    volume( Source, State1, Content2 ),
    volume( Target, State1, Capacity ),
    Content2 is Content0 + Content1 - Capacity,
    volume( Unused, State0, Unchanged ),
    volume( Unused, State1, Unchanged ).

Data Abstraction

volume( small, jugs(Small, _Large, _Reservoir), Small ).
volume( large, jugs(_Small, Large, _Reservoir), Large ).
volume( reservoir, jugs(_Small, _Large, Reservoir), Reservoir ).

jug_permutation( Source, Target, Unused ) :-
    select( Source, [small, large, reservoir], Residue ),
    select( Target, Residue, [Unused] ).

node_state( start(State), State ).
node_state( node(_Transition, State, _Predecessor), State ).

Definite Clause Grammar

narrative( start(Start), Capacities, End ) -->
    "Given three jugs with capacities of:", newline,
    literal_volumes( Capacities ),
    "To obtain the result:", newline,
    literal_volumes( End ),
    "Starting with:", newline,
    literal_volumes( Start ),
    "Do the following:", newline.
narrative( node(Transition, Result, Predecessor), Capacities, End ) -->
    narrative( Predecessor, Capacities, End ),
    literal_action( Transition, Result ).

literal_volumes( Volumes ) -->
    indent, literal( Volumes ), ";", newline.

literal_action( Transition, Result ) -->
    indent, "- ", literal( Transition ), " giving:", newline,
    indent, indent, literal( Result ), newline.

literal( empty_into(From,To) ) -->
    "Empty the ", literal( From ), " into the ",
    literal( To ).
literal( fill_from(From,To) ) -->
    "Fill the ", literal( To ), " from the ",
    literal( From ).
literal( jugs(Small,Large,Reservoir) ) -->
    literal_number( Small ), " gallons in the small jug, ",
    literal_number( Large ), " gallons in the large jug and ",
    literal_number( Reservoir ), " gallons in the reservoir".
literal( small ) --> "small jug".
literal( large ) --> "large jug".
literal( reservoir ) --> "reservoir".

literal_number( Number, Plus, Minus ) :-
    number( Number ),
    number_chars( Number, Chars ),
    append( Chars, Minus, Plus ).

indent --> "  ".

newline --> "
".

Utility Predicates

:- ensure_loaded( misc ).

Output

?- water_jugs.

Given three jugs with capacities of:
  3 gallons in the small jug, 4 gallons in the large jug and 8 gallons in the reservoir;
To obtain the result:
  0 gallons in the small jug, 2 gallons in the large jug and 6 gallons in the reservoir;
Starting with:
  0 gallons in the small jug, 0 gallons in the large jug and 8 gallons in the reservoir;
Do the following:
  - Fill the small jug from the reservoir giving:
    3 gallons in the small jug, 0 gallons in the large jug and 5 gallons in the reservoir
  - Empty the small jug into the large jug giving:
    0 gallons in the small jug, 3 gallons in the large jug and 5 gallons in the reservoir
  - Fill the small jug from the reservoir giving:
    3 gallons in the small jug, 3 gallons in the large jug and 2 gallons in the reservoir
  - Fill the large jug from the small jug giving:
    2 gallons in the small jug, 4 gallons in the large jug and 2 gallons in the reservoir
  - Empty the large jug into the reservoir giving:
    2 gallons in the small jug, 0 gallons in the large jug and 6 gallons in the reservoir
  - Empty the small jug into the large jug giving:
    0 gallons in the small jug, 2 gallons in the large jug and 6 gallons in the reservoir

yes

full source code

/* The "Water-jugs Problem - a solution in Prolog"
 *
 * This classic AI problem is described in Artificial Intelligence as follows: "You
 * are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring
 * markers on it. There is a tap that can be used to fill the jugs with water.
 * How can you get exactly 2 gallons of water into the 4-gallon jug?".
 * E. Rich & K. Knight, Artificial Intelligence, 2nd edition, McGraw-Hill, 1991
 *
 * This program implements an "environmentally responsible" solution to the water_jugs
 * problem: rather than filling and spilling, from an infinite water resource, we
 * conserve a finite initial charge with a third jug (reservoir).
 *
 * This approach is simpler than the traditional method, because there are only two
 * actions; and more flexible, because it can solve problems that are constrained by a
 * limited supply from the reservoir. To simulate the infinite version, we use a filled
 * reservoir with a capacity greater than the combined capacities of the jugs, so that the
 * reservoir can never be emptied. 
 *
 * "Perfection is achieved not when there is nothing more to add, but when
 *  there is nothing more to take away." Antoine de Saint-Exupéry 
 */

% Entry-point:

/* The water_jugs solution is derived by a simple, breadth-first, state-space
 * search; and is translated into a readable format by a DCG.
 */
water_jugs :-
    SmallCapacity = 3,
    LargeCapacity = 4,
    Reservoir is SmallCapacity + LargeCapacity + 1,
    volume( small, Capacities, SmallCapacity ),
    volume( large, Capacities, LargeCapacity ),
    volume( reservoir, Capacities, Reservoir ),
    volume( small, Start, 0 ),
    volume( large, Start, 0 ),
    volume( reservoir, Start, Reservoir ),
    volume( large, End, 2 ),
    water_jugs_solution( Start, Capacities, End, Solution ),
    phrase( narrative(Solution, Capacities, End), Chars ),
    put_chars( Chars ).

/* water_jugs_solution( +Start, +Capacities, +End, ?Solution ) holds when Solution is
 * the terminal 'node' in a state-space search, beginning with a 'start state' in
 * which the water-jugs have Capacities and contain the Start volumes.
 * The terminal node is reached when the water-jugs contain the End volumes.
 */
water_jugs_solution( Start, Capacities, End, Solution ) :-
    solve_jugs( [start(Start)], Capacities, [], End, Solution ).

/* solve_jugs( +Nodes, +Capacities, +Visited, +End, ?Solution ) holds when Solution is
 * the terminal 'node' in a state-space search - beginning with a first 'open'
 * node in Nodes, and terminating when the water-jugs contain the End volumes.
 * Capacities defines the capacities of the water-jugs while Visited is a list of
 * expanded ('closed') node states.
 * The 'breadth-first' operation of solve_jugs is due to the the 'existing'
 * Nodes being appended to the 'new' nodes. If the 'new' nodes were
 * appended to the 'existing' nodes, the operation would be 'depth-first'.
 */
solve_jugs( [Node|Nodes], Capacities, Visited, End, Solution ) :-
 node_state( Node, State ),
 ( State = End ->
  Solution = Node
 ; otherwise ->
  findall(
   Successor,
   successor(Node, Capacities, Visited, Successor),
   Successors
   ),
  append( Nodes, Successors, NewNodes ),
  solve_jugs( NewNodes, Capacities, [State|Visited], End, Solution )
 ).

/* successor( +Node, +Capacities, +Visited, ?Successor ) Successor is a successor of Node, for water-jugs with
 * Capacities, if there is a legal 'transition', from Node's state to Successor's state and Successor's state is not a member
 * of the Visited states.
 */
successor( Node, Capacities, Visited, Successor ) :-
 node_state( Node, State ),
 Successor = node(Action,State1,Node),
 jug_transition( State, Capacities, Action, State1 ),
 \+ member( State1, Visited ).

/* jug_transition( +State, +Capacities, ?Action, ?SuccessorState ) holds when
 * Action describes a valid transition from State to SuccessorState for
 * water-jugs with Capacities.
 *
 * There are 2 sorts of Action:
 *  
 * - empty_into(Source,Target) valid if Source is not already empty and the
 *   combined contents from Source and Target in State are not greater than the
 *   capacity of the Target jug. Source becomes empty in SuccessorState, while
 *   the Target jug acquires the combined contents from Source and Target in
 *   State. 
 * - fill_from(Source,Target) valid if Source is not already empty and the
 *   combined contents from Source and Target in State are greater than the
 *   capacity of the Target jug. The Target jug becomes full, in SuccessorState,
 *   while Source retains the difference between the combined contents of
 *   Source and Target, in State, and the capacity of the Target jug. 
 *
 * In either case the contents of the unused jug are unchanged.
 */
jug_transition( State0, Capacities, empty_into(Source,Target), State1 ) :-
 volume( Source, State0, Content0 ),
 Content0 > 0,
 jug_permutation( Source, Target, Unused ),
 volume( Target, State0, Content1 ),
 volume( Target, Capacities, Capacity ),
 Content0 + Content1 =< Capacity,
 volume( Source, State1, 0 ),
 volume( Target, State1, Content2 ),
 Content2 is Content0 + Content1,
 volume( Unused, State0, Unchanged ),
 volume( Unused, State1, Unchanged ).
jug_transition( State0, Capacities, fill_from(Source,Target), State1 ) :-
 volume( Source, State0, Content0 ),
 Content0 > 0,
 jug_permutation( Source, Target, Unused ),
 volume( Target, State0, Content1 ),
 volume( Target, Capacities, Capacity ),
 Content1 < Capacity,
 Content0 + Content1 > Capacity,
 volume( Source, State1, Content2 ),
 volume( Target, State1, Capacity ),
 Content2 is Content0 + Content1 - Capacity,
 volume( Unused, State0, Unchanged ),
 volume( Unused, State1, Unchanged ).

% Data Abstraction

/* volume( ?Jug, ?State, ?Volume ) holds when Jug ('large', 'small' or 'reservoir')
 * has Volume in State.
 */
volume( small, jugs(Small, _Large, _Reservoir), Small ).
volume( large, jugs(_Small, Large, _Reservoir), Large ).
volume( reservoir, jugs(_Small, _Large, Reservoir), Reservoir ).

/* jug_permutation( ?Source, ?Target, ?Unused ) holds when Source, Target and Unused
 * are a permutation of 'small', 'large' and 'reservoir'.
 */
jug_permutation( Source, Target, Unused ) :-
 select( Source, [small, large, reservoir], Residue ),
 select( Target, Residue, [Unused] ).

/* node_state( ?Node, ?State ) holds when the contents of the water-jugs at Node is
 * described by State.
 */
node_state( start(State), State ).
node_state( node(_Transition, State, _Predecessor), State ).

% Definite Clause Grammar

% DCG describing Water-jugs solutions: the 'narrative' grammar is 'head- recursive'
% because the 'nodes list' has the last node outermost.

narrative( start(Start), Capacities, End ) -->
 "Given three jugs with capacities of:", newline,
 literal_volumes( Capacities ),
 "To obtain the result:", newline,
 literal_volumes( End ),
 "Starting with:", newline,
 literal_volumes( Start ),
 "Do the following:", newline.
narrative( node(Transition, Result, Predecessor), Capacities, End ) -->
 narrative( Predecessor, Capacities, End ),
 literal_action( Transition, Result ).

literal_volumes( Volumes ) -->
 indent, literal( Volumes ), ";", newline.

literal_action( Transition, Result ) -->
 indent, "- ", literal( Transition ), " giving:", newline,
 indent, indent, literal( Result ), newline.

literal( empty_into(From,To) ) -->
 "Empty the ", literal( From ), " into the ",
 literal( To ).
literal( fill_from(From,To) ) -->
 "Fill the ", literal( To ), " from the ",
 literal( From ).
literal( jugs(Small,Large,Reservoir) ) -->
 literal_number( Small ), " gallons in the small jug, ",
 literal_number( Large ), " gallons in the large jug and ",
 literal_number( Reservoir ), " gallons in the reservoir".
literal( small ) --> "small jug".
literal( large ) --> "large jug".
literal( reservoir ) --> "reservoir".

literal_number( Number, Plus, Minus ) :-
 number( Number ),
 number_chars( Number, Chars ),
 append( Chars, Minus, Plus ).

indent --> "  ".

newline --> "
".

% Utility Predicates

:- ensure_loaded( misc ).