Water Jug Problem using DFS | Python Code

 def dfs(jug1,jug2,target):

    vis=set()

    stack=[((0,0),[])]

    vis.add((0,0))

    while stack:

        (a,b),path=stack.pop()

        if a==target or b==target:

            return path

        if (jug1,b) not in vis:

            vis.add((jug1,b))

            stack.append(((jug1,b),path+["fil jug 1"]))

        if (a,jug2) not in vis:

            vis.add((a,jug2))

            stack.append(((a,jug2),path+["fil jug 2"]))

        if (0,b) not in vis:

            vis.add((0,b))

            stack.append(((0,b),path+["empty jug 1"]))

        if (a,0) not in vis:

            vis.add((a,0))

            stack.append(((a,0),path+["empty jug 2"]))

        pour=min(a,jug2-b)

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

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

            stack.append(((a-pour,b+pour),path+["pour jug 2"]))

        pour=min(b,jug1-a)

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

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

            stack.append(((a+pour,b-pour),path+["pour jug 1"]))

    return None  

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

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

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

if dfs(jug1,jug2,target):

    print("this is path :")

    print(dfs(jug1,jug2,target))

else:

    print("No solution found\n")