I built this Python solver and visualizer for the classic 8-puzzle sliding tile problem as a project during my master’s. The system uses a Breadth-First Search (BFS) algorithm to find the optimal solution, handles state deduplication with hash sets, and features a custom Pygame rendering pipeline to animate the result. The complete codebase is available on GitHub: GitHub Repository.
Initial vs. Target State
Solution Playback
Demonstration of the Pygame visualizer stepping through the reconstructed solution sequence.
Technical Details
| Component | Mechanism | Practical Implementation |
|---|---|---|
| Search Algorithm | Breadth-First Search (BFS) | Guarantees the shortest path on an unweighted state graph. |
| State Space Size | 181,440 reachable states ($9! / 2$) | Only half of the permutations are mathematically solvable due to parity constraints. |
| Visited States | Hash-Set Lookup ($O(1)$) | I flattened the 3x3 boards into immutable 9-tuples to prevent the search from looping. |
| Branching Factor ($b$) | $2 \le b \le 4$ moves per state | The system checks the grid boundaries dynamically before moving the empty “0” tile. |
| Data Output | File-backed pipeline | The solver writes the results out to text files (nodePath.txt, etc.) so the visualizer can run independently. |
| Rendering | Pygame 2D Graphics | A simple 300×300 window mapping the text arrays into a visual grid. |
Software Pipeline
I split the project into two distinct stages to keep the computation decoupled from the rendering:
- Tracks the empty "0" tile and validates grid boundaries before executing moves (Up, Down, Left, Right).
- Maintains parent-index tracking in memory so it can reconstruct the path backward once the goal is found.
- Serializes the explored search graphs and the final solution path into text files (`Nodes.txt`, `NodesInfo.txt`, and `nodePath.txt`).
- Runs independently by ingesting the `nodePath.txt` file generated by the solver.
- Reconstructs the raw text lines back into 3×3 state matrices.
- Renders a 300×300 pixel canvas and steps through the solution sequence on a timed cycle.
Breadth-First Search & State Hashing
The 8-puzzle operates as an unweighted state graph where each node is a unique 3x3 board configuration, and valid moves into the empty “0” space act as edges.
Optimal Pathfinding
Because every tile slide carries a uniform cost of one step, the solver uses a Breadth-First Search (BFS) algorithm managed by a FIFO queue. Expanding the search layer by layer guarantees it finds the absolute shortest path to the goal.
Cycle Detection & Hashing
To prevent infinite looping, the search space has to be strictly pruned. Since mutable 2D lists cannot be hashed in Python, every 3×3 grid is flattened into an immutable 9-tuple and added to a visited hash set. This allows for constant-time $O(1)$ lookups, instantly dropping redundant configurations.
Backtracking Parent Pointers
During the search, each generated child node records the index of its parent. When the goal state is found, the algorithm traces these parent pointers backward to the initial state, isolating the exact sequence of moves required to solve the puzzle.
Decoupled Architecture & File I/O
Rather than locking the computation to the graphical rendering, the architecture is decoupled using a file-backed pipeline:
Nodes.txt: Logs every board configuration explored during the search in chronological order.NodesInfo.txt: Stores node metadata, including its unique integer ID, parent index, and traversal cost.nodePath.txt: Contains exclusively the isolated sequence of optimal board matrices from root to goal.
Engineering Benefits
Serializing the data to text files completely separates the computation from the runtime graphics. The solver can execute massive state searches headlessly without UI overhead. The custom Pygame visualizer then independently reads nodePath.txt to playback and animate the exact solution sequence.