Solving Decanting Problems by Graph Theory

A capacity

14

B

13

C

9

total water in jugs

14

show hardest case for specified capacities

Jug capacities are (14 13 9); start is (14 0 0); finish is (0 13 1)

Solution:

(14 0 0)  (1 13 0)  (0 13 1)

	start
	finish
	unreachable state

	reachable states:
	some jugs are empty
	no empty jug; some full jugs

Classic decanting problems present some jugs with water and ask for a method to get from one state to another by pouring water from one jug to another. There is no source or sink; all water must remain in the system.

This Demonstration shows how graph theory can solve the problem; it focuses on the case of three jugs with decreasing integer capacities

A

,

B

,

C

, where each jug in the initial and final states has an integer volume of water. A legal pour is one that empties the source jug or fills the target. Selecting the "hardest case" box causes the start and finish to correspond to a path that is the longest for the particular capacities selected. The total water in the initial state of the three jugs must be set, as that defines the graph. You set the initial and final states by moving the purple and yellow disks, respectively. The final position is always moved to the nearest reachable state; those states are shown by large red or green disks. The smaller red and green disks and the small blue disks are states that are unreachable from the initial state.

The graphic shows a graph that represents the states, with the shortest path from the initial to final state given as a sequence of arrows.