Water Jug Problem in Artificial Intelligence

The Water Jug Problem is a classical Toy Problem in Artificial Intelligence used to demonstrate problem formulation, state-space representation, operators, search strategies, and solution paths.

It is particularly useful for understanding how an AI system can find a sequence of actions to reach a desired goal from an initial state.

1. Definition

The Water Jug Problem is a problem in which we are given two or more water jugs with fixed capacities and an unlimited supply of water. The objective is to measure a specific quantity of water by performing a permitted set of operations such as filling, emptying, and transferring water between jugs.

Exam Definition

The Water Jug Problem is a classical AI state-space search problem in which an agent must obtain a desired quantity of water using jugs of fixed capacities and a set of legal operations such as fill, empty and pour.

2. Example of Water Jug Problem

Suppose we have:

Jug A = 4 litres
Jug B = 3 litres
Unlimited water supply
No measuring scale
Goal = obtain exactly 2 litres of water

We can represent the state as:

(x, y)

where:

x = amount of water in 4-litre Jug A
y = amount of water in 3-litre Jug B

Therefore:

Initial State

(0, 0)

Both jugs are empty.

Goal State

(2, 0)

(2, 3)

depending on the formulation.

3. State-Space Representation

State-space representation is one of the most important concepts in this problem.

A state represents the current amount of water in both jugs.

For example:

(0,0) → Both empty

(4,0) → 4L jug full, 3L jug empty

(0,3) → 4L jug empty, 3L jug full

(4,3) → Both jugs full

(2,3) → 2L in 4L jug, 3L in 3L jug

Since Jug A has capacity 4 and Jug B has capacity 3:

0 ≤ x ≤ 4
0 ≤ y ≤ 3

Therefore, a state can be written as:\[ (x,y) \]

where:\[ x \in \{0,1,2,3,4\} \]

and\[ y \in \{0,1,2,3\} \]

There are at most:\[ 5 \times 4 = 20 \]

possible states.

4. Components of the Water Jug Problem

An AI problem can be formally represented using five major components.

Component	Water Jug Example
Initial State	`(0,0)`
Actions/Operators	Fill, empty, pour
State	`(x,y)`
Goal Test	Check whether desired quantity is obtained
Path Cost	Number of operations

So:

Initial State
     ↓
Possible Actions
     ↓
New States
     ↓
Search
     ↓
Goal State

5. Operators / Legal Actions

There are several operations that the AI can perform.

Operation 1: Fill Jug A

Fill the 4-litre jug completely.

(x,y) → (4,y)

Example:

(0,0) → (4,0)

Operation 2: Fill Jug B

Fill the 3-litre jug completely.

(x,y) → (x,3)

Example:

(0,0) → (0,3)

Operation 3: Empty Jug A

Empty the 4-litre jug.

(x,y) → (0,y)

Example:

(4,3) → (0,3)

Operation 4: Empty Jug B

Empty the 3-litre jug.

(x,y) → (x,0)

Example:

(4,3) → (4,0)

6. Pour Jug A into Jug B

Suppose:

Jug A = 4 L
Jug B = 3 L

If we pour water from A into B, we continue until:

A becomes empty, or
B becomes full.

For example:

(4,0)

Pour A → B:

(4,0)
   ↓
(1,3)

Why?

A initially has 4 L.
B can accept only 3 L.
Therefore, 3 L moves from A to B.
A is left with 1 L.

So:

4L jug = 1L
3L jug = 3L

State:

(1,3)

7. Pour Jug B into Jug A

Similarly, we can pour water from B into A.

For example:

(0,3)

Pour B → A:

(0,3)
   ↓
(3,0)

The 3 litres from B move into A.

8. Complete Set of Operators

For two jugs A and B:

Fill

Fill A:  (x,y) → (4,y)

Fill B:  (x,y) → (x,3)

Empty

Empty A: (x,y) → (0,y)

Empty B: (x,y) → (x,0)

Pour A → B

(x,y) → (x-d, y+d)

where d is the maximum amount that can be transferred without overflowing B.

Pour B → A

(x,y) → (x+d, y-d)

where d is the maximum amount that can be transferred without overflowing A.

9. Solving the 4-Litre and 3-Litre Problem

Problem

Using a 4-litre jug and a 3-litre jug, measure exactly 2 litres of water.

Initial state:

(0,0)

Goal:

(2,0)

One solution is:

Step	Operation	State
0	Initial	`(0,0)`
1	Fill 3L jug	`(0,3)`
2	Pour 3L → 4L	`(3,0)`
3	Fill 3L jug	`(3,3)`
4	Pour 3L → 4L	`(4,2)`
5	Empty 4L jug	`(0,2)`

Now we have:

3L Jug = 2 litres

Therefore, the goal has been achieved.

Solution Path

(0,0)
  ↓ Fill B
(0,3)
  ↓ Pour B → A
(3,0)
  ↓ Fill B
(3,3)
  ↓ Pour B → A
(4,2)
  ↓ Empty A
(0,2)

Goal achieved: 2 litres.

10. State-Space Graph

The Water Jug Problem can be represented as a graph.

              (0,0)
             /     \
        Fill A     Fill B
          /           \
       (4,0)          (0,3)
          |              |
       Pour A→B       Pour B→A
          |              |
       (1,3)          (3,0)
          |              |
       Empty B        Fill B
          |              |
       (1,0)          (3,3)

