Build with ❤️ by VIKAS PANDEY
Explore the docs »
SquareX-Puzzle is an interactive project that takes a square sliding puzzle board as input and uses a breadth-first search(BFS) algorithm to find the minimum number of moves required to reach the final state.
The project provides a user-friendly interface where users can input their puzzle and obtain the number of moves required to solve it and how to make a move.
The project is written in C++ and designed to be easily adaptable to other languages. SquareX-Puzzle is a great example of an algorithmic problem solving project and a useful tool for anyone interested in studying search algorithms.
➤ Getting started with SquareX-Puzzle:
Clone the repository:
git clone https://github.com/iamprofessor1/SquareX-Puzzle.git➤ Navigate to the project directory:
cd SquareX-Puzzle➤ Compile the code:
g++ puzzleSolver.cpp -o puzzleSolver➤ Run the program:
./puzzleSolver➤ Enter the puzzle configuration:
Output:-
---***---Welcome to SquareXPuzzle-Game Solver---***----
? Please Enter the size of board in the form of N X NInput:-
3 3Output:-
The board size is 3 X 3
? Enter the boardInput:-
3 8 5
0 7 1
2 6 4Output:-
---***---Now pick a choice by which you want to solve---***----
? Enter 1 for BFS and 2 for A*(Star)➤ Wait for the program to calculate the solution:
BFS
Congratulations! We've found the solution using BFS!
You'll be happy to know that it only took us 17 moves to get there! :)
This is puzzle you have given :-
Move no :- 0
[ 7 5 4 ]
[ 0 3 2 ]
[ 8 1 6 ]
Move no :- 1
[ 0 5 4 ]
[ 7 3 2 ]
[ 8 1 6 ]
Move no :- 2
[ 5 0 4 ]
[ 7 3 2 ]
[ 8 1 6 ]
Move no :- 3
[ 5 4 0 ]
[ 7 3 2 ]
[ 8 1 6 ]
...
...
...
Move no :- 16
[ 1 2 3 ]
[ 4 5 0 ]
[ 7 8 6 ]
Move no :- 17
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 0 ]
Time taken to execute using the approach BFS :-> 2.172 seconds
Note: The program uses the BFS algorithm to find the solution. It may take a while to compute the solution for larger puzzle configurations.
A Star
Congratulations! We've found the solution using A* ( A_star)!
You'll be happy to know that it only took us 23 moves to get there! :)
This is puzzle you have given :-
Move no :- 0
[ 3 8 5 ]
[ 0 7 1 ]
[ 2 6 4 ]
Move no :- 1
[ 3 8 5 ]
[ 7 0 1 ]
[ 2 6 4 ]
Move no :- 2
[ 3 8 5 ]
[ 7 1 0 ]
[ 2 6 4 ]
Move no :- 3
[ 3 8 5 ]
[ 7 1 4 ]
[ 2 6 0 ]
Move no :- 4
[ 3 8 5 ]
[ 7 1 4 ]
[ 2 0 6 ]
...
...
...
Move no :- 22
[ 1 2 3 ]
[ 4 5 0 ]
[ 7 8 6 ]
Move no :- 23
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 0 ]
Time taken to execute using the approach A*(A_star) :-> 0.047 secondsThe struct named "StateNode" has the following properties:
- "blank" and "next" are the coordinates of the blank tile and the next tile to move.
- "level" represents the depth of the StateNode in the search tree.
- "n" is the size of the board (i.e., n x n).
- "board" is a vector of vector of integers representing the board configuration.
- "parent" is a pointer to the parent StateNode.
This code performs a BFS (breadth-first search) algorithm to solve the puzzle. It takes in the initial state of the puzzle as a StateNode struct and the final state of the puzzle as a vector<vector> board_final. It creates a queue to store the states of the puzzle, starts with the initial state, and iterates through each possible movement of the blank tile until it reaches the final state or the queue is empty.
If the final state is reached, it prints the number of moves required to reach the solution state and calls the print_solution() function to print the solution. If no solution is found, it prints an error message.
The code also includes a visited map to keep track of already visited states and avoids repeating them.
This code implements the A* algorithm to solve puzzles by efficiently navigating through possible states. Key components include:
Heuristic Function: The algorithm employs a heuristic function,(the Manhattan distance), to estimate the cost from a state to the goal state. This guides the search process and helps in choosing the most promising states.
Priority Queue: A priority queue is utilized to prioritize the exploration of states based on their combined cost and level. The goal is to minimize the overall cost to reach the solution.
State Modeling: The state of the puzzle is modeled using a StateNode structure. This structure holds information about the puzzle's configuration, including tile positions, board size, and associated costs.
Exploration and Backtracking: The algorithm explores potential states, considering possible moves and calculating heuristic costs. Backtracking is employed when certain states are found to be unsuitable.
Solution Path Printing: Upon finding a solution, the algorithm prints the path from the initial state to the goal state. This allows for clear visualization of the sequence of moves leading to the solution.
The A_Star function encapsulates the A* algorithm logic, while the Heuristics.h and solutionPrinter.h headers provide essential components for cost estimation and solution visualization, respectively.
The A* algorithm presented in this code offers a versatile and effective method to solve various types of puzzles and optimization problems efficiently.
This is the header file for the solution printer module. It includes the header file for state modeling and declares a function print_solution that prints the solution path for the given puzzle. The function takes a pointer to the current state node as input and prints the board configurations along with the move number. The solution path is printed in reverse order using a stack to store the StateNodes.
The function print_solution uses a loop to pop StateNodes from the stack and print the board configuration and move number. If it is the first iteration of the loop, it prints a message to indicate that the puzzle provided by the user is being printed. The board configuration is printed row-wise, and each element of the board is separated by a space. The board configuration is enclosed in square brackets, and each row is enclosed in a pair of curly braces. Finally, the function prints a blank line after each board configuration to make it easier to read.
The header file is protected by the #ifndef and #endif preprocessor directives to prevent multiple inclusions of the header file in the same translation unit.
The program takes the size of the board and the initial configuration of the board as input from a file named inputPuzzle.txt. It then creates the final configuration of the board and generates an initial StateNode object. Finally, it passes the initial StateNode object and the final board configuration to the bfs function for finding the solution to the puzzle. The bfs function uses a queue and a map data structure to keep track of the visited states and to perform the BFS algorithm. The StateNode struct is used to represent a state in the puzzle. It contains the current board configuration, the position of the blank tile, the position of the next tile to move, the depth of the state in the search tree, and a pointer to the parent state. The StateNode struct also has a constructor that initializes the board configuration after swapping the blank tile with the next tile to move.
The program sets the input and output files to inputPuzzle.txt and outputSolution.txt, respectively. It also sets I/O operations to run faster by using the ios_base::sync_with_stdio(0) function.
The file named inputPuzzle.txt contains the input for the puzzle solver program. The first line of the file contains a single integer, which represents the size of the board (i.e., n x n). The next n lines represent the initial configuration of the board. Each line contains n integers separated by spaces, where each integer represents a tile in the board. The number 0 represents the blank tile
The time complexity of the implemented puzzle solver using the Breadth-First Search (BFS) algorithm depends on the size of the board, represented as n x n, and the number of states generated during the search.
The number of states generated in the worst case for the n-puzzle problem can be bounded by the branching factor raised to the depth of the search tree. In the case of the n-puzzle, the maximum branching factor can be 4 (the number of possible moves for the blank tile). The depth of the search tree can be up to n^2, which is the number of tiles on the board.
Therefore, the worst-case time complexity of the algorithm can be expressed as O(4^(n^2)) , which is exponential in terms of the size of the board.
However, in practice, the number of states generated during the search is much less than the upper bound. This is because the BFS algorithm explores the search space in a breadth-first manner, which means that it visits all the nodes at a given depth before moving to the next level. Hence, the number of nodes generated at a given depth is much less than the maximum branching factor raised to the depth.
Moreover, the implemented algorithm uses a hash map to store the visited nodes and to avoid revisiting them. This reduces the number of nodes generated during the search, especially when dealing with larger boards.
Therefore, the actual time complexity of the algorithm is significantly lower than the upper bound and can be considered reasonable for solving practical instances of the n-puzzle problem.
The time complexity of the A* algorithm depends on the branching factor (maximum possible moves from a state), the depth of the solution (minimum moves to reach the goal), and the accuracy of the heuristic function (estimating cost to the goal).
In general terms, its time complexity is usually expressed as O(B^d), where B is the branching factor and d is the depth of the solution. With an admissible heuristic, the time complexity can be tighter, often O(B^h)* where h* is the optimal cost.
Contributions are always welcome! If you have any ideas or suggestions, feel free to open an issue or a pull request.
if (youEnjoyed) {
starThisRepository();
}