Water Jug Problem in AI — An Exploration with Python | 2023

A Simple Understanding of Water Jug Problem in AI | Karthikeyan Nagaraj

I just came across the topic of the water jug problem in my class and I wanted to share it with the Community of AI People Incorporated with a python program to Solve the Problem in a General Manner

Problem:

You are given with 2 Jugs, 4 Gallon and a 3 Gallon one. Neither of the jugs has any Measuring marks on it. There is a pump that can be used to fill the jugs with water. How can we get exactly 2 Gallons of water in 4 Gallon Jug?

Introduction:

• Water Jug Problem is a classic problem in Artificial Intelligence (AI) that involves finding a way to measure specific amounts of water using two jugs with different capacities.
• The goal is to reach a specific target amount of water in one of the jugs, without exceeding its capacity, by transferring water from one jug to another.
• This problem can be solved using a state space search algorithm.

State Space Search:

• State space search is a technique used in AI to find the solution to a problem by searching through the state space of a problem.
• In this approach, the problem is represented as a graph with nodes as states and edges as transitions.
• The search algorithm starts at an initial state and explores the graph to reach the goal state.
• In the water jug problem, the state space can be represented as a tuple (x, y) where x and y are the amounts of water in the two jugs.
• The initial state is (0, 0) and the goal state is (x, y) or In my case, it is (2, y) where x and y are the desired amounts of water.

Production Rules:

Production rules, also known as rules or heuristics, are used in state space searches to define the actions that can be taken to move from one state to another. In the water jug problem, there are six possible actions:

1. Fill the first jug to its capacity.
2. Fill the second jug to its capacity.
3. Empty the first jug.
4. Empty the second jug.
5. Pour water from the first jug to the second jug until either the first jug is empty or the second jug is full.
6. Pour water from the second jug to the first jug until either the first jug is full or the second jug is empty.

Algorithm:

The algorithm to solve the water jug problem using state space search can be outlined as follows:

1. Represent the problem as a state space graph with nodes as states and edges as transitions.
2. Initialize the open list with the initial state (0, 0).
3. Repeat the following steps until the open list is empty:

• a. Choose a state from the open list and remove it from the list.
• b. If the state is the goal state, return the solution.
• c. Otherwise, generate all possible successor states using the production rules and add them to the open list if they have not been visited before.

4. If the goal state is not reached, return failure.

Python Program to Solve the Problem

Here is a Python program that implements the algorithm to solve the water jug problem:

def water_jug_problem(capacity1, capacity2, target):
    # initial state (x, y) where x and y are the amounts of water in the two jugs
    state = (0, 0)
    parent = {}
    frontier = [state]
    while frontier:
        state = frontier.pop(0)
        if state == (target, 0) or state == (0, target):
            # goal state reached
            path = [state]
            while state in parent:
                state = parent[state]
                path.append(state)
            path.reverse()
            return path
        x, y = state
        # generate all possible successor states
        states = [(capacity1, y), (x, capacity2), (0, y), (x, 0), (min(x + y, capacity1), max(0, x + y - capacity1)), (max(0, y + x - capacity2), min(y + x, capacity2))]
        for new_state in states:
            if new_state not in parent:
                parent[new_state] = state
                frontier.append(new_state)
    return None

# example
capacity1 = 4
capacity2 = 3
target = 2
path = water_jug_problem(capacity1, capacity2, target)
if path is None:
    print("No solution found.")
else:
    for state in path:
        print(state)

Explanation:

1. The program starts by initializing the state space graph with the initial state (0, 0) and the open list with the initial state.
2. The while loop continues until the open list is empty or the goal state is reached.
3. In each iteration, the state with the lowest cost is removed from the open list and checked against the goal state.
4. If it is the goal state, the solution is returned as a list of states.
5. If the goal state is not reached, the program generates all possible successor states using the production rules and adds them to the open list if they have not been visited before.
6. The parent dictionary is used to keep track of the parent state for each new state.

Conclusion:

• The water jug problem can have multiple solutions, and the program returns one of them.
• The time complexity of the algorithm is exponential, so it may take a long time to find the solution for large problems.
• However, it is guaranteed to find the optimal solution, if one exists.

Feel Free to Ask Queries via LinkedIn and to Buy me a Coffee : )

Thank you for Reading!!

Happy Programming ~

Author: Karthikeyan Nagaraj ~ Cyberw1ng