Farmer, Goat, Cabbage, and Tiger Problem Using DLS | Python Code

 

def is_valid(new_state):

    f,g,c,t=new_state

    if g==t and g!=f:

        return False

    if g==c and c!=f:

        return False

    return True

def get_state(cur_state,path):

    f,g,c,t=cur_state

    next_state=[]

    move=[None, 'goat', 'cabbage', 'tiger']

    newf="left"

    if(f=="left"):

        newf="right"

    for item in move:

        newg,newc,newt=g,c,t

        if item=="goat":

            if f!=g:

                continue

            newg=newf

        elif item=="cabbage":

            if f!=c:

                continue

            newc=newf

        elif item=="tiger":

            if t!=f:

                continue

            newt=newf

        new_state=(newf,newg,newc,newt)

        if is_valid(new_state):

            ac=f"Move {item} to {newf}" if item else f"Farmer go alone to {newf}"

            next_state.append((new_state,path+[ac]))

    return next_state

def dls(limit):

    state=('left','left','left','left')

    final_state=('right','right','right','right')

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

    vis=set()

    vis.add(state)

    while stack:

        cur_state,path,depth=stack.pop()

        if(cur_state==final_state):

            return path

        if depth>=limit:

            continue

        for new_state,new_path in reversed(get_state(cur_state,path)):

            if new_state not in vis:

                vis.add(new_state)

                stack.append((new_state,new_path,depth+1))

    return None

   

print("DLS Solution")

print(dls(10))