While reading through some lecture notes on preliminary number theory, I came across the solution to

water jug problem (**with two jugs)** which is summed as thus:

Using the property of the G.C.D of two numbers that GCD(a,b) is the smallest possible linear combination of a and b, and hence a certain quantity Q is only measurable by the 2 jugs, iff Q is a n*GCD(a,b), since Q=sA + tB, where:

```
n = a positive integer
A = capacity of jug A
B= capacity of jug B
```

And, then the method to the solution is discussed

Another model of the solution is to model the various *states* as a state-space search problem as often resorted to in Artificial Intelligence.

My question is: What other known methods exist which models the solution, and how? Google didn't throw up much.

## Best Solution

Strictly for 2 Jug Problem

Q = Gallons you need.

Note:The Q must be a multiple of Gcd(A,B) else there is no solution. If Gcd(A,B) == 1, There is a solution for Any Q.1)

Method 1 :Extended Euclid's Algorithm will solve it faster than any Graph Algorithm.2)

Method 2:Here's aNaive Approach.(note, this can throw 2 solutions, You'll have to choose which is shorter)The Problem in question can be simply solved by

`repeatedly`

Fill from one bucket A to another bucket B (order doesnt matter) until it fills up with the amount you want...ofcoz, when a bucket fillsup, you empty it and continue.Repeatedly Fill A->B

Lets try and observe what happens if we go the other way round, Fill B->A

In this case filling B->A gives us the goal state faster than A->B

Generic N JugsHere's an interesting paper