Water Jug Problem in AI: Definition, Solution, and Python Code

Python Implementation of the Water Jug Problem

The following Python program uses BFS to find a path from (0, 0) to a state where the 4-liter jug contains 2 liters.

from collections import deque


def get_next_states(x, y):
    """Return every valid state reachable in one action."""

    states = {
        (4, y),  # Fill the 4-liter jug
        (x, 3),  # Fill the 3-liter jug
        (0, y),  # Empty the 4-liter jug
        (x, 0),  # Empty the 3-liter jug
    }

    # Pour from the 4-liter jug into the 3-liter jug
    transfer = min(x, 3 - y)
    states.add((x - transfer, y + transfer))

    # Pour from the 3-liter jug into the 4-liter jug
    transfer = min(y, 4 - x)
    states.add((x + transfer, y - transfer))

    return states


def solve_water_jug():
    start_state = (0, 0)
    queue = deque([(start_state, [start_state])])
    visited = {start_state}

    while queue:
        current_state, path = queue.popleft()
        x, y = current_state

        if x == 2:
            return path

        for next_state in get_next_states(x, y):
            if next_state not in visited:
                visited.add(next_state)
                queue.append((next_state, path + [next_state]))

    return None


solution = solve_water_jug()

if solution:
    for state in solution:
        print(state)
else:
    print("No solution found.")

The program generates all valid states that can be reached from the current state. It adds unexplored states to the queue and continues until x equals 2.

One possible output is:

(0, 0)
(0, 3)
(3, 0)
(3, 3)
(4, 2)
(0, 2)
(2, 0)

Conclusion

The water jug problem is an example of how a basic puzzle problem can be transformed into a structured search problem by using AI. An algorithm can systematically explore solutions rather than trial and error if it defines the initial state, goal condition, available actions, and possible transitions. These principles can also be applied to more complex applications such as planning, pathfinding, and automated decision-making. 

To develop these foundations further, explore our Microsoft AI Engineer Course. The program covers Python, machine learning, deep learning, NLP, generative AI, agentic AI, and intelligent automation through live training and hands-on projects, helping learners progress from core AI concepts to building practical AI-powered solutions.

FAQs

1. What's the smallest number of steps required to solve the 4-liter and 3-liter water jug problem?

Here are the six operations that can be performed to achieve 2 liters: Fill the 3-liter jug, pour from the 3-liter into the 4-liter jug, refill the 3-liter jug, pour from the 3-liter into the 4-liter jug until full, empty the 4-liter jug, and pour the remaining 2 liters into the 4-liter jug. BFS can verify that this is the shortest path from the initial state to the goal state (2, 0).

2. What is the search tree like in the water jug problem?

The search tree indicates the sequence of the problem from one state to another. The initial state (0, 0) is the root, and branches indicate valid actions like filling, emptying, or pouring. Search algorithms try out these branches until they arrive at a state in which 2 liters are in the 4-liter jug.

3. What are some real-world applications of the water jug problem?

The water jug problem is used primarily to learn the concept of state space search and problem-solving in AI. The same approach is used in robot path planning, solving games, scheduling workflows, and allocating resources in robot navigation. In both instances, an artificial intelligence system is provided with a set of potential actions. Then it seeks a way to traverse from its current position to a specified end state.