learn.aathan.in

The 8-Puzzle: Sliding Tiles, Solved with A*

The canonical AI search problem. State representation, the four operators, why half of all boards are unsolvable, the misplaced-tiles and Manhattan-distance heuristics, and a full A* implementation with a traced solution.

The 8-puzzle is a 3×3 frame holding eight numbered tiles and one empty slot. You slide tiles into the gap, one at a time, until the numbers read in order.

It looks like a toy. It is the single most important problem in classical AI — because it’s small enough to draw on a page, and large enough (181,440 states) that naïve search struggles. Every idea in heuristic search was first tested here.

The problem

123 46 758 solve 123 456 78 initial stategoal state

Rules. Only a tile orthogonally adjacent to the blank may move, and it moves into the blank. That’s it. There is no lifting, no diagonal, no double-move.

A cleaner way to think about it: the blank is the only thing that moves. Instead of “which of the up-to-4 tiles do I slide”, say “the blank goes Up, Down, Left or Right”. Same puzzle, but now you have exactly four operators instead of eight, and the code is half as long.

State representation

A board is nine values. Use a tuple, in row-major order, with 0 for the blank:

initial = (1, 2, 3,
           4, 0, 6,
           7, 5, 8)

goal    = (1, 2, 3,
           4, 5, 6,
           7, 8, 0)

Why a tuple and not a list of lists?

  • Hashable — you can put it in a set of visited states. A list can’t.
  • Comparable — state == goal is a single, fast comparison.
  • Flat — index arithmetic is trivial: the cell at row rr, column cc is state[3*r + c], and conversely index ii sits at divmod(i, 3).

That last point is what makes the operators short:

blank = state.index(0)
row, col = divmod(blank, 3)

The four operators

OperatorPreconditionEffect
UProw > 0Swap blank with index blank - 3
DOWNrow < 2Swap blank with index blank + 3
LEFTcol > 0Swap blank with index blank - 1
RIGHTcol < 2Swap blank with index blank + 1

The preconditions are the whole story. Forget col > 0 and the blank will “wrap” from column 0 to column 2 of the row above — a bug that produces a perfectly plausible-looking board and a completely wrong answer.

Branching factor. How many moves are available depends on where the blank is:

232 33 232 4 Number of legal moves when the blank sits here. 4 corners × 2 + 4 edges × 3 + 1 centre × 4 = 24 24 ÷ 9 ≈ b ≈ 2.67 average branching factor A depth-20 solution therefore touches roughly 2.67²⁰ ≈ 10¹⁰ nodes if you search blindly.

That last number is why the heuristic isn’t optional.

Half of all boards are unsolvable

This is the fact that trips everyone up. If you generate a random arrangement of the nine cells, there is a 50% chance no sequence of moves reaches the goal. Your solver will run until it exhausts memory, and you’ll blame the code.

The test is inversion parity.

An inversion is a pair of tiles that appear in the wrong relative order when you read the board left-to-right, top-to-bottom, ignoring the blank.

Take our initial state 1 2 3 4 _ 6 7 5 8. Dropping the blank: 1 2 3 4 6 7 5 8.

Now count pairs (i,j)(i, j) with i<ji < j but tilei>tilej\text{tile}_i > \text{tile}_j:

  • 6 before 5 → 1 inversion
  • 7 before 5 → 1 inversion

Total: 2 inversions — even. The standard goal 1 2 3 4 5 6 7 8 has 0 inversions — also even. Parities match, so it’s solvable.

Why parity is invariant: a horizontal blank move swaps the blank with a neighbour in the same row — since the blank is excluded from the count, the tile sequence is unchanged, so inversions don’t change at all. A vertical move jumps a tile over exactly two others, changing the inversion count by −2-2, 00, or +2+2. Either way, parity never flips. So if start and goal have different parity, no path can exist.

def inversions(state):
    tiles = [t for t in state if t != 0]
    return sum(1 for i in range(len(tiles))
                 for j in range(i + 1, len(tiles))
                 if tiles[i] > tiles[j])

def solvable(state, goal):
    """For an odd-width board (3x3), parities must match."""
    return inversions(state) % 2 == inversions(goal) % 2

