Water Jug Problem Using IDS | Python Code

 

def dls(jug1,jug2,target,limit):

   

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

   

    while stack:

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

        if a==target or b==target:

            return path

        if depth>=limit:

            continue

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

       

       

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

   

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

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

        pour=min(a,jug2-b)

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

        pour=min(b,jug1-a)

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

    return None  

def ids(jug1,jug2,target):

    maxdept=(jug2+1)*(jug1+1)

    for depth in range(maxdept+1):

        ans=dls(jug1,jug2,target,depth)

        if ans:

            return ans

    return None

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

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

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

if ids(jug1,jug2,target):

    print("Solution found")

    print(ids(jug1,jug2,target))

else:

    print("Solution not found\n")