8-puzzle solver

8-Puzzle Solver with Advanced Heuristics

Overview

For my 8-puzzle assignment, I implemented an algorithm to solve the classic sliding tile problem, where the goal is to arrange the tiles in ascending order from a scrambled initial state. This project focused on designing and testing efficient heuristics for guiding the search process and optimizing the solving process. Additionally, I extended the problem to handle n x n puzzles for broader scalability.

Challenge

The 8-puzzle is a computationally challenging problem due to its large state space and the need for an efficient solution. The primary challenge was to design a heuristic that:

• Guarantees admissibility, meaning it never overestimates the cost to reach the goal.
• Outperforms the Manhattan distance heuristic in terms of the number of node expansions.
• Works efficiently across multiple initial puzzle states while maintaining optimality.

Additionally, I expanded the scope of the assignment by implementing a generalizable solution for n x n grid puzzles, even though the original requirement was limited to a 3 x 3 grid.

Process

To solve the 8-puzzle problem efficiently, I followed these steps:

• Research and Planning: Studied the properties of the 8-puzzle and solvability conditions for n x n grids. Reviewed existing heuristics such as Manhattan distance and misplaced tiles.
• Algorithm Implementation: Implemented the A* search algorithm using a priority queue and defined the state space, transition function, and goal test for the puzzle.
• Heuristic Design: Used Manhattan distance as a baseline heuristic and developed a custom heuristic incorporating additional problem constraints, such as tile adjacency penalties or linear conflict detection.
• Testing and Validation: Tested both heuristics across multiple initial states and measured efficiency by counting the number of node expansions required to reach the solution.
• Generalization: Extended the implementation to solve puzzles of any size by integrating solvability checks based on inversions and parity rules, ensuring scalability and flexibility.

Outcome

• Performance Improvement: The custom heuristic consistently required fewer node expansions than Manhattan distance, demonstrating its dominance.
• Scalability: The solution was successfully extended to handle n x n puzzles, exceeding the assignment's requirements.
• Optimization and Accuracy: Maintained optimality and efficiency by ensuring all heuristics used were admissible and consistent.

View on Github

You can view the full assignment here here.