The Three Glass Riddle as a Graph

The solution to this problem involves a little bit of abstract thinking. When I use this problem in classrooms, a common first idea is to model each container as a node in the graph. This model makes intuitive sense — the containers are the only things in the problem — so of course they’d be the nodes. But this idea breaks down as we try to continue with the modeling process. Here are some questions I ask to help students see the breakdown:

• If the nodes are the containers, are there just two nodes in the whole graph?
• If the nodes are the three containers, what are the edges?
• If the nodes are the three containers what feature of the graph represents a container with 6 liters of water in it?

These are hard questions to answer if the nodes are the containers. So what else could we choose to be the nodes? The solution is to make each node the current state of both containers. Now we can choose to make the edges represent actions we can take. Specifically we can pour liquid from one container to another and arrive at a new node. In this model there might be multiple nodes that represent a solution — any node where one of the three containers has exactly six liters is a solution.

In this model the starting node has also been defined. The problem statement says the 12 liter container is full, and the other two are empty. Here is a small subset of the graph:

An incomplete deception of a graph representing the three glass riddle.

In this model our edges are directed — pouring from the 12 liter container into the 5 liter container is not the same as pouring from the 5 liter container into the 12 liter container. Additionally, our actions are not always reversible. Consider the bottom right state in the image above: if we were to pour the 12 liter container into the 8 liter container we would end up adding 3 liters to the 8 liter container leaving us with 4/12 and 8/8. If we tried to “reverse” that action we would have to pour all 8 liters back into the 12 liter container, and we’d end up back at the start.

There may be multiple paths to any given node as well as cycles that take us back where we started.

Finally, our edges are unweighted. All of these actions can equally be done, and as far as our question is concerned, there really isn’t a difference in magnitude in taking any one action over another. We could force this problem to require edge weights by asking what is the least amount of liquid that can be transferred in order for one jug to have exactly 6 liters of water. But let’s not get ahead of ourselves — we still have to solve the easy version. Here is a path in our graph that satisfies the riddle:

Errata: **The last step should read pour 8 into 5, not pour 12 into 5**

Graphs like this — where nodes are states and edges are actions/transitions between states — are called “state machines” and they are quite common. Internet protocols such as TCP use state machines to facilitate communication between two computers on the internet. Reinforcement learning algorithms and Markov Decision Processes use and expand on the concept of a state machine. Regular expression parsers typically make use of a state machine as well.

Next article in the series: Breadth and Depth First Search

Table of contents