Missionaries and Cannibals Python Ai | PDF | Algorithms And Data Structures | Algorithms
Scribd
Upload
2K views

Missionaries and Cannibals Python Ai

The document describes implementing the missionaries-cannibals problem in Python. It involves three missionaries and three cannibals crossing a river using a small boat that can carry at most two people at a time, ensuring the missionaries are never outnumbered by cannibals on either side of the river. The solution uses a depth-first search algorithm with a State class to track states and get successor states by moving people and the boat. The code provided implements this solution to find the path to get all missionaries and cannibals across the river safely.

Uploaded by

21131A4433 MUTHA RESHMIKA
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
2K views

Missionaries and Cannibals Python Ai

The document describes implementing the missionaries-cannibals problem in Python. It involves three missionaries and three cannibals crossing a river using a small boat that can carry at most two people at a time, ensuring the missionaries are never outnumbered by cannibals on either side of the river. The solution uses a depth-first search algorithm with a State class to track states and get successor states by moving people and the boat. The code provided implements this solution to find the path to get all missionaries and cannibals across the river safely.

Uploaded by

21131A4433 MUTHA RESHMIKA
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

WEEK 16

Aim: To write a Program to Implement Missionaries-


Cannibals Problems using Python.
Description:
In the missionaries and cannibals’ problem, three missionaries and
three cannibals must cross a river using a boat which can carry at
most two people, under the constraint that, for both banks, if there are
missionaries present on the bank, they cannot be outnumbered by
cannibals (if they were, the cannibals would eat the missionaries). The
boat cannot cross the river by itself with no people on board.
Solution:
First let us consider that both the missionaries (M) and cannibals(C)
are on the same side of the river. Left Right Initially the positions are :
0M , 0C and 3M , 3C (B) Now let’s send 2 Cannibals to left of bank :
0M , 2C (B) and 3M , 1C Send one cannibal from left to right : 0M ,
1C and 3M , 2C (B) Now send the 2 remaining Cannibals to left : 0M
, 3C (B) and 3M , 0C Send 1 cannibal to the right : 0M , 2C and 3M ,
1C (B) Now send 2 missionaries to the left : 2M , 2C (B) and 1M . 1C
Send 1 missionary and 1 cannibal to right : 1M , 1C and 2M , 2C (B)
Send 2 missionaries to left : 3M , 1C (B) and 0M , 2C Send 1 cannibal
to right : 3M , 0C and 0M , 3C (B) Send 2 cannibals to left : 3M , 2C
(B) and 0M , 1C Send 1 cannibal to right : 3M , 1C and 0M , 2C (B)’
Send 2 cannibals to left : 3M , 3C (B) and 0M , 0C • Here (B) shows
the position of the boat after the action is performed. Therefore, all the
missionaries and cannibals have crossed the river safely.
This is the game where you must try to solve the problem with
minimum number of attempts
Python code:
class State:
def __init__(self, missionaries, cannibals, boat):
self.missionaries = missionaries
self.cannibals = cannibals
self.boat = boat

def is_valid(self):
if self.missionaries < 0 or self.cannibals < 0 or
self.missionaries > 3 or self.cannibals > 3:
return False
if self.missionaries < self.cannibals and self.missionaries >
0:
return False
if 3 - self.missionaries < 3 - self.cannibals and 3 -
self.missionaries > 0:
return False
return True

def is_goal(self):
return self.missionaries == 0 and self.cannibals == 0

def _eq_(self, other):


return (
self.missionaries == other.missionaries
and self.cannibals == other.cannibals
and self.boat == other.boat
)

def _hash_(self):
return hash((self.missionaries, self.cannibals, self.boat))

def get_successors(current_state):
successors = []
actions = [(1, 0), (2, 0), (0, 1), (0, 2), (1, 1)]
for action in actions:
new_state = State(
current_state.missionaries - action[0] *
current_state.boat,
current_state.cannibals - action[1] * current_state.boat,
1 - current_state.boat,
)
if new_state.is_valid():
successors.append(new_state)
return successors
def depth_first_search():
initial_state = State(5, 1, 1)
goal_state = State(0, 0, 0)
visited = set()
stack = [[initial_state]]

while stack:
path = stack.pop()
current_state = path[-1]

if current_state in visited:
continue

visited.add(current_state)

if current_state.is_goal():
return path

successors = get_successors(current_state)
for successor in successors:
if successor not in visited:
new_path = list(path)
new_path.append(successor)
stack.append(new_path)

return None

def print_solution(solution):
for i, state in enumerate(solution):
print(f"Step {i + 1}: Missionaries={state.missionaries},
Cannibals={state.cannibals}, Boat={state.boat}")

if __name__ == "__main__":
solution_path = depth_first_search()
if solution_path:
print("Solution found!")
print_solution(solution_path)
else:
print("No solution found.")
Output:
Solution found!
Step 1: Missionaries=5, Cannibals=1, Boat=1
Step 2: Missionaries=3, Cannibals=1, Boat=0
Step 3: Missionaries=3, Cannibals=1, Boat=1
Step 4: Missionaries=1, Cannibals=1, Boat=0
Step 5: Missionaries=1, Cannibals=1, Boat=1
Step 6: Missionaries=0, Cannibals=0, Boat=0

You might also like