Water Jug Problem in AI – BFS, DFS, Python & Java Solutions

Updated on April 16, 2026

•

18 min read

ARTICLE OUTLINE

What is the Water Jug Problem in AI?Problem Statement Problem Constraints Mathematical Foundation – GCD Method Water Jug Problem using the BFS Approach Water Jug Problem using the DFS Approach BFS vs DFS – Which Should You Use?Water Jug Problem in AI using Python – Step-by-Step Significance in AI Applications of the Water Jug Problem Challenges and Advancements Conclusion People Also Ask FAQs

The water jug problem in ai is one of the most widely studied examples in artificial intelligence education. It introduces learners to two pillars of search algorithms in artificial intelligence – Breadth-First Search (BFS) and Depth-First Search (DFS) – through a concrete, intuitive puzzle. Despite its apparent simplicity, the problem encapsulates fundamental concepts including state space representation in ai, goal testing, and heuristic reasoning.

This guide provides the complete water jug problem solution with worked examples, step-by-step algorithms, Python and Java code, complexity analysis, and a clear comparison between BFS and DFS. By the end, you will have a thorough understanding of how the water jug problem in artificial intelligence fits into the broader landscape of AI problem-solving.

What is the Water Jug Problem in AI?

Water jug in ai refers to a classic constraint-satisfaction puzzle used to teach search-based problem solving. You have two unmarked jugs – one with capacity X litres and one with Y litres – and your goal is to measure exactly Z litres of water. The only allowed operations are: fill a jug completely, empty a jug completely, or pour water from one jug to the other until one is full or the other is empty.

What makes the water jug problem in ai significant is not the puzzle itself, but the ai problem solving examples it generates. Every possible combination of water levels in both jugs is a state. Every allowed operation is a transition. The set of all reachable states from the initial state forms the state space representation in ai – and searching this space efficiently is what BFS and DFS accomplish.

Key Insight: The water jug problem is a canonical example in AI textbooks because it cleanly separates the problem domain (liquid measurement) from the search strategy – making it ideal for teaching BFS vs DFS trade-offs in isolation.

POSTGRADUATE PROGRAM IN

Data Science & AIML

Learn Data Science, AI & ML to turn raw data into powerful, predictive insights.

Problem Statement

You have two jugs – one with capacity X litres and one with Y litres. Your objective is to measure exactly Z litres by performing any combination of the following operations:

• Fill either jug to its maximum capacity

• Empty either jug completely

• Pour water from one jug into the other until one jug is full or the other is empty

Worked Examples

Example 1 – Water Jug Problem Example (3L, 5L → 4L):

Step	Jug 1 (3L)	Jug 2 (5L)	Action
1	0	5	Fill Jug 2
2	3	2	Pour Jug 2 → Jug 1 until full
3	0	2	Empty Jug 1
4	2	0	Pour Jug 2 → Jug 1
5	2	5	Fill Jug 2
6	3	4	Pour Jug 2 → Jug 1 until full
Result	3	4	✓ 4 litres achieved in Jug 2

Input: jug1=3L, jug2=5L, target=4L | Output: True

Example 2 – Water Jug Problem Example (2L, 6L → 5L):

Input: jug1=2L, jug2=6L, target=5L | Output: False – The GCD of 2 and 6 is 2. Since 5 is not divisible by 2, it is mathematically impossible to measure exactly 5 litres with these jugs.

Example 3 – Water Jug Problem Example (7L, 9L → 4L):

Step	Jug 1 (7L)	Jug 2 (9L)	Action
1	0	9	Fill Jug 2
2	7	2	Pour Jug 2 → Jug 1 until full
3	0	2	Empty Jug 1
4	2	0	Pour Jug 2 → Jug 1
5	2	9	Fill Jug 2
6	7	4	Pour Jug 2 → Jug 1 until full
Result	7	4	✓ 4 litres achieved in Jug 2

Input: jug1=7L, jug2=9L, target=4L | Output: True

Problem Constraints

The water jug problem algorithm operates under the following constraints:

• jug1Capacity (X) and jug2Capacity (Y) must be positive integers: 1 ≤ X, Y ≤ 1000

• targetAmount (Z) is a non-negative integer: 0 ≤ Z ≤ X + Y

• Both jugs are unmarked – no measurement lines exist for partial fills

• Operations (fill, empty, pour) can be performed any number of times

• Water can only be transferred directly between the two jugs

Mathematical Foundation – GCD Method

