Solving Decanting Problems by Graph Theory
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.[more]
This Demonstration shows how graph theory can solve the problem; it focuses on the case of three jugs with decreasing integer capacities , , , 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.[less]
By viewing the possible states as vertices in a graph, with directed edges for legal moves from state to state, the decanting problem is simply that of finding a path (better, the shortest path) from the initial state to the final. Note that any edge must go to a state that has at least one jug that is empty or full.
Barycentric coordinates (also called trilinear coordinates) allow the states to be viewed as discrete points in an equilateral triangle. Edges in the graph can travel in three directions parallel to the sides of the triangle, and must always travel to the end of the line chosen. In this representation, states on the triangle's boundary (red) have at least one empty jug; states on the boundary of the polygon containing the graph, but not on the triangle's boundary, are states with at least one full jug and no empty jug (these are green); and states in the interior of the polygon are states with neither an empty nor a full jug. The smaller blue vertices are not reachable from the start position.
Snapshot 1: The interesting case of . The hardest problem here is to go from to .
Snapshot 2: The case of and passage from to . In this example, some boundary points are unreachable from .