Skip to content
/ famous-search-algorithms-for-missionaries-and-cannibals Public

Implementation of famous search algorithms for Missionaries and Cannibals problem

0 stars 1 fork Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

feknall/famous-search-algorithms-for-missionaries-and-cannibals

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
README.md
README.md
 
 
a_star.py
a_star.py
 
 
best_first.py
best_first.py
 
 
breadth_first.py
breadth_first.py
 
 
common.py
common.py
 
 
depth_first.py
depth_first.py
 
 

Repository files navigation

famous-search-algorithms-for-missionaries-and-cannibals

How to use

Just clone the project and run any file that you want by python.

Output of Depth First

Win! Last state: (0, 0, 'b')
Steps: [(3, 3, 'a'), (3, 1, 'b'), (3, 2, 'a'), (3, 0, 'b'), (3, 1, 'a'), (1, 1, 'b'), (2, 2, 'a'), (0, 2, 'b'), (0, 3, 'a'), (0, 1, 'b'), (0, 2, 'a'), (0, 0, 'b')]
depth: 0, index: 0, state: (3, 3, 'a')
├── depth: 1, index: 0, state: (3, 2, 'b')
└── depth: 1, index: 1, state: (3, 1, 'b')
    └── depth: 2, index: 0, state: (3, 2, 'a')
        └── depth: 3, index: 0, state: (3, 0, 'b')
            └── depth: 4, index: 0, state: (3, 1, 'a')
                └── depth: 5, index: 0, state: (1, 1, 'b')
                    └── depth: 6, index: 0, state: (2, 2, 'a')
                        └── depth: 7, index: 0, state: (0, 2, 'b')
                            └── depth: 8, index: 0, state: (0, 3, 'a')
                                └── depth: 9, index: 0, state: (0, 1, 'b')
                                    └── depth: 10, index: 0, state: (0, 2, 'a')
                                        └── ***** depth: 11, index: 0, state: (0, 0, 'b') *****

Finished! Solution found? True

Output of Breadth First

States: [(3, 3, 'a')]
Current State: (3, 3, 'a')
Future State: (3, 2, 'b')
Future State: (3, 1, 'b')
Future State: (2, 2, 'b')

States: [(3, 2, 'b'), (3, 1, 'b'), (2, 2, 'b')]
Current State: (3, 2, 'b')

Current State: (3, 1, 'b')
Future State: (3, 2, 'a')

Current State: (2, 2, 'b')

States: [(3, 2, 'a')]
Current State: (3, 2, 'a')
Future State: (3, 0, 'b')

States: [(3, 0, 'b')]
Current State: (3, 0, 'b')
Future State: (3, 1, 'a')

States: [(3, 1, 'a')]
Current State: (3, 1, 'a')
Future State: (1, 1, 'b')

States: [(1, 1, 'b')]
Current State: (1, 1, 'b')
Future State: (2, 2, 'a')

States: [(2, 2, 'a')]
Current State: (2, 2, 'a')
Future State: (0, 2, 'b')

States: [(0, 2, 'b')]
Current State: (0, 2, 'b')
Future State: (0, 3, 'a')

States: [(0, 3, 'a')]
Current State: (0, 3, 'a')
Future State: (0, 1, 'b')

States: [(0, 1, 'b')]
Current State: (0, 1, 'b')
Future State: (0, 2, 'a')
Future State: (1, 1, 'a')

States: [(0, 2, 'a'), (1, 1, 'a')]
Current State: (0, 2, 'a')
Future State: (0, 0, 'b')

Current State: (1, 1, 'a')

States: [(0, 0, 'b')]
Current State: (0, 0, 'b')
Win! Last state: (0, 0, 'b')


State Stack:
(3, 3, 'a')
(3, 2, 'b')
(3, 1, 'b')
(2, 2, 'b')
(3, 2, 'a')
(3, 0, 'b')
(3, 1, 'a')
(1, 1, 'b')
(2, 2, 'a')
(0, 2, 'b')
(0, 3, 'a')
(0, 1, 'b')
(0, 2, 'a')
(1, 1, 'a')
(0, 0, 'b')

All States:
[(3, 3, 'a')]
[(3, 2, 'b'), (3, 1, 'b'), (2, 2, 'b')]
[(3, 2, 'a')]
[(3, 0, 'b')]
[(3, 1, 'a')]
[(1, 1, 'b')]
[(2, 2, 'a')]
[(0, 2, 'b')]
[(0, 3, 'a')]
[(0, 1, 'b')]
[(0, 2, 'a'), (1, 1, 'a')]
[(0, 0, 'b')]
Finished!

Output of Best First

Frontiers: [(3, 3, 'a')]
Best State: (3, 3, 'a')
Best Value: 6

