eight-puzzle

8-Puzzle

Solves the 8-puzzle using Breadth-First Search, guaranteeing the shortest solution. See 15 puzzle — Wikipedia (the 8-puzzle is the 3×3 variant).

The puzzle

A 3×3 grid containing tiles numbered 1–8 and one blank space (shown as .). You can slide any tile adjacent to the blank into the blank's position. The goal is to reach this arrangement:

1 2 3
4 5 6
7 8 .

Starting from a scrambled state, the challenge is to find the sequence of moves that reaches the goal in the fewest steps.

Why BFS?

The puzzle is a state space search problem. Each unique arrangement of the grid is a state, and each slide move transitions to a new state. This forms an implicit graph:

• Nodes — grid arrangements (there are 9!/2 = 181,440 reachable states)
• Edges — valid slide moves (up, down, left, right)
• Start — the scrambled arrangement
• Goal — the solved arrangement

BFS explores all states reachable in 1 move, then all states reachable in 2 moves, and so on. The first time it reaches the goal state, it is guaranteed to have found the shortest path — the minimum number of moves.

Each state is stored as a tuple of 9 numbers (reading the grid left to right, top to bottom). A Python set tracks visited states so the same arrangement is never explored twice.

Solvability

Not all scrambled arrangements can be solved. An arrangement is solvable if and only if the number of inversions is even.

An inversion is any pair of tiles (ignoring the blank) where a larger number appears before a smaller one when reading left to right, top to bottom. For example in [2, 1, 3, ...], the pair (2,1) is one inversion because 2 appears before 1.

This means half of all possible arrangements are unsolvable — no sequence of moves can reach the goal from them. The check runs in O(n²) before BFS starts, avoiding a pointless search.

Run

python eight_puzzle.py

Runs four built-in examples including one unsolvable puzzle.

Example

Start:          Solution:
1 2 3           slide 8 left (1 move)
4 5 6
7 . 8