# Water Jug Problem Algorithm

Problem Formulation:
We are given two jugs, a four-gallon one and a three-gallon one. Neither has any measuring markers on it. There is a pump which can be used to fill the jugs with water. How can we get exactly two gallons of water into the four-gallon jug?

State Space:
The state-space for this problem can be described as the set of ordered pairs of integers (x,y) such that x=0, 1, 2, 3, or 4 and y=0, 1, 2, or 3. Here x is the number of a gallon of water in the four-gallon jug and y is the quantity of water in the three-gallon jug.
Start State : (0,0)
Goal State : (2,n) for any value of n

1. (x,y)→(4,y) // Fill the 4 gallon jug
if x<4

2. (x,y)→(x,3) // Fill the 3 gallon jug
if y<3

3. (x,y)→(x-d,y) // Pour some water out of the 4-gallon jug
if x>0

4. (x,y)→(x,y-d) // Pour some water out of the 3-gallon jug
if x>0

5. (x,y)→(0,y) // Empty the 4-gallon jug on the ground
if x>0

6. (x,y)→(x,0) // Empty the 3-gallon jug on the ground
if y>0

7. (x,y)→(4,y-(4-x)) // Pour water from the 3-gallon jug into the 4 gallons until the 4-gallon jug is full
if x+y≥4 and y>0

8. (x,y)→(x-(3-y),3) // Pour water from the 4-gallon jug into the 3 gallons until the 3-gallon jug is full
if x+y≥3 and x>0

9. (x,y)→(x+y,0) // Pour water all the water from the 3-gallon jug into the 4-gallon jug
if x+y≤4 and y>0

10. (x,y)→(0,x+y) // Pour water all the water from the 4-gallon jug into the 3-gallon jug
if x+y≤3 and x>0

Solution:

 Gallons in the 4-Gallon jug Gallons in the 3-Gallon jug Rule Applied 0 0 2 0 3 9 3 0 2 3 3 7 4 2 5 0 2 9 2 0