Home » Machine Learning/Artificial Intelligence

# Water jug problem in Artificial Intelligence

In this article, we will learn about the very popular problem dealt with Artificial Intelligence: **the water jug problem**. We will learn what this problem is, what set of rules were made to solve it, and what was the final set of rules in solving the problem?

Submitted by Monika Sharma, on May 29, 2019

In the **water jug problem in Artificial Intelligence**, we are provided with two jugs: one having the capacity to hold 3 gallons of water and the other has the capacity to hold 4 gallons of water. There is no other measuring equipment available and the jugs also do not have any kind of marking on them. So, the agent’s task here is to fill the 4-gallon jug with 2 gallons of water by using only these two jugs and no other material. Initially, both our jugs are empty.

So, to solve this problem, following set of rules were proposed:

**Production rules for solving the water jug problem**

Here, let ** x** denote the 4-gallon jug and

**denote the 3-gallon jug.**

*y*S.No. | Initial State | Condition | Final state | Description of action taken |
---|---|---|---|---|

1. | (x,y) | If x<4 | (4,y) | Fill the 4 gallon jug completely |

2. | (x,y) | if y<3 | (x,3) | Fill the 3 gallon jug completely |

3. | (x,y) | If x>0 | (x-d,y) | Pour some part from the 4 gallon jug |

4. | (x,y) | If y>0 | (x,y-d) | Pour some part from the 3 gallon jug |

5. | (x,y) | If x>0 | (0,y) | Empty the 4 gallon jug |

6. | (x,y) | If y>0 | (x,0) | Empty the 3 gallon jug |

7. | (x,y) | If (x+y)<7 | (4, y-[4-x]) | Pour some water from the 3 gallon jug to fill the four gallon jug |

8. | (x,y) | If (x+y)<7 | (x-[3-y],y) | Pour some water from the 4 gallon jug to fill the 3 gallon jug. |

9. | (x,y) | If (x+y)<4 | (x+y,0) | Pour all water from 3 gallon jug to the 4 gallon jug |

10. | (x,y) | if (x+y)<3 | (0, x+y) | Pour all water from the 4 gallon jug to the 3 gallon jug |

The listed production rules contain all the actions that could be performed by the agent in transferring the contents of jugs. But, to solve the water jug problem in a minimum number of moves, following set of rules in the given sequence should be performed:

**Solution of water jug problem according to the production rules:**

S.No. | 4 gallon jug contents | 3 gallon jug contents | Rule followed |
---|---|---|---|

1. | 0 gallon | 0 gallon | Initial state |

2. | 0 gallon | 3 gallons | Rule no.2 |

3. | 3 gallons | 0 gallon | Rule no. 9 |

4. | 3 gallons | 3 gallons | Rule no. 2 |

5. | 4 gallons | 2 gallons | Rule no. 7 |

6. | 0 gallon | 2 gallons | Rule no. 5 |

7. | 2 gallons | 0 gallon | Rule no. 9 |

On reaching the 7^{th} attempt, we reach a state which is our goal state. Therefore, at this state, our problem is solved.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.