Problem Description

Here's a Delphi version of a classic Water Jug problem.   One version goes like this:

 Two friends who have an eight-quart jug of water wish to share it evenly. They also have two empty jars, one holding five quarts, the other three. How can they each measure exactly 4 quarts of water?

(Solution takes 7 pour operations.)

Background & Techniques

Viewer Charles Doumar wrote the original program and introduced me to the Water Jug problem as a test of our TGraphSearch unit which incorporates the Dijkstra Shortest Path Search algorithm.  Alex Bogomolny's  Cut the Knot site has a good Water Jug problem page some of the history and theory. 

Because this version is designed as a test of shortest path searching, we allow any combination of starting values with  any other achievable combination as a goal.   The solver initially knows the capacity and amount of liquid contained in each jug and is searching for a given goal configuration.  The jugs have no intermediate measure of the amount contained so pouring transfers the smaller of  (1.) the amount of water in the "From" jug and (2.) the available unused capacity of the "To" jug.  And, of course, the fewer moves the better.  

Users may set up any 3 or 4 jug puzzle and try to solve it by clicking on jug images.    When you're ready to give up, as I frequently am, the "Show me" button will compute the necessary moves.   

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download the executable version of the program.

Programmer's Notes

The program uses procedure Dijkstra from the TGraphSearch class to search for solutions.    At the top of the form the user selects the number of jugs, 3 or 4, the capacity for each jug and the total amount of water to be distributed across the jugs.   

When any of these amounts change, a call to JarBtnClick  generates nodes for all possible ways to distribute the specified water amount across the available jugs.    The TComboset Combos class  is then used to generate all pairs of jugs from the available number.  If the first of the pair could pour an amount >0 into the 2nd of the pair, a graph edge is generated connecting the two.   

Once the nodes and edges have been built, TComboboxes,  StartCB and EndCb,  are loaded with the available nodes from which the user will select starting and ending jar configurations.  When the start configuration is changed in StartCB, an attempt is made to evaluate the result for all goal nodes in EndCB.  For four jar cases with large capacities, this process might take a long time, so a "Stop" button is provided to abort the process. The results of the solution search are used to pre-calculate "Unsolvable" goals which are flagged in the end goal text and "best solution" move counts, which are retained as objects with each goal entry and displayed when the "Show best solutions" checkbox is checked.  The best goal count is also used to modify the message given when a solution is found manually  ("Congratulations!" or "Good, but it can be solved in fewer moves")    

User play is controlled by an OnDrawCell exit in a TStringGrid which draws scaled images of the jugs (they look more like beakers, but oh well).   Users click on the images define from and to jugs and the move is displayed in a Tmemo display area.   

Whew!  700 lines of code is enough to put the program in the Advanced category. 

Running/Exploring the Program 

• Download source (Requires DFF Library Source DFFLibV02 or later)
• Download DFF Library Source  (Current version DFFLibV11 )
• Download  executable

Suggestions for Further Explorations

	The "jug" images could be drawn to look more like jugs or at least like jars instead of beakers
	The solution pre-calculation is a little messy.  Usually it is fast enough to be unnoticeable. But 4 jugs and large capacities and water volume can take a minute of more.  Currently a button allows interruption, but a better solution would use the OnIdle exit or a separate thread to fill in the possible solution info in the background.