# Two Buckets Water Puzzle

When reading up on graph theory, I came across this puzzle and on further investigation, learned that a general solution for this is similar to this problem.

However, I haven't been able to understand how a graph may be used (though I did come across this animation). I'm trying to come up with an algorithm where, given two buckets of capacities a and b, how can I come up with the least number of steps to obtain precisely k litres? Since I originally saw the question in relation to a chapter on graph theory, I would love some pointers on how this may be solved using graphs (as opposed to the seemingly more commong gcd method).

EDIT: I found another related solution but am still not entirely certain.

• As for how to describe the problem with graphs, if you went a bit further down the page you would have seen a similar problem where they describe the graph-theoretical approach. Essentially, it involves describing each possible state as a vertex, and transitions from one state to another as edges. Mar 19, 2015 at 19:08

Solving for the least number of steps to obtain precisely $k$ liters is then a shortest path problem. You are searching the graph for the shortest path from the original state to a state that has $k$ as one the members of the ordered pair.