Overview

Complete implementation of the 8-puzzle problem solver using A* search algorithm with optimal path finding and visualization.

Problem Description

Classic sliding puzzle with:

• 3×3 grid with 8 numbered tiles and 1 blank space
• Goal: arrange tiles in order from 1-8
• Movement: slide adjacent tiles into blank space
• Challenge: finding optimal solution path

Algorithm Implementation

A Search with Manhattan Distance*

• Heuristic: Sum of Manhattan distances from goal state
• Open set: Priority queue (min f = g + h)
• Closed set: Visited states to prevent cycles
• Guarantees optimal solution path

Key Features

• ✅ Optimal path finding using A*
• ✅ Manhattan distance heuristic
• ✅ State space visualization
• ✅ Solution path animation
• ✅ Performance metrics (nodes explored, path length)
• ✅ Configurable initial states

Technical Stack

• Language: C++
• Algorithm: A* Search
• Heuristic: Manhattan Distance
• Data Structures: Priority Queue, Hash Set
• Visualization: Animation output

Getting Started

git clone https://github.com/svaibhav101/slide-8-puzzle.git
cd slide-8-puzzle && mkdir build && cd build
cmake .. && make
./puzzle_solver

Complexity Analysis

• Time: O(b^d) where b=branching factor, d=depth
• Space: O(b^d) for open/closed sets
• Optimality: Guaranteed with admissible heuristic
• Completeness: Always finds solution if exists

Use Cases

• Search algorithm learning
• Heuristic function design study
• Path planning fundamentals
• AI problem-solving demonstrations