Before running BFS or DFS on the water jug problem in ai, you can determine solvability instantly using number theory. A water jug problem solution exists if and only if the targetAmount Z is divisible by the Greatest Common Divisor (GCD) of jug1Capacity (X) and jug2Capacity (Y), AND Z ≤ X + Y.

Formal condition: targetAmount % gcd(jug1Capacity, jug2Capacity) == 0

Jug 1 (X)	Jug 2 (Y)	Target (Z)	GCD(X,Y)	Z % GCD	Solvable?
3	5	4	1	4 % 1 = 0	Yes – True
2	6	5	2	5 % 2 = 1	No – False
7	9	4	1	4 % 1 = 0	Yes – True
4	6	3	2	3 % 2 = 1	No – False
3	7	6	1	6 % 1 = 0	Yes – True

This mathematical shortcut is the foundation of the optimal water jug problem solution. When building the water jug problem algorithm, adding a GCD pre-check before running BFS or DFS eliminates entire unsolvable problem instances in O(log(min(X,Y))) time – far faster than exhaustive search.

GCD Pre-Check – Python Code

# water jug problem in ai python - GCD pre-check

import math

def can_measure_water_gcd(jug1: int, jug2: int, target: int) -> bool:

if target > jug1 + jug2:

return False

if target == 0:

return True

return target % math.gcd(jug1, jug2) == 0

# Examples

print(can_measure_water_gcd(3, 5, 4)) # True (GCD=1, 4%1=0)

print(can_measure_water_gcd(2, 6, 5)) # False (GCD=2, 5%2=1)

print(can_measure_water_gcd(7, 9, 4)) # True (GCD=1, 4%1=0)

82.9%

of professionals don't believe their degree can help them get ahead at work.

Water Jug Problem using the BFS Approach

The Breadth-First Search (BFS) approach to the water jug problem in ai explores all possible states of both jugs level by level – guaranteeing the shortest sequence of operations to reach the target. Each state (jug1_level, jug2_level) is a node in a graph. BFS uses a queue to process states in FIFO order, ensuring minimum operations are always explored first.

Step-by-Step BFS Algorithm

1. Initialisation: If targetAmount > jug1Capacity + jug2Capacity, return False. Initialise a queue with state (0,0) and a visited set.

2. BFS Loop: Pop state (jug1, jug2) from the queue. If jug1 == target, jug2 == target, or jug1+jug2 == target → return True.

3. Generate States: For each current state, generate 6 new states: Fill jug1, Fill jug2, Empty jug1, Empty jug2, Pour jug2→jug1, Pour jug1→jug2.

4. Track Visited: Add each unvisited new state to the queue and mark it visited.

5. Termination: If queue empties with no solution found → return False.

BFS – Python Code (water jug problem in ai python)

# water jug problem in ai using python - BFS solution

from collections import deque

class Solution:

def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetAmount: int) -> bool:

if targetAmount > jug1Capacity + jug2Capacity:

return False

queue = deque([(0, 0)])

visited = set([(0, 0)])

while queue:

jug1, jug2 = queue.popleft()

if jug1 == targetAmount or jug2 == targetAmount or jug1 + jug2 == targetAmount:

return True

possible_actions = [

(jug1Capacity, jug2), # fill jug1

(jug1, jug2Capacity), # fill jug2

(0, jug2), # empty jug1

(jug1, 0), # empty jug2

(min(jug1+jug2, jug1Capacity), # pour jug2 -> jug1

jug2 - (min(jug1+jug2, jug1Capacity)-jug1)),

(jug1 - (min(jug1+jug2, jug2Capacity)-jug2), # pour jug1 -> jug2

min(jug1+jug2, jug2Capacity))

]

for new_jug1, new_jug2 in possible_actions:

if (new_jug1, new_jug2) not in visited:

visited.add((new_jug1, new_jug2))

queue.append((new_jug1, new_jug2))

return False

# Test

sol = Solution()

print(sol.canMeasureWater(3, 5, 4)) # True

print(sol.canMeasureWater(2, 6, 5)) # False

BFS – Java Code

import java.util.*;

