SPPU | Third Year | Sem VI | 310253 — Artificial Intelligence
Master these core concepts before running the simulation. Each card builds on the previous one.
A 3×3 sliding puzzle with 8 numbered tiles and one empty space. You slide tiles into the empty space to rearrange them into a target configuration.
Our problem: rearrange from the jumbled start to the target in the fewest moves.
A quick, educated guess about how close you are to your goal.
You're in Pune, driving to Mumbai. Straight-line distance is 150 km. The actual road distance is 160–170 km. That 150 km estimate is your heuristic — it's always optimistic, never overestimates the real distance.
Key property — Admissibility: A good heuristic never overestimates the true cost. This guarantees A* will find the optimal (shortest) solution.
g(n) = 0 (no moves yet), h(n) = 4 (tiles 2, 8, 1, 6 are misplaced), so f(n) = 0 + 4 = 4
Count how many tiles are NOT in their goal position (skip the blank).
| Position | Initial | Goal | Match? |
|---|---|---|---|
| [0,0] | 2 | 1 | ✗ Misplaced |
| [0,1] | 8 | 2 | ✗ Misplaced |
| [0,2] | 3 | 3 | ✓ Correct |
| [1,0] | 1 | 8 | ✗ Misplaced |
| [1,1] | 6 | _ | ✗ Misplaced |
| [1,2] | 4 | 4 | ✓ Correct |
| [2,0] | 7 | 7 | ✓ Correct |
| [2,1] | _ | 6 | — Blank (skip) |
| [2,2] | 5 | 5 | ✓ Correct |
Misplaced: tiles 2, 8, 1, 6 → h(n) = 4
Why it's admissible: Each misplaced tile needs at least one move to fix, so this count never overestimates the actual number of moves needed.
A search algorithm that finds the optimal (shortest) path from start to goal.
A* is smart because it uses f(n) to prioritize the most promising states — balancing "moves already made" with "estimated moves remaining."
States waiting to be explored. We always pick the one with the lowest f(n) next.
States already explored. Once a state is in CLOSED, we never revisit it.
OPEN is the waitlist — the host seats the highest-priority customer (lowest f(n)) first. Once served, they go to the served list (CLOSED). You never re-serve someone already done.