Missionaries and Cannibals Problem Using BFS | python code

 

from collections import deque

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

    initial_state = (3, 3, 'left')

    queue = deque([(initial_state, [])])

    visited = set()

    visited.add(initial_state)

    while queue:

        current_state, path = queue.popleft()

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

            return path

        for next_state, next_path in get_state(current_state, path):

            if next_state not in visited:

                queue.append((next_state, next_path))

                visited.add(next_state)

    return None

print("Here is the step of this solution using BFS:")

flag = bfs()

if flag:

    for step_num, step in enumerate(flag, 1):

        print(f"{step_num}. {step}")

else:

    print("No solution found.")