On a 4×4 board (the 15-puzzle) the rule is different — because the width is even, you must also account for the row the blank sits in. Always check the width before copying a parity test off the internet.

The two classic heuristics

h₁ — misplaced tiles

Count how many tiles are not in their goal position. Ignore the blank.

For our initial board versus the goal, tiles 5 and 8 are wrong (and 6 and 7 — let’s count properly):

TileNow atShould be atMisplaced?
100no
211no
322no
433no
574yes
655no
766no
887yes

h1=2h_1 = 2.

It’s admissible because every misplaced tile needs at least one move, so you can never overestimate.

h₂ — Manhattan distance

For each tile, add the number of rows plus columns it is away from home.

  • Tile 5 is at index 7 → (row 2, col 1); goal index 4 → (row 1, col 1). Distance ∣2−1∣+∣1−1∣=1|2-1| + |1-1| = 1.
  • Tile 8 is at index 8 → (row 2, col 2); goal index 7 → (row 2, col 1). Distance ∣2−2∣+∣2−1∣=1|2-2| + |2-1| = 1.

h2=2h_2 = 2.

123 46 7 58 tile 5: (row 2, col 1) → (row 1, col 1) = 1 step tile 8: (row 2, col 2) → (row 2, col 1) = 1 step every other tile is already home = 0 h₂ = 1 + 1 = 2 the blank is never counted

h₂ dominates h₁: for every state, h2(n)≥h1(n)h_2(n) \ge h_1(n), and it’s still admissible. A stronger admissible heuristic always expands fewer nodes.

Here is what that costs in practice — mean nodes expanded over 20 random boards at each optimal solution depth, measured with the code further down this page:

Solution depthBFSA* with h₁A* with h₂
121,5389232
1822,5081,461277
24127,93118,1111,660
30181,345117,62318,467

Same algorithm, same board, same optimal answer. The only difference is the guess — and at depth 24 it is the difference between expanding 78% of the entire state space and expanding 0.9% of it.

Notice the last row. At depth 30 you are near the hardest boards that exist (the maximum is 31), and BFS has simply run out of puzzle — 181,345 of the 181,440 reachable states. Even h₂ is working hard there. Heuristics buy you an enormous amount, but they don’t repeal the exponential.

A worked solution, traced

Our board needs exactly two moves. Watch A* pick them.

123 46 78 5 123 46 7 5 8 123 46 7 58 blank DOWNblank RIGHT (5 slides up)(8 slides left) g=0 h=2 f=2 g=1 h=1 f=2 g=2 h=0 f=2 startone tile leftGOAL f stays flat at 2 the whole way — the sign of a perfectly-informed search

Notice what happened to f=g+hf = g + h: it stayed at 2 for all three states. That’s the hallmark of a consistent heuristic on an optimal path. Every move you spend (gg goes up by 1) buys you exactly one unit of progress (hh goes down by 1). When ff never rises along the solution path, A* walks straight to the goal without exploring a single wrong branch.

Full working code

import heapq
from collections import deque

GOAL = (1, 2, 3,
        4, 5, 6,
        7, 8, 0)

# Precompute where each tile belongs: tile -> (row, col)
GOAL_POS = {tile: divmod(i, 3) for i, tile in enumerate(GOAL)}


def successors(state):
    """Yield (next_state, move_name) for every legal blank move."""
    blank = state.index(0)
    row, col = divmod(blank, 3)
    moves = []
    if row > 0: moves.append((blank - 3, 'UP'))
    if row < 2: moves.append((blank + 3, 'DOWN'))
    if col > 0: moves.append((blank - 1, 'LEFT'))
    if col < 2: moves.append((blank + 1, 'RIGHT'))

    for target, name in moves:
        lst = list(state)
        lst[blank], lst[target] = lst[target], lst[blank]
        yield tuple(lst), name


def h_misplaced(state):
    """h1 — count tiles not in their goal square (ignore the blank)."""
    return sum(1 for i, t in enumerate(state) if t != 0 and t != GOAL[i])


