The Water Jugs Problem: Difference between revisions

From This Prolog Life
Jump to navigation Jump to search
m (Revert "Three Glasses" link to HTTP.)
(24 intermediate revisions by the same user not shown)
Line 3: Line 3:


<blockquote>
<blockquote>
"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?".
&ldquo;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?&rdquo;.


<cite>[http://www.amazon.co.uk/exec/obidos/ASIN/0070522634/bindingtimeli-21 E. Rich & K. Knight, Artificial Intelligence, 2nd edition, McGraw-Hill, 1991]</cite>
<cite>[http://amzn.to/2J3Dge3 E. Rich & K. Knight, Artificial Intelligence, 2nd edition, McGraw-Hill, 1991]</cite>
</blockquote>
</blockquote>


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 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; it is more flexible than the traditional method, because it can solve problems that are constrained by a limited supply from the reservoir.
This approach is simpler than the traditional method because there are only two actions. It is more flexible than the traditional method because it can solve problems that are constrained by a limited supply from the reservoir<ref>For example, the "[http://www.cut-the-knot.org/water.shtml Three Glass Puzzle]" where the jugs have capacities of 8 (filled), 5 and 3 and the goal is to get two equal volumes (4).</ref>.


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.
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.


<blockquote>
<blockquote>
"Perfection is achieved not when there is nothing more to add, but when there is nothing more to take away."
&ldquo;Perfection is achieved not when there is nothing more to add, but when there is nothing more to take away.&rdquo;


<cite>[http://en.wikiquote.org/wiki/Antoine_de_Saint-Exupery Antoine de Saint-Exup&#233;ry]</cite>
<cite>[https://en.wikiquote.org/wiki/Antoine_de_Saint_Exup%C3%A9ry Antoine de Saint-Exup&#233;ry]</cite>
</blockquote>
</blockquote>


Line 24: Line 24:
====water_jugs====
====water_jugs====


is the entry point. The solution is derived by a simple, breadth-first, state-space search; and translated into a readable format by a DCG.
is the entry point. The solution is derived by a simple, breadth-first, state-space search, and translated into a readable format by a DCG.


<syntaxhighlight lang="prolog">water_jugs :-
<pre class="prolog">water_jugs :-
    SmallCapacity = 3,
    SmallCapacity = 3,
    LargeCapacity = 4,
    LargeCapacity = 4,
    Reservoir is SmallCapacity + LargeCapacity + 1,
    Reservoir is SmallCapacity + LargeCapacity + 1,
    volume( small, Capacities, SmallCapacity ),
    volume( small, Capacities, SmallCapacity ),
    volume( large, Capacities, LargeCapacity ),
    volume( large, Capacities, LargeCapacity ),
    volume( reservoir, Capacities, Reservoir ),
    volume( reservoir, Capacities, Reservoir ),
    volume( small, Start, 0 ),
    volume( small, Start, 0 ),
    volume( large, Start, 0 ),
    volume( large, Start, 0 ),
    volume( reservoir, Start, Reservoir ),
    volume( reservoir, Start, Reservoir ),
    volume( large, End, 2 ),
    volume( large, End, 2 ),
    water_jugs_solution( Start, Capacities, End, Solution ),
    water_jugs_solution( Start, Capacities, End, Solution ),
    phrase( narrative(Solution, Capacities, End), Chars ),
    phrase( narrative(Solution, Capacities, End), Chars ),
    put_chars( Chars ).</syntaxhighlight>
    put_chars( Chars ).</pre>


====water_jugs_solution( +Start, +Capacities, +End, ?Solution )====
====water_jugs_solution( +Start, +Capacities, +End, ?Solution )====


holds when <var>Solution</var> is the terminal 'node' in a state-space search - beginning with a 'start state' in which the water-jugs have <var>Capacities</var> and contain the <var>Start</var> volumes. The terminal node is reached when the water-jugs contain the <var>End</var> volumes.
holds when <var>Solution</var> is the terminal state in a state-space search that begins with an initial state, in which the water-jugs have <var>Capacities</var> and contain the <var>Start</var> volumes, and ends when the water-jugs contain the <var>End</var> volumes.


<syntaxhighlight lang="prolog">
<pre class="prolog">
water_jugs_solution( Start, Capacities, End, Solution ) :-
water_jugs_solution( Start, Capacities, End, Solution ) :-
    solve_jugs( [start(Start)], Capacities, [], End, Solution ).
    solve_jugs( [start(Start)], Capacities, [], End, Solution ).
</syntaxhighlight>
</pre>


====solve_jugs( +Nodes, +Capacities, +Visited, +End, ?Solution )====
====solve_jugs( +Nodes, +Capacities, +Visited, +End, ?Solution )====


holds when <var>Solution</var> is the terminal 'node' in a state-space search, beginning with a first 'open' node in <var>Nodes</var>, and terminating when the water-jugs contain the <var>End</var> volumes. <var>Capacities</var> define the capacities of the water-jugs, while <var>Visited</var> is a list of expanded ('closed') node states.
holds when <var>Solution</var> is the terminal node in a state-space search, beginning with a first open node in <var>Nodes</var>, and terminating when the water-jugs contain the <var>End</var> volumes. <var>Capacities</var> define the capacities of the water-jugs while <var>Visited</var> is a list of expanded (closed) node states.


The 'breadth-first' operation of solve_jugs is due to the 'existing' <var> Nodes</var> being appended to the 'new' nodes. (If the 'new' nodes were appended to the 'existing' nodes, the operation would be 'depth-first'.)
The breadth-first operation of solve_jugs is due to the existing <var>Nodes</var> being appended to the new nodes. (If the new nodes were appended to the existing nodes, the operation would be depth-first.)


<syntaxhighlight lang="prolog">
<pre class="prolog">
solve_jugs( [Node|Nodes], Capacities, Visited, End, Solution ) :-
solve_jugs( [Node|Nodes], Capacities, Visited, End, Solution ) :-
    node_state( Node, State ),
    node_state( Node, State ),
    ( State = End ->
    ( State = End ->
        Solution = Node
        Solution = Node
    ; otherwise ->
    ; otherwise ->
        findall(
        findall(
            Successor,
            Successor,
            successor(Node, Capacities, Visited, Successor),
            successor(Node, Capacities, Visited, Successor),
            Successors
            Successors
            ),
            ),
        append( Nodes, Successors, NewNodes ),
        append( Nodes, Successors, NewNodes ),
        solve_jugs( NewNodes, Capacities, [State|Visited], End, Solution )
        solve_jugs( NewNodes, Capacities, [State|Visited], End, Solution )
    ).
    ).
</syntaxhighlight>
</pre>


====successor( +Node, +Capacities, +Visited, ?Successor )====
====successor( +Node, +Capacities, +Visited, ?Successor )====


<var>Successor</var> is a successor of <var>Node</var>, for water-jugs with <var>Capacities</var>, if there is a legal 'transition' from <var> Node</var>'s state to <var>Successor</var>'s state, and <var>Successor</var>'s state is not a member of the <var>Visited</var> states.
<var>Successor</var> is a successor of <var>Node</var>, for water-jugs with <var>Capacities</var>, if there is a legal transition from <var>Node</var>'s state to <var>Successor</var>'s state and <var>Successor</var>'s state is not a member of the <var>Visited</var> states.


<syntaxhighlight lang="prolog">
<pre class="prolog">
successor( Node, Capacities, Visited, Successor ) :-
successor( Node, Capacities, Visited, Successor ) :-
    node_state( Node, State ),
    node_state( Node, State ),
    Successor = node(Action,State1,Node),
    Successor = node(Action,State1,Node),
    jug_transition( State, Capacities, Action, State1 ),
    jug_transition( State, Capacities, Action, State1 ),
    \+ member( State1, Visited ).
    \+ member( State1, Visited ).
</syntaxhighlight>
</pre>


===Transition Rules===
===Transition Rules===
Line 92: Line 92:
There are two sorts of <var>Action</var>:
There are two sorts of <var>Action</var>:


* <code>empty_into(Source,Target)</code> valid if ''Source'' is not already empty and the combined contents from ''Source'' and ''Target'', (in <var>State</var>), are not greater than the capacity of the ''Target'' jug. In <var>SuccessorState</var>: ''Source'' becomes empty, while the ''Target'' jug acquires the combined contents of ''Source'' and ''Target'' in <var>State</var>.
* <code>empty_into(Source,Target)</code> valid if ''Source'' is not already empty and the combined contents from ''Source'' and ''Target'', in <var>State</var>, are not greater than the capacity of the ''Target'' jug. The ''Source'' jug becomes empty in <var>SuccessorState</var> while the ''Target'' jug acquires the combined contents of ''Source'' and ''Target'' in <var>State</var>.
* <code>fill_from(Source,Target)</code> valid if ''Source'' is not already empty and the combined contents from ''Source'' and ''Target'', (in <var>State</var>), are greater than the capacity of the ''Target'' jug. In <var>SuccessorState</var>: the ''Target'' jug becomes full, while ''Source'' retains the difference between the combined contents of ''Source'' and ''Target'', in <var>State</var>, and the capacity of the ''Target'' jug.
* <code>fill_from(Source,Target)</code> valid if ''Source'' is not already empty, and the combined contents from ''Source'' and ''Target'', in <var>State</var>, are greater than the capacity of the ''Target'' jug. The ''Target'' jug becomes full in <var>SuccessorState</var>, while ''Source'' retains the excess of the combined contents of ''Source'' and ''Target'' in <var>State</var>, over the capacity of the ''Target'' jug.


In either case, the contents of the unused jug are unchanged.
In either case, the contents of the unused jug are unchanged.


<syntaxhighlight lang="prolog">jug_transition( State0, Capacities, empty_into(Source,Target), State1 ) :-
<pre class="prolog">jug_transition( State0, Capacities, Action, State1 ) :-
    volume( Source, State0, Content0 ),
    volume( Source, State0, SourceContents ),
    Content0 > 0,
    SourceContents > 0,
    jug_permutation( Source, Target, Unused ),
    jug_permutation( Source, Target, Unused ),
    volume( Target, State0, Content1 ),
    volume( Target, State0, TargetContents ),
    volume( Target, Capacities, Capacity ),
    volume( Target, Capacities, TargetCapacity ),
    Content0 + Content1 =< Capacity,
    volume( Unused, State0, Unchanged ),
    volume( Source, State1, 0 ),
    volume( Unused, State1, Unchanged ),
    volume( Target, State1, Content2 ),
    CombinedContents is SourceContents + TargetContents,
    Content2 is Content0 + Content1,
    ( CombinedContents =< TargetCapacity ->
    volume( Unused, State0, Unchanged ),
        Action = empty_into(Source,Target),
    volume( Unused, State1, Unchanged ).
        NewSourceContents = 0,
jug_transition( State0, Capacities, fill_from(Source,Target), State1 ) :-
        NewTargetContents = CombinedContents
    volume( Source, State0, Content0 ),
    ; CombinedContents > TargetCapacity ->
    Content0 > 0,
        Action = fill_from(Source,Target),
    jug_permutation( Source, Target, Unused ),
        NewSourceContents is CombinedContents-TargetCapacity,
    volume( Target, State0, Content1 ),
        NewTargetContents = TargetCapacity
    volume( Target, Capacities, Capacity ),
    ),  
    Content1 < Capacity,
    volume( Source, State1, NewSourceContents ),
    Content0 + Content1 > Capacity,
    volume( Target, State1, NewTargetContents ).</pre>
    volume( Source, State1, Content2 ),
    volume( Target, State1, Capacity ),
    Content2 is Content0 + Content1 - Capacity,
    volume( Unused, State0, Unchanged ),
    volume( Unused, State1, Unchanged ).</syntaxhighlight>


==Data Abstraction==
==Data Abstraction==
Line 127: Line 122:
====volume( ?Jug, ?State, ?Volume )====
====volume( ?Jug, ?State, ?Volume )====


holds when <var>Jug</var> ('large', 'small' or 'reservoir') has <var>Volume</var> in <var>State</var>.
holds when <var>Jug</var> (large, small or reservoir) has <var>Volume</var> in <var>State</var>.


<syntaxhighlight lang="prolog">
<pre class="prolog">
volume( small, jugs(Small, _Large, _Reservoir), Small ).
volume( small, jugs(Small, _Large, _Reservoir), Small ).
volume( large, jugs(_Small, Large, _Reservoir), Large ).
volume( large, jugs(_Small, Large, _Reservoir), Large ).
volume( reservoir, jugs(_Small, _Large, Reservoir), Reservoir ).
volume( reservoir, jugs(_Small, _Large, Reservoir), Reservoir ).
</syntaxhighlight>
</pre>


====jug_permutation( ?Source, ?Target, ?Unused )====
====jug_permutation( ?Source, ?Target, ?Unused )====


holds when <var>Source</var>, <var>Target</var> and <var>Unused</var> are a permutation of 'small', 'large' and 'reservoir'.
holds when <var>Source</var>, <var>Target</var> and <var>Unused</var> are a permutation of <code>small</code>, <code>large</code> and <code>reservoir</code>.


<syntaxhighlight lang="prolog">
<pre class="prolog">
jug_permutation( Source, Target, Unused ) :-
jug_permutation( Source, Target, Unused ) :-
    select( Source, [small, large, reservoir], Residue ),
    select( Source, [small, large, reservoir], Residue ),
    select( Target, Residue, [Unused] ).
    select( Target, Residue, [Unused] ).
</syntaxhighlight>
</pre>


====node_state( ?Node, ?State )====
====node_state( ?Node, ?State )====
Line 149: Line 144:
holds when the contents of the water-jugs at <var>Node</var> are described by <var>State</var>.
holds when the contents of the water-jugs at <var>Node</var> are described by <var>State</var>.


<syntaxhighlight lang="prolog">
<pre class="prolog">
node_state( start(State), State ).
node_state( start(State), State ).
node_state( node(_Transition, State, _Predecessor), State ).
node_state( node(_Transition, State, _Predecessor), State ).
</syntaxhighlight>
</pre>


==Definite Clause Grammar==
==Definite Clause Grammar==


====narrative(+Node, +Capacities, +End )//====
====narrative( +Solution, +Capacities, +End )/====


is a DCG presenting water-jugs solutions in a readable format. The grammar is head-recursive, because the 'nodes list' describing the solution has the last node outermost.
is a DCG presenting the water-jugs <var>Solution</var> in a readable format. The grammar is head-recursive because the <var>Solution</var> has the last node outermost.


<syntaxhighlight lang="prolog">
<pre class="prolog">
narrative( start(Start), Capacities, End ) -->
narrative( start(Start), Capacities, End ) -->
    "Given three jugs with capacities of:", newline,
    "Given three jugs with capacities of:", newline,
    literal_volumes( Capacities ),
    literal_volumes( Capacities ),
    "To obtain the result:", newline,
    "To obtain the result:", newline,
    literal_volumes( End ),
    literal_volumes( End ),
    "Starting with:", newline,
    "Starting with:", newline,
    literal_volumes( Start ),
    literal_volumes( Start ),
    "Do the following:", newline.
    "Do the following:", newline.
narrative( node(Transition, Result, Predecessor), Capacities, End ) -->
narrative( node(Transition, Result, Predecessor), Capacities, End ) -->
    narrative( Predecessor, Capacities, End ),
    narrative( Predecessor, Capacities, End ),
    literal_action( Transition, Result ).
    literal_action( Transition, Result ).
   
   
literal_volumes( Volumes ) -->
literal_volumes( Volumes ) -->
    indent, literal( Volumes ), ";", newline.
    indent, literal( Volumes ), ";", newline.
   
   
literal_action( Transition, Result ) -->
literal_action( Transition, Result ) -->
    indent, "- ", literal( Transition ), " giving:", newline,
    indent, "- ", literal( Transition ), " giving:", newline,
    indent, indent, literal( Result ), newline.
    indent, indent, literal( Result ), newline.
   
   
literal( empty_into(From,To) ) -->
literal( empty_into(From,To) ) -->
    "Empty the ", literal( From ), " into the ",
    "Empty the ", literal( From ), " into the ",
    literal( To ).
    literal( To ).
literal( fill_from(From,To) ) -->
literal( fill_from(From,To) ) -->
    "Fill the ", literal( To ), " from the ",
    "Fill the ", literal( To ), " from the ",
    literal( From ).
    literal( From ).
literal( jugs(Small,Large,Reservoir) ) -->
literal( jugs(Small,Large,Reservoir) ) -->
    literal_number( Small ), " gallons in the small jug, ",
    literal_number( Small ), " gallons in the small jug, ",
    literal_number( Large ), " gallons in the large jug and ",
    literal_number( Large ), " gallons in the large jug and ",
    literal_number( Reservoir ), " gallons in the reservoir".
    literal_number( Reservoir ), " gallons in the reservoir".
literal( small ) --> "small jug".
literal( small ) --> "small jug".
literal( large ) --> "large jug".
literal( large ) --> "large jug".
Line 195: Line 190:
   
   
literal_number( Number, Plus, Minus ) :-
literal_number( Number, Plus, Minus ) :-
    number( Number ),
    number( Number ),
    number_chars( Number, Chars ),
    name( Number, Chars ),
    append( Chars, Minus, Plus ).
    append( Chars, Minus, Plus ).
   
   
indent --> "  ".
indent --> "  ".
Line 203: Line 198:
newline --> "
newline --> "
  ".
  ".
</syntaxhighlight>
</pre>


==Utility Predicates==
==Utility Predicates==


Load a small library of [http://www.binding-time.co.uk/misc.html puzzle utilities].
Load a small library of [[Puzzle Utilities]].


<syntaxhighlight lang="prolog">
<pre class="prolog">
:- ensure_loaded( misc ).
:- ensure_loaded( misc ).
</syntaxhighlight>
</pre>


The code is available as plain text [http://www.binding-time.co.uk/download/water_jugs.txt here].
The code is available as plain text [https://binding-time.co.uk/download/water_jugs.txt here].


==Output==
==Output==
Line 245: Line 240:
</pre>
</pre>
</div>
</div>
=====Footnote=====
<references/>

Revision as of 17:30, 9 December 2018

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. It is more flexible than the traditional method because it can solve problems that are constrained by a limited supply from the reservoir[1].

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

Solution

water_jugs

is the entry point. The solution is derived by a simple, breadth-first, state-space search, and 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 state in a state-space search that begins with an initial state, in which the water-jugs have Capacities and contain the Start volumes, and ends 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 define 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 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 ).

Transition Rules

jug_transition( +State, +Capacities, ?Action, ?SuccessorState )

holds when Action describes a valid transition, from State to SuccessorState, for water-jugs with Capacities.

There are two 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. The Source jug becomes empty in SuccessorState while the Target jug acquires the combined contents of 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 excess of the combined contents of Source and Target in State, over the capacity of the Target jug.

In either case, the contents of the unused jug are unchanged.

jug_transition( State0, Capacities, Action, State1 ) :-
    volume( Source, State0, SourceContents ),
    SourceContents > 0,
    jug_permutation( Source, Target, Unused ),
    volume( Target, State0, TargetContents ),
    volume( Target, Capacities, TargetCapacity ),
    volume( Unused, State0, Unchanged ),
    volume( Unused, State1, Unchanged ),
    CombinedContents is SourceContents + TargetContents,
    ( CombinedContents =< TargetCapacity ->
        Action = empty_into(Source,Target),
        NewSourceContents = 0,
        NewTargetContents = CombinedContents
    ; CombinedContents > TargetCapacity ->
        Action = fill_from(Source,Target),
        NewSourceContents is CombinedContents-TargetCapacity,
        NewTargetContents = TargetCapacity
    ),    
    volume( Source, State1, NewSourceContents ),
    volume( Target, State1, NewTargetContents ).

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 are described by State.

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

Definite Clause Grammar

narrative( +Solution, +Capacities, +End )/

is a DCG presenting the water-jugs Solution in a readable format. The grammar is head-recursive because the Solution 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 ),
    name( Number, Chars ),
    append( Chars, Minus, Plus ).
 
indent --> "  ".
 
newline --> "
 ".

Utility Predicates

Load a small library of Puzzle Utilities.

:- ensure_loaded( misc ).

The code is available as plain text here.

Output

The output of the program is:

?- 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
Footnote
  1. For example, the "Three Glass Puzzle" where the jugs have capacities of 8 (filled), 5 and 3 and the goal is to get two equal volumes (4).