A* 8-Puzzle Solver Visualizer
An interactive demonstration of state-space search exploring heuristic dominance in the classic sliding tile puzzle.
8-Puzzle Solver
Enter a starting configuration to see how the Manhattan Distance heuristic guides the search path.
The Objective
The 8-puzzle is a classic sliding tile problem where the goal is to organize eight numbered tiles on a 3x3 grid by moving them into an empty space. Because the state space of this puzzle is relatively large, blind search methods are highly inefficient. This project solves the problem using the A* search algorithm, an informed search technique that evaluates nodes using the cost function f(n) = g(n) + h(n), where g(n) is the actual step cost and h(n) is the estimated cost to reach the goal.
Technical Implementation
1. Optimized Data Structures
The algorithm utilizes a PriorityQueue to manage the open list, ensuring the node with the lowest f(n) value is expanded first. To prevent infinite loops, a HashSet acts as the closed list.
2. Memory Management
Storing raw 2D arrays in memory caused inefficiencies during early development. This was solved by flattening the arrays into unique strings before adding them to the set, allowing for fast O(1) lookups and keeping memory usage low.
3. Heuristic Comparison
The system compared two admissible heuristics: Misplaced Tiles (h1), which counts tiles out of position, and Manhattan Distance (h2), which calculates the sum of vertical and horizontal distances to the target.
4. Logical State Translation
Mapping grid coordinates required careful tracking during successor generation. The algorithm translates the abstract movement of the blank space (0) into the physical movement of tiles (e.g., if the blank moves "Up", the UI records "Tile X Down").
Analysis & Outcome
Experimental results across 5 different initial configurations proved that while both heuristics always find the same optimal solution length, the Manhattan Distance (h2) performs significantly better than Misplaced Tiles (h1).
This aligns with Dominance Theory. Because h2(n) ≥ h1(n) for every state, h2 provides a closer estimate to the actual cost without overestimating. By returning higher values, it allows the A* algorithm to prune unpromising branches much earlier, resulting in drastically fewer expanded nodes and faster execution times.