Frontiers: [(3, 2, 'b'), (3, 1, 'b'), (2, 2, 'b')]
Best State: (3, 1, 'b')
Best Value: 4

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 3, 'a')]
Best State: (3, 2, 'a')
Best Value: 5

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (3, 0, 'b'), (2, 2, 'b')]
Best State: (3, 0, 'b')
Best Value: 3

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 1, 'a'), (3, 2, 'a')]
Best State: (3, 1, 'a')
Best Value: 4

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (1, 1, 'b')]
Best State: (1, 1, 'b')
Best Value: 2

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (2, 2, 'a'), (3, 1, 'a')]
Best State: (2, 2, 'a')
Best Value: 4

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (3, 1, 'a'), (1, 1, 'b'), (0, 2, 'b')]
Best State: (1, 1, 'b')
Best Value: 2

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (3, 1, 'a'), (0, 2, 'b'), (2, 2, 'a'), (3, 1, 'a')]
Best State: (3, 1, 'a')
Best Value: 4

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (0, 2, 'b'), (2, 2, 'a'), (3, 1, 'a'), (3, 0, 'b'), (1, 1, 'b')]
Best State: (0, 2, 'b')
Best Value: 2

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (2, 2, 'a'), (3, 1, 'a'), (3, 0, 'b'), (1, 1, 'b'), (0, 3, 'a'), (2, 2, 'a')]
Best State: (0, 3, 'a')
Best Value: 3

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (2, 2, 'a'), (3, 1, 'a'), (3, 0, 'b'), (1, 1, 'b'), (2, 2, 'a'), (0, 2, 'b'), (0, 1, 'b')]
Best State: (0, 1, 'b')
Best Value: 1

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (2, 2, 'a'), (3, 1, 'a'), (3, 0, 'b'), (1, 1, 'b'), (2, 2, 'a'), (0, 2, 'b'), (0, 2, 'a'), (0, 3, 'a'), (1, 1, 'a')]
Best State: (0, 2, 'a')
Best Value: 2

Frontiers: [(3, 2, 'b'), (2, 2, 'b'), (3, 3, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'a'), (3, 0, 'b'), (2, 2, 'a'), (3, 1, 'a'), (3, 0, 'b'), (1, 1, 'b'), (2, 2, 'a'), (0, 2, 'b'), (0, 3, 'a'), (1, 1, 'a'), (0, 1, 'b'), (0, 0, 'b')]
Best State: (0, 0, 'b')
Best Value: 0

Win! Last state: (0, 0, 'b')
Finished! Win: True

Output of A*

Frontiers: {(3, 3, 'a')}
Best State: (3, 3, 'a')
Best Value: 6

Frontiers: {(3, 1, 'b'), (2, 2, 'b'), (3, 2, 'b')}
Best State: (3, 1, 'b')
Best Value: 5

Frontiers: {(3, 2, 'a'), (2, 2, 'b'), (3, 2, 'b'), (3, 3, 'a')}
Best State: (3, 2, 'a')
Best Value: 7

Frontiers: {(3, 0, 'b'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'b'), (3, 3, 'a')}
Best State: (3, 0, 'b')
Best Value: 6

Frontiers: {(3, 1, 'a'), (3, 2, 'a'), (3, 1, 'b'), (2, 2, 'b'), (3, 2, 'b'), (3, 3, 'a')}
Best State: (3, 1, 'a')
Best Value: 8

