# 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

**(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 |