## “Water buckets” Problem

In Solving “Water buckets” Problem Using Scala  Biju Kunjummen presented a Scala program to solve this puzzle:

You have a 12-gallon bucket, an 8-gallon bucket and a 5-gallon bucket. The 12-gallon bucket is full of water and the other two are empty. Without using any additional water (or buckets) how can you divide the twelve gallons of water equally so that two of the three buckets have exactly 6 gallons of water in them?

Not knowing Scala I present here a brief description of the algorithm that can be used to solve the puzzle. (See The Sunday Programmer for a C++ implementation)

Let us name the buckets 0,1 and 2. At any stage there are six possible actions:

• Pour from 0 to 1 denoted as Pour(0,1)
• Pour (0,2)
• Pour (1,0)
• Pour(1,2)
• Pour (2,0)
• Pour(2,1)

Notice that quantity is not considered because any pour action either empties the source or fills up the destination. This leads us to a depth first solution. We try each possible action until we reach the goal… with some caveats. A pour action may be invalid if the source is empty or destination is full. Secondly if the result of a pour action returns us to a state previously visited then we ignore that state as it will lead to a cycle in a depth-first search tree. Here we define a state as the triple <X,Y,Z> where X, Y and Z is the amount of water in the 12-gallon, 8-gallon and 5-gallon bucket respectively. The initial state is <12,0,0> and the goal state is <6,6,0>. This leads us to the following algorithm:

```let seen-states = {start-state}

let Solve(current-state) =
if current-state = goal-state
return true
else
for-each action in possible-actions
next-state = Do-Pour(action, current-state)
if NOT next-state in seen-states
if Solve(next-state)
print-output action
return true
return false

Solve(start-state)
```

Here Do-Pour returns the next state after the pour action unless the pour action is invalid in which case it returns the current state; add-state adds a state to collection of states. 