Frontiers: {(1, 1, 'b'), (3, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (3, 3, 'a'), (2, 2, 'b'), (3, 2, 'b')}
Best State: (3, 2, 'b')
Best Value: 6

Frontiers: {(1, 1, 'b'), (3, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (3, 2, 'a')
Best Value: 9

Frontiers: {(1, 1, 'b'), (3, 0, 'b'), (3, 1, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (1, 1, 'b')
Best Value: 7

Frontiers: {(2, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (3, 1, 'a'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (2, 2, 'a')
Best Value: 12

Frontiers: {(1, 1, 'b'), (3, 0, 'b'), (3, 1, 'b'), (3, 1, 'a'), (0, 2, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (3, 0, 'b')
Best Value: 10

Frontiers: {(1, 1, 'b'), (3, 2, 'a'), (3, 1, 'b'), (3, 1, 'a'), (0, 2, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (3, 3, 'a')
Best Value: 12

Frontiers: {(1, 1, 'b'), (3, 2, 'a'), (3, 1, 'b'), (3, 1, 'a'), (3, 2, 'b'), (0, 2, 'b'), (2, 2, 'b')}
Best State: (1, 1, 'b')
Best Value: 11

Frontiers: {(3, 2, 'a'), (2, 2, 'a'), (3, 1, 'b'), (3, 1, 'a'), (3, 2, 'b'), (0, 2, 'b'), (2, 2, 'b')}
Best State: (3, 2, 'a')
Best Value: 15

Frontiers: {(2, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (3, 1, 'a'), (3, 2, 'b'), (0, 2, 'b'), (2, 2, 'b')}
Best State: (0, 2, 'b')
Best Value: 11

Frontiers: {(2, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (3, 1, 'a'), (3, 2, 'b'), (0, 3, 'a'), (2, 2, 'b')}
Best State: (3, 1, 'a')
Best Value: 16

Frontiers: {(2, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (1, 1, 'b'), (3, 2, 'b'), (0, 3, 'a'), (2, 2, 'b')}
Best State: (3, 2, 'b')
Best Value: 16

Frontiers: {(2, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (1, 1, 'b'), (3, 3, 'a'), (0, 3, 'a'), (2, 2, 'b')}
Best State: (0, 3, 'a')
Best Value: 17

Frontiers: {(2, 2, 'a'), (1, 1, 'b'), (3, 0, 'b'), (3, 1, 'b'), (0, 1, 'b'), (0, 2, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (1, 1, 'b')
Best Value: 17

Frontiers: {(2, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (3, 1, 'a'), (0, 1, 'b'), (0, 2, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (2, 2, 'a')
Best Value: 22

Frontiers: {(1, 1, 'b'), (3, 0, 'b'), (3, 1, 'b'), (3, 1, 'a'), (0, 1, 'b'), (0, 2, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (3, 1, 'b')
Best Value: 17

Frontiers: {(1, 1, 'b'), (3, 2, 'a'), (3, 0, 'b'), (3, 1, 'a'), (0, 1, 'b'), (0, 2, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (3, 1, 'a')
Best Value: 22

Frontiers: {(1, 1, 'b'), (3, 2, 'a'), (3, 0, 'b'), (0, 1, 'b'), (0, 2, 'b'), (3, 3, 'a'), (2, 2, 'b')}
Best State: (2, 2, 'b')
Best Value: 17

Frontiers: {(1, 1, 'b'), (3, 2, 'a'), (3, 0, 'b'), (0, 1, 'b'), (0, 2, 'b'), (3, 3, 'a')}
Best State: (3, 2, 'a')
Best Value: 27

Frontiers: {(1, 1, 'b'), (3, 0, 'b'), (2, 2, 'b'), (0, 1, 'b'), (3, 1, 'b'), (0, 2, 'b'), (3, 3, 'a')}
Best State: (0, 1, 'b')
Best Value: 18

Frontiers: {(1, 1, 'b'), (3, 0, 'b'), (2, 2, 'b'), (3, 1, 'b'), (0, 2, 'b'), (3, 3, 'a'), (0, 2, 'a'), (0, 3, 'a'), (1, 1, 'a')}
Best State: (0, 2, 'a')
Best Value: 26

Frontiers: {(1, 1, 'b'), (3, 0, 'b'), (2, 2, 'b'), (0, 0, 'b'), (3, 1, 'b'), (0, 2, 'b'), (3, 3, 'a'), (0, 3, 'a'), (1, 1, 'a'), (0, 1, 'b')}
Best State: (0, 2, 'b')
Best Value: 21

Frontiers: {(2, 2, 'a'), (1, 1, 'b'), (3, 0, 'b'), (3, 1, 'b'), (1, 1, 'a'), (3, 3, 'a'), (0, 0, 'b'), (0, 1, 'b'), (0, 3, 'a'), (2, 2, 'b')}
Best State: (1, 1, 'a')
Best Value: 26

Frontiers: {(2, 2, 'a'), (1, 1, 'b'), (3, 0, 'b'), (3, 1, 'b'), (3, 3, 'a'), (0, 0, 'b'), (0, 1, 'b'), (0, 3, 'a'), (2, 2, 'b')}
Best State: (1, 1, 'b')
Best Value: 23

Frontiers: {(2, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (3, 1, 'a'), (3, 3, 'a'), (0, 0, 'b'), (0, 1, 'b'), (0, 3, 'a'), (2, 2, 'b')}
Best State: (3, 3, 'a')
Best Value: 28

Frontiers: {(2, 2, 'a'), (3, 0, 'b'), (3, 1, 'b'), (3, 1, 'a'), (3, 2, 'b'), (0, 0, 'b'), (0, 1, 'b'), (0, 3, 'a'), (2, 2, 'b')}
Best State: (3, 0, 'b')
Best Value: 26

Frontiers: {(2, 2, 'a'), (3, 1, 'b'), (3, 1, 'a'), (3, 2, 'b'), (3, 2, 'a'), (0, 0, 'b'), (0, 1, 'b'), (0, 3, 'a'), (2, 2, 'b')}
Best State: (0, 3, 'a')
Best Value: 29

Frontiers: {(2, 2, 'a'), (3, 1, 'b'), (3, 1, 'a'), (3, 2, 'b'), (3, 2, 'a'), (0, 0, 'b'), (0, 1, 'b'), (0, 2, 'b'), (2, 2, 'b')}
Best State: (0, 0, 'b')
Best Value: 27

Win state: (0, 0, 'b')
Win!
Finished! Win: True

About

Implementation of famous search algorithms for Missionaries and Cannibals problem

Topics

artificial-intelligence search-algorithm breadth-first-search depth-first-search path-finding best-first-search a-start missionaries-cannibals-problem

Resources

Readme
Activity

Stars

0 stars

Watchers

1 watching

Forks

1 fork
Report repository

Releases

No releases published

Packages

No packages published

Languages