The SlidingPuzzleSolver is a C++ project designed to solve sliding puzzles, such as the 4x4 puzzle where the goal is to arrange the tiles in a specific order with the empty space denoted by 0
. This solver reads puzzle configurations from input.txt
and outputs the steps required to solve the puzzle in output.txt
. Some complex puzzles might not be solvable within practical time or memory limits.
The SlidingPuzzleSolver utilizes the A* (A-star) search algorithm, which is a popular and efficient pathfinding and graph traversal algorithm. Here's a detailed explanation of how it works in this project:
-
Initialization:
- The algorithm starts with the initial configuration of the puzzle read from
input.txt
.
- The algorithm starts with the initial configuration of the puzzle read from
-
Priority Queue:
- A priority queue is used to explore the most promising paths first. The priority is determined by a cost function
f(n) = g(n) + h(n)
, where:g(n)
is the cost to reach the current state from the initial state (i.e., the number of moves taken so far).h(n)
is the heuristic estimate of the cost to reach the goal state from the current state. In this case, the heuristic is the sum of the Manhattan distances of the tiles from their goal positions.
- A priority queue is used to explore the most promising paths first. The priority is determined by a cost function
-
Expansion:
- The algorithm expands the most promising node by generating its neighboring nodes (possible moves in the puzzle). The new Manhattan distance is calculated for each neighboring state.
-
Goal Check:
- If the current node represents the goal state (Manhattan distance is 0), the algorithm terminates and returns the solution path.
-
Loop:
- This process continues until the goal state is found or there are no more nodes to explore.
- Input: The puzzle configuration should be provided in
input.txt
, where the empty space is denoted by0
. - Output: The steps to solve the puzzle will be written to
output.txt
.
- Visual Studio (preferably the latest version)
- C++ compiler
-
Clone the Repository
git clone https://github.com/tbtiberiu/SlidingPuzzleSolver.git cd SlidingPuzzleSolver
-
Open in Visual Studio
- Launch Visual Studio.
- Open the project by navigating to
File > Open > Project/Solution
and select theSlidingPuzzleSolver.sln
file.
-
Build the Project
- In the Solution Explorer, right-click on the
SlidingPuzzleSolver
project and selectBuild
.
- In the Solution Explorer, right-click on the
-
Run the Project
- Ensure
input.txt
is in the same directory as the executable or provide the path to the file in the code. - Run the project by pressing
F5
or selectingDebug > Start Debugging
.
- Ensure
Input (input.txt
):
3
3 5 2
1 0 4
8 6 7
Output (output.txt
):
Move 0 (START):
3 5 2
1 4
8 6 7
Move 1 (DOWN):
Moved space from (1, 1) to (2, 1).
3 5 2
1 6 4
8 7
...
Move 22 (DOWN):
Moved space from (1, 2) to (2, 2).
1 2 3
4 5 6
7 8
The main components of the solver are as follows:
State Struct: Represents the state of the puzzle, including the size, body (tiles), and the coordinates of the empty space.
Node Struct: Represents a node in the search tree, including the state, level (number of moves from the initial state), Manhattan sum (heuristic), move (the move that led to this state), and a pointer to the parent node.
Functions:
clearFile
: Clears the output file.readState
: Reads the initial puzzle state from the input file.writeState
: Writes the current state to the output file.printList
: Prints the sequence of moves to solve the puzzle.getInitialManhattanDistance
: Computes the initial Manhattan distance for the given state.isSolvable
: Checks if the puzzle is solvable.generateNewStates
: Generates new states from the current state and pushes them onto the priority queue.
Memory or Time Limits: Some puzzles might be too complex to solve within practical limits. Try a simpler configuration.
Compilation Errors: Ensure all dependencies are correctly configured in Visual Studio. This project uses the ISO C++20 Language Standard.