Breadth First Search

What is BFS?

Breadth-first search (BFS) is a graph traversal algorithm that starts at a given vertex (often called the root) of a graph and explores all the vertices at the same level before moving on to the next level.

ENPM661 – 8 Puzzle Project

• GitHub

1. Find all the possible states of the 8-puzzle starting from the given initial node until the goal node. Note that states should be unique.

2. From the initial state, use different moves in all directions to generate new states, and check the validity of the newly generated node.

3. Implement backtracking to find the plan to solve the problem

The sample iterations look like this:

In this project, we are supposed to have the following nodes:

• Node_State_i: The state of node i is represented by a 3 by 3 matrix, for example [ 1 2 3; 4 5 6; 7 8 0]
• Node_Index_i: The index of node i
• Parent_Node_Index_i: The index of the parent for node i

Run the code using the following:

python3 main.py

# for visualization
python3 plot_path.py

The final output for specific nodes of the set :

start_state = [1,6,7], [2,0,5], [4,3,8]
goal_status = [1,4,7], [2,5,8], [3,0,6]

The output of plot_path.py is as follows:

Start Node
-------------
| 1 | 2 | 4 |
-------------
| 6 | 0 | 3 |
-------------
| 7 | 5 | 8 |
-------------

Step  2
-------------
| 0 | 2 | 4 |
-------------
| 1 | 6 | 3 |
-------------
| 7 | 5 | 8 |
-------------

Step  3
-------------
| 2 | 0 | 4 |
-------------
| 1 | 6 | 3 |
-------------
| 7 | 5 | 8 |
-------------


Step  4
-------------
| 2 | 4 | 0 |
-------------
| 1 | 6 | 3 |
-------------
| 7 | 5 | 8 |
-------------


Step  5
-------------
| 2 | 4 | 3 |
-------------
| 1 | 6 | 0 |
-------------
| 7 | 5 | 8 |
-------------


Step  6
-------------
| 2 | 4 | 3 |
-------------
| 1 | 0 | 6 |
-------------
| 7 | 5 | 8 |
-------------


Step  7
-------------
| 2 | 0 | 3 |
-------------
| 1 | 4 | 6 |
-------------
| 7 | 5 | 8 |
-------------


Step  8
-------------
| 0 | 2 | 3 |
-------------
| 1 | 4 | 6 |
-------------
| 7 | 5 | 8 |
-------------


Step  9
-------------
| 1 | 2 | 3 |
-------------
| 0 | 4 | 6 |
-------------
| 7 | 5 | 8 |
-------------


Step  10
-------------
| 1 | 2 | 3 |
-------------
| 4 | 0 | 6 |
-------------
| 7 | 5 | 8 |
-------------


Step  11
-------------
| 1 | 2 | 3 |
-------------
| 4 | 5 | 6 |
-------------
| 7 | 0 | 8 |
-------------


Step  12
-------------
| 1 | 2 | 3 |
-------------
| 4 | 5 | 6 |
-------------
| 7 | 8 | 0 |
-------------


Achieved Goal Node
-------------
| 1 | 2 | 3 |
-------------
| 4 | 5 | 0 |
-------------
| 7 | 8 | 6 | 
-------------