/8-Puzzle-Solver-using-BFS-Algorithm

A solver to to find all the possible states of the 8-Puzzle and reach a user defined goal.

Primary LanguagePythonMIT LicenseMIT

8-Puzzle-Solver-using-BFS-Algorithm

Project Description

An instance of the 8-puzzle game consists of a board holding 8 distinct movable tiles ans empty space. For such a board, the empty space may be legally swapped with any tile horizontally or vertically adjacent to it. In this project, we are given an initial state of the puzzle, the search problem is to find a sequence of moves or action that transitions this state to the goal state; that is, the configuration with all tiles arranged in ascending order 0,1,2,3,4,5,6,7,8 or 8,7,6,5,4,3,2,1,0 or any other user defined goal state.

TB3

Objective

Use the Breadth First Search (BFS) Algorithm to solve the 8 puzzle. The slider should swap the empty space with a number to create a unique state. We need to make sure that no state is repeated so as to avoid infinite looping.

  • Breadth First Search (BFS) : It is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node).
  • Action/Move Set : The Action/Move Set that the algorithm uses to generate new states is [up, down, right, left]. Using these actions, the algorithm generates new states at each state and checks whether each new state is the required goal state.
  • Distance Metric : Again, an abstract module to allow re-use, it includes the required distance metric that is Manhattan distance. Here Manhattan Distance is used because the slider either moves up, down, right or left for about one unit and not more than that. It also won't slide in any other angles directions i.e; diagonally.
  • Unique State Checker : We implement a set data structure to store all existing states. We will write an algorithm such that every unique state that is being entered into the set will be compared to all other existing states to avoid repitition.

Contents

    ├── assets
    │   └── images
    ├── nodePath.txt
    ├── Nodes.txt
    ├── NodesInfo.txt
    ├── LICENSE
    ├── README
    └── Solver.py

Instructions

Flowchart of the algorithm

TB3

Steps to run my implementation

  1. Clone the repository
git clone https://github.com/bharadwaj-chukkala/8-Puzzle-Solver-using-BFS-Algorithm.git
  1. Install Python 3.9 and the libraries mentinoned below prior to running the code
  2. Go to the root directory from your IDE.
  3. Please mention the path to the datasets wherever necessary.
  4. Run the Solver.py file as it is.
  5. Nodes.txt will contain all possible states
  6. nodePath.txt will contain the generated path to the goal from initial state
  7. NodesInfo.txt will contain the information about child states, parent states and cost2come
  8. Note: if dataset and results are not given, please paste the py file in the folder where dataset is present and also create a results folder in the directory where you run the code.

Dependencies

  • NumPy
  • argparse

Results

I have defined the initial state and goal state as follows:

Initial State ➡️ Goal State
8 6
5 4 7
2 3 1
should
change to
1 2 3
4 5 6
7 8

License

This project is licensed under the MIT License - see the LICENSE file for details.

Author Contact

Bharadwaj Chukkala
UID: 118341705
Bharadwaj Chukkala is currently a Master's student in Robotics at the University of Maryland, College Park, MD (Batch of 2023). His interests include Machine Learning, Perception and Path Planning for Autonomous Robots.
Contact LinkedIn GitHub