subangkar / missionaries-and-cannibals-problem-python Goto Github PK

The missionaries and cannibals problem, which is a famous problem in AI, is usually stated as follows. Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place.

Here the problem formulation has been solved by BFS and the DFS search strategy.

This implementation is able to deal with a scaled-up version of this problem (for example, a problem with five missionaries and five cannibals). The implementation can have m number of missionaries, c number of cannibals, k number of maximum allowable passengers in the boat. There is a search cut-off limit (for example, termination after 30 seconds, or after 1,000,000 nodes have been expanded) which has been passed as input via "in.txt".

Run "main.py"(in Python3)
Input format("in.txt"):

Line1: m
Line2: c
Line3: k
Line4: TIME_LIMIT_IN_SECONDS
Line5: NO_OF_EXPLORED_NODES_LIMIT

Output:
"outBFS.txt" contains the output generated by Breadth First Search and
"outDFS.txt" contains the output generated by Depth First Search.

This solution is implemented as part of an assignment of Artificial Intelligence Sessional course of Undergrad CS curriculam of department of CSE, BUET.

Contributor: Subangkar Karmaker Shanto