Problem Description: Water Jug Problem
• You are given two jugs, one with a capacity of X liters and the other with a capacity
of Y liters.
• You need to measure exactly Z liters of water using these two jugs.
• The allowed operations are:
o Empty a Jug
o Fill a Jug (You may assume that you have unlimited supply of water)
o Pour water from one jug to the other until one of the jugs is either empty
or full.
Sample Problem Scenario:
Consider a scenario where you have a 3-liter jug and a 5-liter jug, and you need to
measure precisely 4 liters of water.
1. Understanding the Setup
Let's establish the ground rules and how we "talk" to the computer about this problem.
• The Goal: We start with empty jugs and want to reach a state where one jug
contains exactly 4 Liters.
• The Jugs:
o Jug A: Capacity = 3 Liters
o Jug B: Capacity = 5 Liters
• The State: We represent the current situation as a pair of numbers: (a, b).
o a = amount of water in the 3L jug.
o b = amount of water in the 5L jug.
o Start State: (0, 0) (Both empty).
o Goal State: Any pair that looks like (n, 4) or (4, n).
2. The Rules (The Action Space)
From any state (a, b), you can perform these moves to generate new states (children):
1. Fill A: Make a = 3.
2. Fill B: Make b = 5.
3. Empty A: Make a = 0.
4. Empty B: Make b = 0.
5. Pour A → B: Pour water from A to B until B is full OR A is empty.
6. Pour B → A: Pour water from B to A until A is full OR B is empty.
3. Step-by-Step BFS Execution
Let's trace the algorithm. We use a Queue (First-In-First-Out line) to keep track of
states we need to visit, and a Visited List to ensure we don't repeat work.
Layer 0 (Start)
• Current State: (0, 0)
• Action: Add (0, 0) to the Queue.
Layer 1 (1 Step Away)
We take (0, 0) out of the queue and generate all possible next moves:
1. Fill 3L → State: (3, 0)
2. Fill 5L → State: (0, 5)
Note: Emptying empty jugs or pouring empty jugs does nothing, so we ignore those.
Queue now: [(3, 0), (0, 5)]
Layer 2 (2 Steps Away)
Now we look at the states generated in Layer 1.
A. Expand (3, 0):
• Empty 3L → (0, 0) (Skip, already visited)
• Fill 5L → (3, 5)
• Pour 3L to 5L → (0, 3) (Transfer the 3L into the empty 5L jug)
B. Expand (0, 5):
• Fill 3L → (3, 5) (Duplicate, skip)
• Empty 5L → (0, 0) (Skip)
• Pour 5L to 3L → (3, 2) (Fill the 3L jug, leaving 2L in the 5L jug)
Queue now: [(3, 5), (0, 3), (3, 2)]
Layer 3 (3 Steps Away)
We continue exploring the new states.
A. Expand (0, 3) (from the path where we poured 3L into 5L):
• Fill 3L → (3, 3)
• Empty 5L → (0, 0) (Skip)
• Pour 5L to 3L → (3, 0) (Skip, visited in Layer 1)
B. Expand (3, 2) (from the path where we poured 5L into 3L):
• Empty 3L → (0, 2) (We dump the 3L jug, keeping the 2L in the 5L jug)
• Fill 5L → (3, 5) (Skip)
• Pour 3L to 5L → (0, 5) (Skip, visited in Layer 1)
Queue now: [(3, 3), (0, 2), ...]
Layer 4... and Finding the Goal
Let's fast forward slightly following the path from state (0, 2).
1. We have (0, 2).
2. Next Move: Pour the 2L from the 5L jug into the 3L jug.
o New State: (2, 0)
3. Next Move: Fill the 5L jug.
o New State: (2, 5)
4. Next Move (The Solution): Pour from the 5L jug into the 3L jug.
o The 3L jug already has 2 Liters. It only needs 1 Liter to be full.
o We pour 1 Liter from the 5L jug.
o The 5L jug had 5 Liters. 5 - 1 = 4 Liters.
o Final State: (3, 4)
Goal Reached! We have 4 Liters in the 5L jug.
Using BFS, we found this shortest path (solution):
State (3L,
Step Operation Explanation
5L)
0 Start (0, 0) Both empty
1 Fill 5L (0, 5) Fill the big jug
Pour 5L → Fill the small jug from the big one (leaves
2 (3, 2)
3L 2L)
3 Empty 3L (0, 2) Dump the small jug
State (3L,
Step Operation Explanation
5L)
Pour 5L →
4 (2, 0) Move the 2L into the small jug
3L
5 Fill 5L (2, 5) Fill the big jug again
Pour 5L → Pour until small jug is full (takes 1L,
6 (3, 4)
3L leaves 4L)
Why this worked
This step-by-step demonstration shows how Breadth-First Search systematically
explores the state space to find the optimal solution to the Water Jug Problem. BFS
systematically explored all 1-move sequences, then all 2-move sequences, etc., until it
hit the goal. It ensured we didn't run in infinite circles (like pouring back and forth
repeatedly) by keeping a "Visited" list.