def h_manhattan(state):
    """h2 — total row+column distance every tile must travel."""
    total = 0
    for i, tile in enumerate(state):
        if tile == 0:
            continue
        r, c = divmod(i, 3)
        gr, gc = GOAL_POS[tile]
        total += abs(r - gr) + abs(c - gc)
    return total


def solve(start, h=h_manhattan):
    """A* — returns (moves, nodes_expanded) or (None, n) if unsolvable."""
    counter = 0
    frontier = [(h(start), 0, counter, start, [])]
    best_g = {start: 0}
    expanded = 0

    while frontier:
        _, g, _, state, path = heapq.heappop(frontier)
        if state == GOAL:
            return path, expanded
        expanded += 1
        for nxt, move in successors(state):
            ng = g + 1
            if ng < best_g.get(nxt, float('inf')):
                best_g[nxt] = ng
                counter += 1
                heapq.heappush(frontier,
                               (ng + h(nxt), ng, counter, nxt, path + [move]))
    return None, expanded


def inversions(state):
    tiles = [t for t in state if t != 0]
    return sum(1 for i in range(len(tiles))
                 for j in range(i + 1, len(tiles))
                 if tiles[i] > tiles[j])


def solvable(state):
    return inversions(state) % 2 == inversions(GOAL) % 2


if __name__ == '__main__':
    start = (1, 2, 3,
             4, 0, 6,
             7, 5, 8)

    if not solvable(start):
        print('This board can never reach the goal.')
    else:
        for name, h in [('misplaced', h_misplaced), ('manhattan', h_manhattan)]:
            path, expanded = solve(start, h)
            print(f'{name:10s} -> {len(path)} moves, {expanded} nodes expanded')
            print(f'             {" ".join(path)}')

Running it:

misplaced  -> 2 moves, 2 nodes expanded
             DOWN RIGHT
manhattan  -> 2 moves, 2 nodes expanded
             DOWN RIGHT

Try a genuinely scrambled board, (8, 6, 7, 2, 5, 4, 3, 0, 1). It is one of the hardest 8-puzzles there is — the optimal solution takes 31 moves, the maximum for this puzzle — and the gap between the heuristics opens right up:

misplaced  -> 31 moves, 143848 nodes expanded
manhattan  -> 31 moves,  21197 nodes expanded

Both return a 31-move solution, because both are admissible. One of them looks at seven times fewer boards to do it.

Comparing the algorithms on this problem

AlgorithmOptimal?Nodes (depth-18 board)Verdict
BFS✅22,508Works, eats memory
DFS❌wanders foreverUseless without a depth limit
Iterative deepening✅more than BFSBFS quality, DFS memory
A* with h₁✅1,461Good
A* with h₂✅277The right answer
IDA* with h₂✅somewhat more than A*Same quality, constant memory — scales to 15-puzzle

IDA* (iterative-deepening A*) is worth knowing: it runs a depth-first search with an ff-cutoff, raising the cutoff each round to the smallest ff that exceeded it. It expands slightly more nodes than A* but uses O(d)O(d) memory instead of O(bd)O(b^d) — which is what lets it solve the 15-puzzle.

Why this problem matters

The 8-puzzle isn’t about tiles. It’s the smallest problem that has all four properties real planning problems have:

  • A huge state space you can’t enumerate
  • A clear goal test but no obvious formula for the answer
  • Reversible operators (so cycles exist and must be detected)
  • A natural relaxation that yields a heuristic

Change the words and you have real systems:

  • Warehouse robots — the blank is the free aisle slot, tiles are shelves, and the goal is the picking order. Amazon’s Kiva robots solve exactly this.
  • Register allocation in a compiler — variables must be shuffled through a limited number of registers, one move at a time.
  • Container terminal stacking — retrieving a specific container from under a stack is the same “move the obstruction to the only free spot” problem.

And the lesson generalises further than the applications: a good heuristic beats a faster computer. Going from BFS to A*+Manhattan on a depth-24 board cuts the work by a factor of 77, and swapping h₁ for h₂ alone accounts for 11× of that. You do not get multiples like those from better hardware — you get them from thinking about the problem for ten minutes.

Where to go next