# Solving Decanting Problems by Graph Theory

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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]
Contributed by: Stan Wagon (March 2015)

Macalester College

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

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 .

## Permanent Citation