Missionaries and Cannibals Problem Using DFS | Python Code

 

def isvalid(c, m):

    if c < 0 or m < 0 or c > 3 or m > 3:

        return False

    if m > 0 and c > m:

        return False

    # Check other side

    m = 3 - m

    c = 3 - c

    if c < 0 or m < 0 or c > 3 or m > 3:

        return False

    if m > 0 and c > m:

        return False

    return True

def get_state(current_state, path):

    m, c, direction = current_state

    next_states = []

    moves = [(1,0), (2,0), (0,1), (0,2), (1,1)]

    if direction == "left":

        for dm, dc in moves:

            new_leftm = m - dm

            new_leftc = c - dc

            if isvalid(new_leftc, new_leftm):

                new_state = (new_leftm, new_leftc, "right")

                action = f"move {dm}M and {dc}C go to right"

                next_states.append((new_state, path + [action]))

    else:

        for dm, dc in moves:

            new_leftm = m + dm

            new_leftc = c + dc

            if isvalid(new_leftc, new_leftm):

                new_state = (new_leftm, new_leftc, "left")

                action = f"move {dm}M and {dc}C go to left"

                next_states.append((new_state, path + [action]))

    return next_states

def dfs():

    initial_state=(3,3,"left")

    stack=[(initial_state,[])]

    vis=set()

    vis.add(initial_state)

    while stack:

        current_state,path=stack.pop()

        if current_state==(0,0,"right"):

            return path

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

            if new_state not in vis:

                stack.append((new_state,new_path))

                vis.add(new_state)

    return None

print("DFS solution  : ")

print(dfs())