The AI searches this graph to find a path from:

Initial State → Goal State

11. Water Jug Problem as a Search Problem

The Water Jug Problem demonstrates the basic idea of search in Artificial Intelligence.

The AI system:

Starts with the initial state.
Generates possible actions.
Produces new states.
Checks whether the goal has been reached.
If not, continues searching.
Stops when a solution is found.

General process

             Initial State
                  |
                  ↓
          Generate Actions
                  |
                  ↓
           Generate States
                  |
                  ↓
             Goal Test
             /        \
           Yes         No
            |           |
         Solution    Continue
                      Search

12. Which Search Algorithms Can Be Used?

Several AI search techniques can solve the Water Jug Problem.

1. Breadth-First Search (BFS)

BFS explores states level by level.

Level 0 → (0,0)

Level 1 → possible states

Level 2 → states generated from Level 1

Level 3 → states generated from Level 2

If every operation has the same cost, BFS can find a solution with the minimum number of operations.

2. Depth-First Search (DFS)

DFS follows one path as deeply as possible before backtracking.

Start
 ↓
State
 ↓
State
 ↓
State
 ↓
Backtrack if necessary

It may find a solution without guaranteeing the shortest solution.

3. Uniform Cost Search

If different operations have different costs, Uniform Cost Search can find the least-cost solution.

13. Importance of State Representation

The biggest lesson from the Water Jug Problem is that a real-world situation can be represented mathematically.

Instead of saying:

“There is some water in two jugs.”

AI represents it as:

(x,y)

For example:

(2,3)

means:

4L Jug → 2 litres
3L Jug → 3 litres

This makes the problem suitable for computer processing.

14. Goal Test

A goal test checks whether the current state satisfies the objective.

For example, if the objective is:

Obtain exactly 2 litres.

The goal test can be:

x = 2
OR
y = 2

Therefore:

(2,0) → Goal
(2,3) → Goal
(0,2) → Goal
(4,2) → Goal

depending on the problem requirement.

15. Path Cost

Path cost represents the cost of reaching a state.

If every operation costs 1:

Fill = 1
Empty = 1
Pour = 1

Then:\[ Path\ Cost = Number\ of\ operations \]

For example:

(0,0)
 ↓ 1
(0,3)
 ↓ 1
(3,0)
 ↓ 1
(3,3)
 ↓ 1
(4,2)

The path cost is:\[ 4 \]

16. Important AI Concepts Demonstrated

The Water Jug Problem helps students understand several important AI concepts:

AI Concept	Water Jug Example
State	`(x,y)`
Initial state	`(0,0)`
Goal state	State containing required quantity
Operators	Fill, empty, pour
State space	All possible `(x,y)` combinations
Search	Finding sequence of operations
Path	Sequence from initial to goal
Path cost	Number/cost of operations
Goal test	Check required quantity
BFS/DFS	Search techniques

17. Important Property: Solvability

Not every Water Jug Problem has a solution.

Suppose the jug capacities are:

A = 4 litres
B = 3 litres

We can measure:

1 litre
2 litres
3 litres
4 litres

But whether a target is measurable depends on the relationship between the jug capacities.

A classical mathematical condition is:\[ gcd(A,B) \mid Target \]

That means the greatest common divisor (GCD) of the jug capacities must divide the desired quantity.

Example

For 4 L and 3 L:\[ GCD(4,3)=1 \]

Since 1 divides 2:\[ 1 \mid 2 \]

the 2-litre problem is solvable.

18. Why is Water Jug a Toy Problem?

The Water Jug Problem is called a toy problem because it is:

Small
Clearly defined
Easy to represent
Has a limited state space
Has clearly defined actions
Has a clearly defined goal
Can be solved using standard search algorithms

It does not contain the complexity and uncertainty normally found in real-world problems.

19. Real-World Analogy

Although the Water Jug Problem itself is a toy problem, its underlying idea is extremely important.

For example, consider route planning.

Water Jug Problem       Route Planning

State                   Current location
Action                  Take a road
New State               New location
Goal                    Destination
Cost                    Distance/time
Search                  Find best route

Similarly:

Water Jug
    ↓
State representation
    ↓
Actions
    ↓
Search
    ↓
Goal

is the foundation for many AI problem-solving systems.

20. Water Jug Problem — Exam Answer

Short Answer

The Water Jug Problem is a classical toy problem in Artificial Intelligence used to demonstrate state-space search. Given two jugs of fixed capacities and an unlimited water supply, the objective is to obtain a specified quantity of water using operations such as filling, emptying and pouring. A state is represented as (x,y), where x and y represent the quantities of water in the two jugs. AI search algorithms such as BFS and DFS can be used to find a sequence of operations from the initial state to the goal state.

Key Flow

Water Jug Problem
       ↓
Initial State
    (0,0)
       ↓
State Representation
    (x,y)
       ↓
Operators
Fill / Empty / Pour
       ↓
State Space
       ↓
Search Algorithm
 BFS / DFS / UCS
       ↓
Goal Test
       ↓
Goal State

Most Important Points for MCA Students

Remember these 7 terms:

Initial State → State → Operators → State Space → Goal Test → Search → Path Cost

These seven concepts form the core of the Water Jug Problem and are directly connected to AI problem formulation and searching for solutions.