public class WaterJugBFS {

public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetAmount) {

if (targetAmount > jug1Capacity + jug2Capacity) return false;

Queue queue = new LinkedList<>();

queue.add(new int[]{0, 0});

Set visited = new HashSet<>();

visited.add("0,0");

while (!queue.isEmpty()) {

int[] cur = queue.poll();

int j1 = cur[0], j2 = cur[1];

if (j1==targetAmount || j2==targetAmount || j1+j2==targetAmount) return true;

int[][] next = {

{jug1Capacity, j2},

{j1, jug2Capacity},

{0, j2},

{j1, 0},

{Math.min(j1+j2,jug1Capacity), j2-(Math.min(j1+j2,jug1Capacity)-j1)},

{j1-(Math.min(j1+j2,jug2Capacity)-j2), Math.min(j1+j2,jug2Capacity)}

};

for (int[] s : next) {

String key = s[0]+","+s[1];

if (!visited.contains(key)) { visited.add(key); queue.add(s); }

}

return false;

}

BFS Complexity Analysis

Metric	Value	Explanation
Time Complexity	O(X × Y)	X = jug1 capacity, Y = jug2 capacity. Each unique (jug1, jug2) pair is a state – BFS visits each at most once.
Space Complexity	O(X × Y)	The queue and visited set can hold all possible states simultaneously in the worst case.

Water Jug Problem using the DFS Approach

The Depth-First Search (DFS) approach explores each path fully before backtracking. For the water jug problem in ai, DFS recursively tries every operation (fill, empty, pour) from the current state, diving deep into one branch before trying alternatives. It uses a visited set to prevent cycles and returns True as soon as the target is found.

Unlike BFS, DFS does not guarantee the shortest solution path. However, it uses less memory in practice (proportional to the current recursion depth) and finds a valid water jug problem solution if one exists.

Step-by-Step DFS Algorithm

6. Initial Check: If targetAmount > jug1 + jug2, return False immediately.

7. DFS Setup: Create a helper function dfs(jug1, jug2). Maintain a visited set to prevent cycles.

8. Base Case: If jug1 == target, jug2 == target, or jug1+jug2 == target → return True. If state already visited → return False.

9. Recursive Actions: Try all 6 operations recursively. Return True if any branch finds the target.

10. Termination: If all branches exhausted without finding the target → return False.

DFS – Python Code (water jug problem python code)

# water jug problem in artificial intelligence in python - DFS solution

class Solution:

def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetAmount: int) -> bool:

if targetAmount > jug1Capacity + jug2Capacity:

return False

visited = set()

def dfs(jug1, jug2):

if jug1==targetAmount or jug2==targetAmount or jug1+jug2==targetAmount:

return True

if (jug1, jug2) in visited:

return False

visited.add((jug1, jug2))

return (

dfs(jug1Capacity, jug2) or # fill jug1

dfs(jug1, jug2Capacity) or # fill jug2

dfs(0, jug2) or # empty jug1

dfs(jug1, 0) or # empty jug2

dfs(min(jug1+jug2, jug1Capacity), # pour jug2 -> jug1

jug2-(min(jug1+jug2, jug1Capacity)-jug1)) or

dfs(jug1-(min(jug1+jug2, jug2Capacity)-jug2), # pour jug1 -> jug2

min(jug1+jug2, jug2Capacity))

)

return dfs(0, 0)

# Test - water jug problem in ai python code

sol = Solution()

print(sol.canMeasureWater(3, 5, 4)) # True

print(sol.canMeasureWater(2, 6, 5)) # False

DFS – Java Code

import java.util.*;

