June 4, 2024 (Updated on: March 7, 2025)

Solving the 3×3 Sliding Puzzle: Proof of Solvability and Maximum Moves

A few days ago, I was playing the video game The Legend of Zelda : The Wind Waker. In this game, there’s a sliding puzzle mini-game. The objective is to slide the pieces around to recreate the original image. And I quickly realized that I was terrible at it. It took me dozens of minutes to find the solution. Until I discovered that there were 15 more to complete! The question then arose : are all the sliding puzzles solvable?

The Wind Waker slidding puzzle is a $4 \times 4$ one, but let’s talk about an easier one, a $3 \times 3$

The sliding puzzle is a game consisting of an $n \times n$ grid (here, $3 \times 3$ ) containing $n^2 - 1$ numbered tiles from $1$ to $8$ and an empty space that allows tiles to be moved by sliding them around.

We will prove the solvability of the game and establish the maximum number of moves required to solve a $3 \times 3$ puzzle.

Conditions for solving a 3×3 sliding puzzle

The question of solvability relies on the parity of tile permutations (as per Johnson and Story article in 1879 in the American Journal of Mathematics). But first, let’s define the mathematical concepts we will need.

The permutations

A sliding puzzle configuration can be represent as a permutation of the numbers ${1, 2, ..., 8}$ and the empty space.

The number of inversions

An inversion is a pair $(i, j)$ such that $i < j$ , which means that the tile $j$ appears before tile $i$ in the puzzle board when we read the grid from left to right and from top to bottom.

A permutation of tiles is stated as even or odd based on the number of inversions it contains. So :

A permutation is even if the total number of inversions is even.
A permutation is odd if this number is odd.

For example, let’s consider the following initial configuration :

\begin{array}{ccc} 2 & 8 & 3 \\ 1 & 6 & 4 \\ 7 & \_ & 5 \end{array}

If we ignore the empty space, the sequence of numbers is :

(2, 8, 3, 1, 6, 4, 7, 5)

Let’s count the inversions :

2 precedes 1 → $(2,1)$ (1 inversion)
8 precedes 3, 1, 6, 4, 7, 5 → $(8,3), (8,1), (8,6), (8,4), (8,7), (8,5)$ (6 inversions)
3 precedes 1 → $(3,1)$ (1 inversion)
6 precedes 4, 5 → $(6,4), (6,5)$ (2 inversions)
4 precedes 1 → $(4,1)$ (1 inversion)
7 precedes 5 → $(7,5)$ (1 inversion)

The total of inversions in th example is : $1 + 6 + 1 + 2 + 1 + 1 = 12$ (even).

The parity of the number of inversions is defined as :

\text{inv}(\sigma) = \sum_{i < j} \mathbf{1}_{\sigma(i) > \sigma(j)}

where $\sigma(i)$ represents the number at position $i$ in the configuration.

The parity of the empty tile position

In a $3 \times 3$ sliding puzzle, the parity of the configuration also depends on the position of the empty tile.

The row of the empty tile $r$ is counted from the bottom :

$r = 1$ for the last row,
$r = 2$ for the middle row,
$r = 3$ for the top row.

So, a configuration is solvable if and only if :

\text{parity of the number of inversions} + \text{parity of } r \equiv 0 \pmod{2}

In other words :

If $ext{inv}(\sigma)$ is even, then $r$ must be odd.
If $ext{inv}(\sigma)$ is odd, then $r$ must be even.

Let’s go back to our previous example :

The number of inversions is even (12).
The empty space is in row 1 (last row) → $r = 1$ (odd).

So, $12 + 1 = 13$ is odd.

Since the final solved state has $0 + 1 = 1$ (odd), then this configuration is solvable !.

The maximum moves required to solve the puzzle

Solving a sliding puzzle requires a certain number of moves, which depends on the optimal path from any given configuration to the solved state. And this is determined using a new key concept :

The Manhattan distance

The Manhattan distance is a measure of how far a given configuration is from the solved state. Basically, how far you are from solving the puzzle. It is defined as :

d = \sum_{i=1}^{8} \left( |x\_i - x\_i^*| + |y\_i - y\_i^*| \right)

where :

$(x\_i, y\_i)$ represents the present coordinates of the tile $i$ ,
$(x\_i^*, y\_i^*)$ represents the correct coordinates of the tile $i$ in the solved state.

For example, let’s consider this puzzle configuration :

\begin{array}{ccc} 2 & 8 & 3 \\ 1 & 6 & 4 \\ 7 & \_ & 5 \end{array}

The goal state is obviously :

\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & \_ \end{array}

If we calculate the Manhattan distance for each tile of the initial configuration, we have :

Tile 1 : $|2-1| + |0-1| = 2$
Tile 2 : $|0-0| + |1-0| = 1$
Tile 3 : Already correct
Tile 4 : $|1-1| + |0-2| = 2$
Tile 5 : $|1-2| + |1-2| = 2$
Tile 6 : $|1-1| + |2-1| = 1$
Tile 7 : Already correct
Tile 8 : $|2-0| + |1-1| = 2$

Then, the total Manhattan distance is :

2 + 1 + 0 + 2 + 2 + 1 + 0 + 2 = 10

The total possible ptates and the solvability

A $3 \times 3$ puzzle contains 9 spaces, with 8 tiles and one empty space. Each configuration can be seen as a permutation of 8 tiles with a given empty tile position.

The number of permutations of the 8 tiles is : $8! = 40320$
Since the empty space can be in 9 different positions, the total number of states is : $9! = 362880$

However, due to parity constraints we see before, only half of the configurations are solvable, which lead us to :

\frac{9!}{2} = 181440

Conclusion

A 3×3 sliding puzzle is solvable if and only if the parity of the number of inversions matches the parity of the empty tile’s row.
The maximum number of moves required to solve any solvable configuration is 31.