🧩 8-Puzzle Solver (AI Search Algorithms)

A Streamlit-based interactive application that solves the classic 8-puzzle problem using different AI search strategies:

• Uniform Cost Search (UCS)
• A* Search
• Greedy Best-First Search

---

🚀 Features

• Interactive 3×3 puzzle input grid
• Validates input (must contain numbers 0–8 exactly once)
• Checks puzzle solvability using inversion count
• Visual comparison of:
  • UCS
  • A* (Manhattan heuristic)
  • Greedy (Misplaced tiles heuristic)
• Displays solution path and cost

---

🧠 Algorithms Used

1. Uniform Cost Search (UCS)

• Explores all paths uniformly
• Guarantees optimal solution

2. A* Search

• Uses Manhattan distance heuristic
• Optimal and efficient

3. Greedy Best-First Search

• Uses misplaced tiles heuristic
• Fast but not always optimal

---

📌 Heuristics

Misplaced Tiles

Counts how many tiles are not in their goal position.

Manhattan Distance

Sum of distances of each tile from its goal position:

[ |x_1 - x_2| + |y_1 - y_2| ]

---

🔢 Goal State

1 2 3 4 5 6 7 8 0

(0 represents the blank tile)

---

⚙️ How to Run

1. Install dependencies

pip install streamlit

2. Run the app

streamlit run app.py

Solvability Rule

A puzzle is solvable if the number of inversions is even