Water Jug Problem Using BFS| Python code

 from collections import deque

def bfs(jug1, jug2, target):

    vis = set()

    q = deque()

    q.append(((0, 0), []))

    vis.add((0, 0))

    while q:

        (a, b), path = q.popleft()

       

        if a == target or b == target:

            path.append((a, b))

            return path

       

       

        if (jug1, b) not in vis:

            vis.add((jug1, b))

            q.append(((jug1, b), path + ['fill jug1']))

     

        if (a, jug2) not in vis:

            vis.add((a, jug2))

            q.append(((a, jug2), path + ['fill jug2']))

       

        if (0, b) not in vis:

            vis.add((0, b))

            q.append(((0, b), path + ['empty jug1']))

   

        if (a, 0) not in vis:

            vis.add((a, 0))

            q.append(((a, 0), path + ['empty jug2']))

       

        pour = min(a, jug2 - b)

        if (a - pour, b + pour) not in vis:

            vis.add((a - pour, b + pour))

            q.append(((a - pour, b + pour), path + ['pour jug1 to jug2']))

     

        pour = min(b, jug1 - a)

        if (a + pour, b - pour) not in vis:

            vis.add((a + pour, b - pour))

            q.append(((a + pour, b - pour), path + ['pour jug2 to jug1']))

    return None

jug1 = int(input("Enter jug 1 capacity: "))

jug2 = int(input("Enter jug 2 capacity: "))

target = int(input("Enter target amount: "))

solution = bfs(jug1, jug2, target)

if solution:

    print("Steps to reach the goal:")

    for step in solution:

        print(step)

else:

    print("No solution found.")