Program 3: Solve the Water Jug Problem using Breadth First Search (BFS).

from collections import deque

def water_jug_bfs(jugA, jugB, target):
    visited = set()
    queue = deque()
    
    queue.append((0, 0, []))  # state + path
    
    while queue:
        x, y, path = queue.popleft()
        
        if (x, y) in visited:
            continue
        
        visited.add((x, y))
        path = path + [(x, y)]
        
        if x == target or y == target:
            return path
        
        next_states = []
        
        # Fill jugs
        next_states.append((jugA, y))
        next_states.append((x, jugB))
        
        # Empty jugs
        next_states.append((0, y))
        next_states.append((x, 0))
        
        # Pour A -> B
        pour = min(x, jugB - y)
        next_states.append((x - pour, y + pour))
        
        # Pour B -> A
        pour = min(y, jugA - x)
        next_states.append((x + pour, y - pour))
        
        for state in next_states:
            if state not in visited:
                queue.append((state[0], state[1], path))
    
    return None


solution = water_jug_bfs(4, 3, 2)
print("Solution path:")
for step in solution:
    print(step)

from collections import deque

def water_jug_bfs(jugA, jugB, target):
    visited = set()
    queue = deque()
    
    queue.append((0, 0, []))  # state + path
    
    while queue:
        x, y, path = queue.popleft()
        
        if (x, y) in visited:
            continue
        
        visited.add((x, y))
        path = path + [(x, y)]
        
        if x == target or y == target:
            return path
        
        next_states = []
        
        # Fill jugs
        next_states.append((jugA, y))
        next_states.append((x, jugB))
        
        # Empty jugs
        next_states.append((0, y))
        next_states.append((x, 0))
        
        # Pour A -> B
        pour = min(x, jugB - y)
        next_states.append((x - pour, y + pour))
        
        # Pour B -> A
        pour = min(y, jugA - x)
        next_states.append((x + pour, y - pour))
        
        for state in next_states:
            if state not in visited:
                queue.append((state[0], state[1], path))
    
    return None


solution = water_jug_bfs(4, 3, 2)
print("Solution path:")
for step in solution:
    print(step)