Tiles Game

This well-known puzzle, often referred to as the 'Puzzle of Fifteen', became popular in America during the 1870s. The puzzle consists of fifteen square tiles, labelled numerically from 1 to 15. They are arranged in a random ordering within a square tray that is just large enough to hold sixteen tiles in a 4 x 4 grid (see fig. 1). The tiles should then be slid around the tray until they are in the correct ordering as shown in fig. 2, with the blank space at the bottom-right hand corner. The tiles must not be picked out of the tray.

fig 1

6 1 10 2

7 11 4 14

5 9 15

8 12 13 3

fig 2:
Solution

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15

fig 3: Unsolvable

1 2 3 4

5 6 7 8

9 10 11 12

13 15 14

Not all configurations are solvable. For example, the configuration in which the last two tiles are swapped (fig. 3) is not solvable.

Formula for determining solvability

There is a method to check whether any given game state is solvable. First, consider the tiles written out in a row, like this:

fig 4

12
1 10 2

7 11 4 14

5 9 15

8 13 6 3

fig 5:
Tiles written in a row

12 1
10
2
7
11
4
14
5

9
15
8
13 6 3

An inversion is when a tile precedes another tile with a lower number on it. The solution state has zero inversions. For example, if, in a 4 x 4 grid, number 12 is top left, then there will be 11 inversions from this tile, as numbers 1-11 come after it. To explain it another way, an inversion is a pair of tiles (a,b) such that a appears before b, but a>b. Count the number of inversions in the grid. For example, on the grid of fig.4:

the 12 gives us 11 inversions
the 1 gives us none
the 10 gives us 8 inversions
the 2 gives us none
the 7 gives us 4 inversions
the 11 gives us 6 inversions
the 4 gives us one inversion
the 14 gives us 6
the 5 gives us one
the 9 gives us 3
the 15 gives us 4
the 8 gives us 2
2 from the 13
one from the 6

So there are 49 inversions in this example.

The formula says:

If the grid width is odd, then the number of inversions in a solvable situation is even.
If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

That gives us this formula for determining solvability:

( (grid width odd) && (#inversions even) ) || ( (grid width even) && ((blank on odd row from bottom) == (#inversions even)) )

Why is that formula correct?

Definition: the polarity of a number is whether the number is even or odd.

Fact 1: For a grid of odd width, the polarity of the number of inversions is invariant. That means: all legal moves preserve the polarity of the number of inversions.

Example: consider the move below. The number of inversions on the left is 11, an odd number. By moving the 3 up, the 9 and the 8 both lose an inversion. So the result has 9 inversions, which is still odd.

11 inversions

7
1
2

5 9

8 3 6

goes to

9 inversions

7
1
2

5 3
9

8
6

Proof of fact 1:

Moving a tile left or right does not change the number of inversions, and therefore doesn't change its polarity.
Moving a tile up or down does change the number of inversions. The tile moves past an even number of other tiles (which is the width of the board, minus 1). So the number of inversions changes by ±1±1±1±1...±1, an even number of times. This is even.

For a grid with an even width, the situation is similar.

Fact 2: For a grid of even width, the following is invariant: (#inversions even) == (blank on odd row from bottom).

Example: consider the move below. The number of inversions on the left is 49, and the blank is on an even row from the bottom. So the value of the invariant is "false == false", which is true. The number of inversions on the right is 48, because the 11 has lost two inversions, but the 14 has gained one. The blank is on an odd row from the bottom. So the value of the invariant is "true==true", which is still true.

49 inversions
blank on even row from bot

12
1 10 2

7 11 4 14

5 9 15

8 13 6 3

goes to

48 inversions
blank on odd row from bot

12
1 10 2

7
4 14

5 11 9 15

8 13 6 3

Proof of fact 2:

Moving a tile left or right does not change the number of inversions and does not change the row of the blank
Moving a tile up or down does change the number of inversions. The tile moves past an odd number of other tiles (which is the width of the board, minus 1). So the number of inversions changes by ±1±1±1±1...±1, an odd number of times. This is odd. The row of the blank also changes, from odd to even, or from even to odd. So both halves of the invariant changes. So its value is preserved.

With these two facts, we can easily prove the following:

Fact 3:

If the width is odd, then every solvable state has an even number of inversions.
If the width is even, then every solvable state has

an even number of inversions if the blank is on an odd numbered row counting from the bottom;
an odd number of inversions if the blank is on an even numbered row counting from the bottom;

Proof of fact 3:

The initial (solved) state has those properties;
Those properties are preserved by every legal move
Any solvable state can be reached from the initial state by some sequence of legal moves.

Fact 3 is "one half" of the formula.

So you have shown that all solvable states have the stated property. But could there be some unsolvable states that have it too?

Good question! But the answer is no. We can show that:

Fact 4: (the converse of fact 3)
If a state is such that

If the width is odd, then the state has an even number of inversions.
If the width is even and the blank is on an odd numbered row counting from the bottom, then the state has an even number of inversions
If the width is even and the blank is on an even numbered row counting from the bottom, then the state has an odd number of inversions

Then the puzzle is solvable from that state.

Proof of fact 4:
To prove this, you have essentially to show how to solve the puzzle. That is what we do for the remainder of this page. The heuristics we develop will be useful if you decide to implement the automatic solution generator.

How to solve the puzzle

There are many ways which are not optimal, and you probably have your own. Here's mine.

Get the 1 in the right place. Then get the 2 in the right place. Continue in this way until everything is in the right place.

Sometimes you have to temporarily undo some of your past achievements, to make room for your current task.

You can always get the blank where you want it, by temporarily moving stuff out of the way. ((picture))
You can always rotate any triplet, e.g., make abc into cab or bca, if you have some room above or below. Here's how:((picture))
You can insert a tile into a nearly complete row. Here's how.((picture))

By combining moves like these ones, you can solve any puzzle right down to the last line. You can rotate the last line until it is nearly right. If the puzzle is solvable, you can solve it completely.

But that takes too many moves. Can't you tell me how to solve it in a minimum number of moves? What is the minimum number of moves for a given configuration, anyway?

More good questions. Some of the answers are given on Kevin Gong's web page. Try http://kevingong.com/Math/SixteenPuzzle.html. My proofs are based on his, but why does he use all that dreadful notation?

Page written by Mark Ryan
Page maintained by Mark Ryan
Last modified: 26 November 2004