15 Puzzle Solver
The 15-puzzle is a sliding puzzle consisting of a 4×4 grid with fifteen numbered tiles and one empty space. The goal is to rearrange the tiles into the correct order by sliding them into the empty space. This interactive visualizer demonstrates how the A* search algorithm efficiently finds a solution. Users can generate random puzzle configurations, control the speed of the solver, and watch the tiles move step-by-step as the algorithm reconstructs the optimal path to the goal state.
Algorithm explanation
The solver uses the A* search algorithm, which is an informed search algorithm that combines the cost to reach a node (g) and a heuristic estimate of the cost to reach the goal (h). In this implementation, the Manhattan Distance heuristic is used. The algorithm explores puzzle states by prioritizing those with the lowest estimated total cost f(n) = g(n) + h(n). Each board configuration represents a node in the search graph, and edges represent valid tile moves. A* ensures that the optimal solution is found when the heuristic is admissible.
Concepts used
- Graph Search
- Heuristic Search
- A* Algorithm
- Manhattan Distance
- State Space Search
- Priority Queue
Complexity
Exponential in the worst case, typically approximated as O(b^d), where b is the branching factor (~2.13) and d is the depth of the optimal solution.O(b^d) due to storing explored states in memory for the open and closed sets.Real-world usage
- Artificial intelligence search problems
- Robotics path planning
- Route finding systems such as GPS navigation
- Game AI and puzzle solvers
- Optimization problems using heuristic search