Water Jug Problem Algorithm
Water Jug Problem:
In the water jug problem in AI, 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 that 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
Water Jug Problem in AI:
In AI, the water jug problem algorithm is given below:
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 |