THE UNIVERSITY OF BIRMINGHAM
School of Computer Science
Software Workshop Java
Solvability of the Tiles Game

Mark Ryan


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:
So there are 49 inversions in this example.

The formula says:
  1. If the grid width is odd, then the number of inversions in a solvable situation is even.
  2. 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.
  3. 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:

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:

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

Fact 3:
Proof of fact 3:
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

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.
  1. You can always get the blank where you want it, by temporarily moving stuff out of the way. ((picture))
  2. 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))
  3. 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