8-Puzzle

The following searach algorithms are implemented:

• Breadth-first search
• Depth-first search
• Iterative deepening DFS search
• Uniform-Cost search
• Best-first search, h = number of tiles that are not it correct position
• A*1 search, h = number of tiles that are not it correct position
• A*2 search, h = sum of Manhattan distances between all tiles and their correct positions
• A*3 search, h = fair Manhattan distance

Example:

Initial state
[1 2 3]
[8 6 4]
[7 5 0]
action= None , depth= 0

step 1
[1 2 3]
[8 6 4]
[7 0 5]
action= move 5 to the right , depth= 1

step 2
[1 2 3]
[8 0 4]
[7 6 5]
action= move 6 down , depth= 2. Goal state found