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. And, in some variations, one of the cannibals has only one arm and cannot row.[1]
In this repo I'll be building state space tree upto certain depth and use BFS and DFS to find the solution space tree for Missionaries and Cannibal Problem. To build the tree I'll be using pydot which is a Python wrapper for graphviz.
emoji==0.5.4
pydot==1.4.1
Graphviz Binary Download graphviz https://www.graphviz.org/download/
- Download graphviz binary
- Open solve.py and update the directory to point graphviz bin directory
# Set it to bin folder of graphviz
os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin/'
- Install all the requirements
pip install -r requirements.txt
python generate_full_space_tree.py -d 20
where d is the depth.
- For dfs without legends on graph run
python main.py -m dfs
- For dfs with legends on graph run
python main.py -m dfs -l True
- For bfs without legends on graph run
python main.py -m bfs
- For bfs with legends on graph run
python main.py -m bfs -l True
- The state space tree are saved as bfs.png and dfs.png or bfs_legend.png and dfs_legend.png or state_space{depth}.png in the current directory. The solution moves are displayed on console as in solution.
You can change the order of self.options following line inside solve.py or options inside generate_full_space_tree.py to get different state space tree.
self.options = [(0, 1), (0, 2), (1, 0), (1, 1), (2, 0),]
Windows cmd doesnt support emoji as of now. Try running on bash or terminal to see the graphics properly.
