THE UNIVERSITY OF BIRMINGHAM
School of Computer Science
Software Workshop Java
Solvability of the Tiles Game
Mark Ryan
Tiles Game
This wellknown 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 bottomright 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 111 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 (secondlast, fourthlast 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, thirdlast, fifthlast 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