8-puzzle
Slides tiles on a 3 × 3 board, computes the misplaced-tiles (h1) and Manhattan-distance (h2) heuristics, checks solvability, and solves any board with BFS, IDS, greedy best-first, A*, and weighted A*, then steps through the solution.
- Lecture reference: Solving Problems by Searching · slide 10
- Lecture reference: Informed Search · slides 32–37
Board
Click a tile next to the blank to slide it. On the focused board, ←↑→↓ move the blank.
Row by row, with _ or 0 for the blank: 7 2 4 / 5 _ 6 / 8 3 1, 724506831, or one row per line.
Scramble walks the blank from the goal state for the given number of random moves, never undoing the previous move; the same seed gives the same board.
Heuristics
Tiles 1–8 in order; the blank is not counted. The terms of h2 are the numbers of squares each tile is from its goal square. Lecture reference: Informed Search · slide 32
Relaxed problems
If a tile can move anywhere, h1(n) gives the shortest solution. If a tile can move to any adjacent square, h2(n) gives the shortest solution. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.
Lecture reference: Informed Search · slide 33Pattern databases
h3(n): the cost of getting a subset of tiles (say, 1, 2, 3, 4) into their correct positions. The exact solution cost for every possible subproblem instance can be precomputed and saved in a pattern database.
Lecture reference: Informed Search · slide 34Are h1 and h2 admissible?
Lecture reference: Informed Search · slide 32Show answer
Which one is better for search?
Lecture reference: Informed Search · slide 35Show answer
Solvers from the start state to the goal state
| Solver | Nodes expanded | Nodes generated | Max frontier | Solution length | Time (ms) |
|---|---|---|---|---|---|
BFS graph search | – | – | – | – | – |
IDS tree search, path check | – | – | – | – | – |
Greedy (h2) graph search | – | – | – | – | – |
A* (h1) graph search | – | – | – | – | – |
A* (h2) graph search | – | – | – | – | – |
Weighted A* (h2, α = 2) graph search | – | – | – | – | – |
Solution playback
Run a solver to step through its solution here.
State space
| Puzzle | States |
|---|---|
| 8-puzzle | 181,440 (9!/2) |
| 15-puzzle | ~1.3 trillion |
| 24-puzzle | ~10²⁵ |
Actions: move the blank left, right, up, or down. Path cost: 1 per move. Finding the optimal solution of the n-puzzle is NP-hard. Lecture reference: Solving Problems by Searching · slide 10
Why 9!/2
Read the tiles row by row and skip the blank. An inversion is a pair of tiles in the wrong order. Moving the blank left or right keeps the order; moving it up or down carries one tile past two others, which changes the count by −2, 0, or +2. So no move changes the parity of the count, and the 9! = 362,880 arrangements split into two halves of 181,440 that cannot reach each other.