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

 

from collections import deque

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 bfs():

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

    goal_state=('right','right','right','right')

    q=deque([(state,[])])

    vis=set()

    vis.add(state)

    while q:

        cur_state,path=q.popleft()

        if cur_state==goal_state:

            return path

        for next_state,newpath in get_state(cur_state,path):

            if next_state not in vis:

                vis.add(next_state)

                q.append((next_state,newpath))

    return None

print("BFS solutions for Farmer, Goat, Cabbage, and Tiger Problem ")

print(bfs())