public class WaterJugDFS {

public boolean canMeasureWater(int j1Cap, int j2Cap, int target) {

if (target > j1Cap + j2Cap) return false;

return dfs(j1Cap, j2Cap, target, 0, 0, new HashSet<>());

}

private boolean dfs(int j1Cap, int j2Cap, int target, int j1, int j2, Set visited) {

if (j1==target || j2==target || j1+j2==target) return true;

String state = j1+","+j2;

if (visited.contains(state)) return false;

visited.add(state);

return dfs(j1Cap,j2Cap,target, j1Cap,j2,visited) ||

dfs(j1Cap,j2Cap,target, j1,j2Cap,visited) ||

dfs(j1Cap,j2Cap,target, 0,j2,visited) ||

dfs(j1Cap,j2Cap,target, j1,0,visited) ||

dfs(j1Cap,j2Cap,target, Math.min(j1+j2,j1Cap),

j2-(Math.min(j1+j2,j1Cap)-j1),visited) ||

dfs(j1Cap,j2Cap,target, j1-(Math.min(j1+j2,j2Cap)-j2),

Math.min(j1+j2,j2Cap),visited);

}

DFS Complexity Analysis

Metric	Value	Explanation
Time Complexity	O(X × Y)	Each unique state is visited at most once due to the visited set.
Space Complexity	O(X × Y)	Visited set + call stack depth – worst case equals total state count.

BFS vs DFS – Which Should You Use?

Breadth first search vs depth first search is one of the most important decisions when solving the water jug problem in ai. The two search algorithms in artificial intelligence differ fundamentally in how they explore the state space – and those differences matter in practice.

Dimension	BFS	DFS
Search order	Level-by-level (FIFO queue)	Branch-by-branch (recursion / stack)
Shortest path	Guaranteed – always finds minimum operations	Not guaranteed – finds a valid path, not necessarily shortest
Memory usage	Higher – stores all frontier states	Lower in practice – stores only current path
Time complexity	O(X × Y)	O(X × Y)
Space complexity	O(X × Y)	O(X × Y) worst case; O(depth) average
Risk	Memory exhaustion on large state spaces	Stack overflow on very deep recursion (large X,Y)
Best for	Finding minimum-step solution	Quickly checking if a solution exists
Implementation	Iterative (queue)	Recursive or iterative (stack)
Use in water jug problem	Optimal – guarantees fewest steps	Correct but may find longer path

Recommendation: Use BFS when you need the minimum number of operations (e.g., for a real-world scenario where efficiency matters). Use DFS when you only need to verify solvability and memory is constrained. Both search algorithms in artificial intelligence produce correct answers – the difference is optimality and resource usage. The breadth first search vs depth first search trade-off here mirrors the broader choice faced in any AI pathfinding scenario.

Water Jug Problem in AI using Python – Step-by-Step

For learners who want to trace through the water jug problem in ai python execution manually, here is a complete traced BFS run for jug1=3L, jug2=5L, target=4L – showing every state the water jug problem algorithm visits before finding the solution.

Step	State (j1,j2)	Action Taken	Queue After Action
Start	(0,0)	Initial state	[(0,0)]
1	(0,0)	Fill jug1 → (3,0)	[(3,0),(0,5),(0,0)*skip]
2	(3,0)	Fill jug2 → (3,5)	[(0,5),(3,5),…]
3	(0,5)	Pour j2→j1 → (3,2)	[(3,5),(3,2),…]
4	(3,5)	Check: 3+5=8 ≠ 4	Continue BFS
5	(3,2)	Empty j1 → (0,2)	[(0,2),…]
6	(0,2)	Pour j2→j1 → (2,0)	[(2,0),…]
7	(2,0)	Fill j2 → (2,5)	[(2,5),…]
8	(2,5)	Pour j2→j1 → (3,4)	[(3,4),…]
9	(3,4)	Check: j2=4 == target!	Return True ✓

This trace shows exactly 9 steps to reach the solution – this is the guaranteed shortest path from BFS. The full water jug problem in ai python code (BFS version above) will produce this exact traversal sequence. Understanding this trace is critical for debugging your own implementation of the water jug problem in artificial intelligence with example.

Complete Runnable Python Script – Both BFS and DFS

# water jug problem in ai python code - complete runnable script

# Includes GCD check, BFS, and DFS - all three approaches

import math

from collections import deque

# ── Approach 1: GCD Method (O(log n)) ──────────────────────────────

def gcd_approach(x, y, z):

if z > x + y: return False

if z == 0: return True

return z % math.gcd(x, y) == 0

# ── Approach 2: BFS (water jug problem in ai using python) ─────────

def bfs_approach(x, y, z):

if z > x + y: return False

queue, visited = deque([(0,0)]), {(0,0)}

while queue:

j1, j2 = queue.popleft()

if j1==z or j2==z or j1+j2==z: return True

for nj1, nj2 in [(x,j2),(j1,y),(0,j2),(j1,0),

(min(j1+j2,x), j2-(min(j1+j2,x)-j1)),

(j1-(min(j1+j2,y)-j2), min(j1+j2,y))]:

if (nj1,nj2) not in visited:

visited.add((nj1,nj2)); queue.append((nj1,nj2))

return False

# ── Approach 3: DFS (water jug problem python code) ─────────────────

def dfs_approach(x, y, z):

if z > x + y: return False

visited = set()

def dfs(j1, j2):

if j1==z or j2==z or j1+j2==z: return True

if (j1,j2) in visited: return False

visited.add((j1,j2))

return (dfs(x,j2) or dfs(j1,y) or dfs(0,j2) or dfs(j1,0) or

dfs(min(j1+j2,x), j2-(min(j1+j2,x)-j1)) or

dfs(j1-(min(j1+j2,y)-j2), min(j1+j2,y)))

return dfs(0,0)

# ── Tests ────────────────────────────────────────────────────────────

tests = [(3,5,4,True),(2,6,5,False),(7,9,4,True)]

for x,y,z,expected in tests:

gcd = gcd_approach(x,y,z)

bfs = bfs_approach(x,y,z)

dfs = dfs_approach(x,y,z)

print(f'Jugs({x},{y}) target={z}: GCD={gcd} BFS={bfs} DFS={dfs} Expected={expected}')

Significance in AI

The water jug problem in artificial intelligence with example is more than a classroom exercise – it is a microcosm of core AI concepts that appear in real production systems:

AI Concept	How the Water Jug Problem Demonstrates It
State Space Representation in AI	Every (jug1, jug2) pair is a state. The full set of reachable states is the state space – mapping directly to how AI represents any problem.
Search Algorithms in Artificial Intelligence	BFS and DFS are the two foundational uninformed search strategies – both illustrated clearly in the water jug problem.
Goal Testing	Checking if jug1==target or jug2==target is a direct example of AI goal testing – a standard step in any search-based AI problem.
Transition Model	The six operations (fill, empty, pour) define the transition model – a core component of any formal AI problem specification.
Optimality	BFS guarantees optimality (minimum steps); DFS does not – illustrating the trade-off between completeness and efficiency in AI search.
AI Planning	The step-by-step operation sequence required to reach the goal mirrors AI planning systems, where actions must be carefully ordered.

The state space representation in ai built from the water jug problem is identical in structure to the state spaces used in GPS (General Problem Solver), STRIPS planning, and modern reinforcement learning environments – making it an ideal pedagogical bridge between introductory and advanced AI.

Applications of the Water Jug Problem

Ai problem solving examples derived from the water jug problem appear across a surprisingly broad range of real-world domains:

• Puzzle Solving & Algorithm Education: The canonical use – teaching BFS and DFS through a tangible, traceable example. It appears in virtually every AI and algorithms textbook.

• AI Pathfinding: The water jug’s state-transition structure maps directly onto graph-based pathfinding – used in GPS navigation, game AI, and autonomous vehicle route planning.

• Robotics: Robots performing tasks with limited resources (battery levels, cargo capacity, water volume) use decision logic structurally identical to the water jug algorithm.

• Optimization and Resource Allocation: Scheduling systems, supply chain management, and resource distribution algorithms use the same constrained state-space approach to allocate limited resources efficiently.

• Game Development: Puzzle games – from mobile casual games to escape room simulations – use water jug logic as the basis for constraint-satisfaction puzzle design.

• Chemical Process Engineering: Measuring exact volumes of reactants using available containers is a direct real-world instantiation of the water jug problem – used in laboratory automation.

Challenges and Advancements

Key challenges in scaling the water jug problem algorithm:

• State Explosion: As jug capacities increase, the number of unique states grows as O(X×Y) – quickly becoming computationally expensive for large values (X,Y > 1000).

• DFS Inefficiency: DFS may find a valid water jug problem solution through a long, non-optimal path – unsuitable for applications where minimum operations matter.

• Multi-Jug Extension: Extending to 3 or more jugs increases state space dimensionality exponentially – a known NP-hard problem class.

• Real-World Constraints: Physical systems add noise, measurement error, and partial fills – requiring probabilistic extensions to the deterministic model.

Advancements improving the water jug problem algorithm:

• A* Search: Heuristic-guided search dramatically reduces explored states by prioritising states closer to the target – typically faster than plain BFS for large state spaces.

• Dynamic Programming: Memoising sub-problem results avoids redundant computation – useful when solving many water jug instances with the same jug capacities.

• Bidirectional BFS: Searches forward from the initial state and backward from the goal simultaneously – can reduce time complexity to O(b^(d/2)) vs O(b^d) for BFS.

• Constraint Propagation: Combines the GCD mathematical check with search to prune invalid states before exploring them, improving both time and space efficiency.

Conclusion

The water jug problem in ai is a masterclass in foundational ai problem solving examples – compact enough to understand completely, yet rich enough to illustrate state space representation in ai, search algorithms in artificial intelligence, and optimality trade-offs between BFS and DFS.

Key takeaways: the GCD method provides instant mathematical solvability check; BFS guarantees the minimum-step water jug problem solution; DFS is simpler to implement recursively but non-optimal; both have O(X×Y) complexity. The water jug problem in artificial intelligence with example translates directly to pathfinding, robotics, resource allocation, and planning systems.

To deepen your AI expertise with hands-on problem solving, consider the Certificate Program in Artificial Intelligence and Machine Learning offered by Hero Vired.