# Water jugs and BFS

## Using graphs to solve puzzles

Random highschool memory: while waiting for some class, I was pondering a puzzle. You know, one of these wolf, goat and cabbage puzzles, only a bit knottier. I was just starting to take programming classes at school, and as I was searching for the solution, another puzzle, much trickier, occurred to me: *write a program to solve the puzzle*. Between writing “2D games” with ika and doing seemingly pointless exercises at school, I felt I had no handle whatsoever to approach this problem. After thinking about it hard for some time I gave up.

A few years later I encountered another famous puzzle - the water pouring puzzle. Though I’ve solved variations of it before, for some reason this time I remembered my meta-puzzle from highschool, and this time, having covered CS fundamentals, after some thought the solution clicked. It was all graphs!

### The water pouring puzzle graph

Here’s the simplest version of the puzzle I know: you have two empty jugs of water, of volumes 3 liters and 5 liters. You’re next to an infinite source of water so you can fill up the jugs as much as you want, you can pour them into each other, and you can empty them completely. Your task is to have exactly one jug full of 4 liters of water, and there’s no way to make any measurements other than “completely full” or “completely empty”.

Here’s the solution (spoiler alert), referring to the 5-liter jug as `J5`

and the 3-liter jug as `J3`

:

- Fill up
`J5`

. - Pour
`J5`

into`J3`

until`J3`

is full, leaving 2 liters in`J5`

. - Empty
`J3`

. - Pour the remaining 2 liters from
`J5`

to`J3`

, leaving 2 liters in`J3`

. - Fill up
`J5`

. - Pour
`J5`

into`J3`

until`J3`

is full, leaving exactly 4 liters in`J5`

. Done!

Now the real task is to write a program that, given the volumes of the jugs and a target volume, will either print instructions to get to the target volume or let us know that the mission is impossible.

The way we’ll approach this is by treating each state of the pair of jugs as a node in the graph of all possible states. My notation for states will be `(amount of water in J3, amount of water in J5)`

. We’ll create an edge
from node `(a, b)`

to node `(c, d)`

if there’s some legitimate, atomic action we can take in state `(a, b)`

to arrive at state `(c, d)`

. For example, we’ll draw an edge from `(0, 5)`

to `(3, 2)`

because in the former state we can pour `J5`

into `J3`

until `J3`

is full, arriving at the latter state.

The key insight is that in such a graph, a path from the node corresponding to the initial state to the node corresponding to the desired state is equivalent to a solution - we can use each edge to reconstruct the required action. And we can use BFS to search for such a path, and, if it exists, get the shortest possible solution! Quite neat. Formulating the problem like this is an instance of a state space search.

Here’s how the full graph for the `(3, 5)`

pouring puzzle looks like, with the starting node, target nodes and path highlighted:

Of course we can implement BFS on this graph without creating the graph in memory. Let’s walk through a simple implementation in Python.

First let’s get the jug volumes:

Define a function to identify a node corresponding to the target state:

Now a less trivial function - finding all neighbors of a state. At this point we’re not concerned with whether or not we’ve already seen some neighbor, we’ll just generate all of them and take care of bookkeeping later. Also, some nodes might be neighbors of themselves (e.g. if jug A is already empty we can still “empty” it), but again that will be taken care of in the same BFS bookkeeping.

While we’re at it we’ll also annotate each edge with the description of the action so we can later print it.

Now for the BFS. We’ll start by initializing a bunch of stuff - the initial state, the node exploration queue, the set of all visited states, a dictionary documenting what is the previous node of each visited node, and a dictionary containing the description of actions required to arrive from some node to another.

As for the BFS itself, we explore nodes through the queue, looking at neighbors and adding them to the queue whenever we encounter a novel state, taking care of all the bookkeeping.

And finally, we need to see if we arrived at a solution. If we did, we can reconstruct the process by going backwards
using the `prev`

and `action`

dictionaries from the final `curr_state`

until we get to the initial state.

Here are some sample runs:

```
Enter jug A volume: 3
Enter jug B volume: 5
Enter target volume: 4
Fill J5
Pour J5 into J3
Empty J3
Pour J5 into J3
Fill J5
Pour J5 into J3
-----------------------
Enter jug A volume: 7
Enter jug B volume: 5
Enter target volume: 6
Fill J7
Pour J7 into J5
Empty J5
Pour J7 into J5
Fill J7
Pour J7 into J5
Empty J5
Pour J7 into J5
Fill J7
Pour J7 into J5
-----------------------
Enter jug A volume: 6
Enter jug B volume: 4
Enter target volume: 1
No solution...
-----------------------
Enter jug A volume: 11
Enter jug B volume: 5
Enter target volume: 8
Fill J11
Pour J11 into J5
Empty J5
Pour J11 into J5
Empty J5
Pour J11 into J5
Fill J11
Pour J11 into J5
Empty J5
Pour J11 into J5
Empty J5
Pour J11 into J5
Fill J11
Pour J11 into J5
```

### Beyond water jugs

While more mathematical interpretations of the water pouring puzzle exist, the general approach can be applied to other puzzles where you need to take a series of actions, for example the 15 puzzle, Rush Hour-style puzzles or puzzles in the river-crossing style I mentioned at the beginning.

Let’s try the approach with the following puzzle:

You and three other friends found yourselves in a dark cave with a torch that will last 12 minutes. There’s enough room for only two to walk outside together, but one of them will need to go back with the torch. You only need 1 minute to leave the cave, but your friends need a little more time: 2, 4 and 5 minutes. When two people walk together the faster one waits for the slower one. How can you all exit the cave safely?

And the result:

```
1 and 2 go outside together
1 goes back with the torch
4 and 5 go outside together
2 goes back with the torch
1 and 2 go outside together
```

### Other approaches

A few years later, in an introduction to AI class, I was introduced to several other approaches for solving problems of similar nature; most notably, the Graphplan algorithm, which can represent and incorporate more sophisticated task-specific knowledge, allowing for potentially much faster searches. The algorithm also represents problems as graphs and solutions as paths, but the structure is more complicated.