The Fifteen Puzzle—A New Approach

Author(s): S. MURALIDHARAN
Source: Mathematics Magazine, Vol. 90, No. 1 (February 2017), pp. 48-57
Published by: Mathematical Association of America
Stable URL: [Link]
Accessed: 15-02-2017 05:37 UTC

JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted
digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about
JSTOR, please contact support@[Link].

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at
[Link]

Mathematical Association of America is collaborating with JSTOR to digitize, preserve and extend access
to Mathematics Magazine

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
48 MATHEMATICS MAGAZINE

The Fifteen Puzzle—A New Approach

S. M U R A L I D H A R A N
Decision Sciences and Algorithms Lab
Tata Consultancy Services, Chennai, INDIA
drsmuralidharan@[Link]

You probably have seen the 15-puzzle before. This puzzle, also called the Gem Puzzle,
Boss Puzzle, Game of Fifteen, Mystic Square, and other names, consists of sliding
square tiles numbered 1 to 15 that occupy all but one cell of a 4 × 4 box (Figure
1). The basic goal is to use the blank cell to slide the square tiles so that the final
arrangement is the natural order of the numbers 1 to 15. Do you know how to solve
it? Perhaps a trial and error approach might work. Starting from an arbitrary initial
arrangement, is it possible to arrive at the natural order? Have you seen an algorithm
that you could use for any initial position? This puzzle has a rich history. Sam Loyd
claimed that he was the inventor of the puzzle but it may have been invented by Noyes
Chapman, a postmaster in Canastota, New York.
Only half of the possible 15! initial arrangements can be restored to the natural order
but that was not evident when this puzzle swept the United States and other parts of the
world in the 1880’s. The major challenge was to achieve the goal starting from a near
perfect initial array in which the last row contained 13, 15, 14 in that order—the only
difference being the permutation of the last two adjacent tiles. This challenge gripped
the people of all ages and walks of life. Sam Loyd even announced a prize of 1000 US
dollars for the solver of this challenge.

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15

Figure 1 The 15-puzzle.

It can be proved that of the 15! possible initial arrangements, half of them can be
restored to the natural order and the other half to the order in which the first three rows
are in natural order and the last row is 13-15-14 (see [1, 2, 5, 6, 7, 10]). In particular,
the 13-15-14 arrangement cannot be restored to the natural order.
Almost all the proofs use the theory of the alternating group A15 but do not exhibit
a set of moves to arrive at one of the above two possible arrangements from a given
initial arrangement.
There are also several algorithms for solving the puzzle. Even for the general N × N
board, one can find a solution using heuristics, but finding the optimal number of
moves in which the general puzzle can be solved is known to be an NP-hard problem
(e.g., [8, 9]).
In this paper we give a simpler, elementary (nongroup-theoretic) proof that exactly
half of the 15! arrangements can be restored to the natural order. We also describe
Math. Mag. 90 (2017) 48–57. doi:10.4169/[Link].90.1.48. 
c Mathematical Association of America
MSC: Primary 91A60, Secondary 05A05.

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
VOL. 90, NO. 1, FEBRUARY 2017 49
an algorithm to restore any arrangement into one of the two arrangements mentioned
above. The key strategy we use is “divide and conquer.” We reduce the problem to the
2 × 4 board and use the results proved for this board to derive the main theorem. Our
approach generalizes to the N × N board as well.

2 × 4 Puzzle We first consider the 2 × 4 puzzle in which we arrange the numbers

1, 2, . . . , 7 in some order and study which of those arrangements can be restored to the
natural order. With any arrangement, we associate a sequence formed by following the
arrow in Figure 2. For example, for the arrangement shown in Figure 2, the sequence

Figure 2 2 × 4 board and listing order.

associated is (a, b, c, d, g, f, e). Note that we ignore the blank space in forming the
sequence.
In any sequence we say that an inversion occurs each time a larger number precedes
a smaller number. For example, in the sequence (1, 2, 3, 4, 7, 6, 5), the number of
inversions is 3 and in (7, 6, 5, 4, 3, 2, 1), the number of inversions is 21.
An arrangement is said to have even parity if the corresponding sequence has an
even number of inversions and odd parity if the sequence has odd number of inver-
sions. Inversions hold the key to determine which arrangements can be restored to the
natural order. We prove the following theorem.
Theorem 1. An arrangement of the numbers in the 2 × 4 board can be restored to the
natural order if and only if the arrangement has odd parity.
We begin with a lemma.
Lemma 1. If two adjacent numbers in a sequence are interchanged, the resulting
sequence has the opposite parity of the original sequence.
Proof. Suppose that in the sequence s1 = (. . . , a, b, . . .) we interchange a, b to get
the sequence s2 = (. . . , b, a, . . .). If a < b, then s2 has one more inversion caused by
the larger number b preceding the smaller a, since all other inversions of the sequence
s1 are preserved in s2 . Thus s2 has opposite parity to the parity of s1 . Also, if a > b, the
inversion in s1 caused by the larger a preceding the smaller b is removed in s2 by the
interchange. Thus s2 has one less inversion than s1 . Thus again, s2 has opposite parity
to the parity of s1 .
As a corollary, we make the following observation. The sequences

s1 = (. . . , a, x1 , x2 , . . . , xr , . . .),
s2 = (. . . , x1 , x2 , . . . , xr , a, . . .)

have the same parity if r is even and have opposite parity if r is odd.
This is clear from the lemma, since we can obtain s2 by interchanging a with
x1 , x2 , . . . , xr , in that order. Since each interchange reverses the parity, there are r
reversals. We first prove that the legal moves do not change the parity.
Lemma 2. Any legal move does not change the parity of the arrangement.

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
50 MATHEMATICS MAGAZINE

Figure 3 Vertical moves.

Proof. Any horizontal shift does not change the sequence and hence the parity of the
sequence is not affected.
Consider the vertical moves (Figure 3).
When we move the x in the first column, the sequence (x, y, z, t, w, v, u) becomes
(y, z, t, w, v, u, x) and hence x moves to the final position after 6 interchanges. Hence
by the observation above, the resulting sequence has the same parity as the original
sequence.
When we move u in the first column, second row to the first column, first row,
the sequence changes from (x, y, z, t, w, v, u) to (u, x, y, z, t, w, v) and again u is
interchanged six times. Thus in this case also the parity of the sequence does not
change.
Similarly, when we move a symbol in the second column, the number of inter-
changes is 4 and hence the parity is maintained.
When we move a symbol in the third column, the number of interchanges required
is 2 and finally, moving a symbol in the last column does not change the sequence at
all. Thus in all cases the parity of the sequence is maintained. This completes the proof
of the lemma.
We now introduce some basic moves that play a key role in the proof of Theorem 1.
S(±n): In this move, we slide the symbols either clockwise or anticlockwise so that
each symbol moves by n cells. The moves S(+1) and S(−1) are shown in Figure 4.
R1 : This move allows for three adjacent symbols to cycle in a row under certain
conditions (as shown in Figure 5). The proof that R1 can be obtained by a sequence of
legal moves is shown in Figure 6.
E 1 , E 2 : These moves interchange two adjacent columns, as shown in Figure 7. E 1
can be obtained as follows. (See Figure 8.) Shift e, move b down, apply S(−2), push
d down, and move a, c anticlockwise. The legal moves constituting E 2 are shown in
Figure 9.
T : This move shifts elements in a triangular cycle among two adjacent rows. For
example, in Figure 10 we shift a from the top row to the bottom row and shift d from
the bottom row to the top row. Figure 11 shows how this can be accomplished using
legal moves.
R2 : This moves three elements in the bottom row cyclically, as shown in Figure 12.
The legal moves leading to R2 are given in Figure 13.
Now we prove Theorem 1. Start with an arbitrary arrangement of 1, 2, . . . , 7 in
the 2 × 4 board, as given in Figure 14. By using the moves T and R1 , we see that
any symbol in the first row can be interchanged with the first symbol in the second
row, with no other symbols switching rows (although their order within the row may
change). Again, using E 1 and E 2 , we can bring any symbol in the second row to the

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
VOL. 90, NO. 1, FEBRUARY 2017 51

(+1)

(–1)

Figure 4 Slide move S(±1).

Figure 5 Move R1 .

(–2) (+2)

Figure 6 Legal moves for R1 .

first cell in the second row (again without impacting the set of symbols in the individual
rows) and hence it follows that we can exchange any pair of symbols between the first
and second rows. Thus we can bring the symbols 1, 2, 3, 4 to the first row and 5, 6, 7
to the second row. Now using E 1 , E 2 , we can assume that 4 is in the first row, fourth
column. Using R2 , we can assume that the second row is either 5, 6, 7 in that order or
5, 7, 6. Thus we have reached one of the two arrangements A1 , A2 in Figure 15 where
(x, y, z) is 1, 2, 3 in some order. Suppose that the initial arrangement had odd parity,
and we reached the A1 arrangement. The parity of the sequence (x, y, z, 4, 7, 6, 5)
must also be odd and since (4, 7, 6, 5) has three inversions, it follows that (x, y, z)
must have an even number of inversions. Hence (x, y, z) must be one of (1, 2, 3),
(3, 1, 2), or (2, 3, 1). Now, using R1 , we can move this arrangement to the natural
order.
Now suppose that we reach the arrangement A2 . Since (4, 6, 7, 5) has two inver-
sions, the sequence (x, y, z) must have an odd number of inversions. Thus it must
be one of (1, 3, 2), (2, 1, 3), or (3, 2, 1). The (1, 3, 2) case is already solved (we use
E 1 to interchange the second and third columns and we obtain the natural order). For
(2, 1, 3), first use E 1 to interchange second and third columns and then R1 to obtain
the natural order. For (3, 2, 1), we use R1 to change the first row to (1, 3, 2) and use E 1

Figure 7 Moves E 1 and E 2 .

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
52 MATHEMATICS MAGAZINE

Figure 8 Legal moves for E 1 .

1 1

Figure 9 Legal moves for E 2 .

Figure 10 Move T .

Figure 11 Legal moves for T .

Figure 12 Move R2 .

2
1 1

Figure 13 Legal moves for R2 .

Figure 14 Starting arrangement.

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
VOL. 90, NO. 1, FEBRUARY 2017 53
4 4
5 6 7 5 7 6

1 2

Figure 15 Proof of Theorem 1.

to interchange the second and third columns. This results in the natural order. Hence if
we start with an arrangement with odd parity, we can reach the natural order.
A similar argument shows that if we start with an arrangement with even parity we
reach the arrangement in which the first row is 1, 2, 3, 4 in that order and the second
row is 5, 7, 6 in that order. Thus we have proved the following theorem.
Theorem 2. Starting with any arrangement on the 2 × 4 board, we reach the arrange-
ments Anat or Ar ev (Figure 16) when the parity of the original arrangement is odd or
even, respectively.

1 2 3 4 1 2 3 4
5 6 7 5 7 6

Figure 16 Final positions for 2 × 4 board.

4 × 4 Puzzle As in the 2 × 4 case, we first choose a suitable listing order and asso-
ciate a sequence with any arrangement in such a way that any legal move does not
alter the parity of the associated sequence. For the 4 × 4 board, we choose the list-
ing sequence by following the path shown in Figure 17. With this listing order, the

Figure 17 Listing order.

horizontal moves do not change the sequence. For the vertical moves, there are those
that do not change the sequence. These are shown in Figure 18. The other vertical
moves of an arbitrary element u will move u two, four, or six places in the sequence, as
shown in Figures 19, 20, and 21, respectively. In all the cases, the symbols are shifted
in the sequence by an even number of places and hence the parity of the sequence is
not altered.
Now we are ready to prove the following theorem.
Theorem 3. An arrangement of the numbers in the 4 × 4 board can be restored to the
natural order if and only if the arrangement has odd parity.

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
54 MATHEMATICS MAGAZINE

Figure 18 Moves that do not change the sequence.

Figure 19 Moves that shift a symbol by 2 places.

Figure 20 Moves that shift a symbol by 4 places.

The “only if” part is obvious—if the arrangement can be restored to the natural order
using legal moves, then it necessarily has odd parity since the sequence associated with
the natural order

(1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12, 15, 14, 13)

has 9 inversions and parity is not changed by legal moves.

Now suppose that we start with an arrangement with odd parity. Let us call the
2 × 4 board consisting of the first and second rows of the board Btop and the 2 × 4
board consisting of the third and fourth rows Bbot . Using the move T repeatedly, we
can move all numbers 1, 2, 3, . . . , 8 to Btop and the numbers 9, 10, . . . , 15 to the Bbot .
Again through a combination of the moves E 1 , E 2 , R1 , R2 , we can assume that 4 is
at the first row, fourth column, 8 is at the second row, fourth column, and 12 is at the
third row, fourth column with blank occupying the last row, last column. Now since
the parity of the board is odd, we have two cases to consider:
1. Btop has odd parity, Bbot has even parity, and
2. Btop has even parity, Bbot has odd parity.
1. Btop has odd parity, Bbot has even parity: Bring the blank cell to the second row,

Figure 21 Moves that shift a symbol by 6 places.

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
VOL. 90, NO. 1, FEBRUARY 2017 55
fourth column by pushing 12 to the fourth row, fourth column and 8 to third row,
fourth column. Since Btop has odd parity, the sequence (a, b, c, 4, 8, x, y, z) has
odd parity. Since 8 is involved in three inversions (all x, y, z are less than 8), the
sequence (a, b, c, 4, x, y, z) has even parity. Thus by Theorem 2, we can bring the
board Btop to the arrangement A2 (Figure 22). Now move 8 back to second row,

1 2 3 4 9 10 11 12
5 7 6 13 15 14

2 2

Figure 22 Btop and Bbot arrangement.

fourth column, 12 to third row, fourth column, and consider the bottom board Bbot .
Since this has even parity, again by Theorem 2, we can bring the board Bbot to the
arrangement A2 (Figure 22). Now, applying the move E 1 in A2 , we can change
it to A2 (Figure 23). Stitching together A2 and A2 , and moving 12, we obtain the

1 2 3 4
5 7 6 8
9 11 10 12 9 11 10
13 14 15 13 14 15 12

2 3

Figure 23 Bbot arrangement and full board.

arrangement in A3 . Now, applying the move E 1 to the second and third rows, we
obtain the natural order. This completes proof for this case.
2. Btop has even parity, Bbot has odd parity
Since Btop has even parity, the sequence (a, b, c, 4, 8, x, y, z) has even parity.
Since 8 is involved in three inversions (all x, y, z are less than 8), the sequence
(a, b, c, 4, x, y, z) has odd parity. Sliding 8 and 12 down, applying Theorem 2, and
sliding 8 and 12 up show that we can bring the board Btop to the natural order. Also,
since Bbot has odd parity, it can be brought to the natural order by Theorem 2. Now,
stitching these together, we obtain the natural order on 1, 2, . . . , 15.
A similar argument proves the following result.
Theorem 4. An arrangement of the numbers in the 4 × 4 board can be restored to the
order 13 − 15 − 14 if and only if the arrangement has even parity.
The above proof also gives an algorithm for restoring the board to one of the two
arrangements. The steps are as follows:
1. Move 1, 2, . . . , 8 to the top two rows, bring 4, 8, and 12 into their proper positions,
slide 8 and 12 down, bring 1, 2, . . . , 7 into the natural order or 5 − 7 − 6 order,
slide 8 and 12 back up.
2. (a) top board is in natural order, bottom board is in natural order: the full board is
in natural order

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
56 MATHEMATICS MAGAZINE
(b) top board is in natural order, bottom board is in 13 − 15 − 14 order: the full
board is in 13 − 15 − 14 order
(c) top board is in 5 − 7 − 6 order, bottom board is in natural order: Use E 1 in
second and third rows and again in third and fourth rows. The board will be in
13 − 15 − 14 order
(d) top board is in 5 − 7 − 6 order, bottom board is in 13 − 15 − 14 order: Use E 1
in second and third rows and again in third and fourth rows. The board will be
in natural order.
The above algorithm may not yield the optimal number of moves required to restore
the board. It is known that the 15-puzzle can be solved in maximum of 80 single tile
moves [11].
In general, permutation puzzles (e.g., [3, 4, 6]) are interesting and any discussion
of them involves some amount of group theory. Another famous permutation puzzle,
Rubik’s cube, has been studied extensively and there are algorithms for solving the
cube. The usual proofs in the literature for the 15-puzzle are all existence proofs—that
is, using the theory of permutation groups, one shows that there exists a set of moves—
without explicitly describing the moves—to restore any starting arrangement to one of
the two arrangements mentioned in the beginning of this paper. An arrangement is first
mapped to a permutation in the symmetric group S15 on 15 symbols (the blank cell is
assumed to be at the 16th place). One shows that an arrangement can be restored to
the natural order of the numbers 1 to 15 if and only if the mapped permutation is even.
The proof uses the fact that the subgroup A15 of even permutations is generated by the
3-cycles [1]. For the 15-puzzle, there are algorithms [6, 10] but none of the published
algorithms use a divide and conquer approach. They also appear to be specific to 4 × 4
board. The proof given in this paper provides a better intuition for solving the puzzle
and also extends to the more general N × N board.

Generalization It is easy to see that the above proof can be modified to prove that
for any board of size m × n, two arrangements can be reached from one another if and
only if they have the same parity.

Acknowledgment The author would like to thank the referees and the editor for their helpful suggestions
towards improving this paper. Thanks to Sachin Lodha for reviewing the draft version of the paper and for his
encouragement.

REFERENCES
1. A. F. Archer, A modern treatment of the 15 puzzle, Amer. Math. Monthly 106 (1999) 793–799.
2. B. Averbach, O. Chein, Problem Solving through Recreational Mathematics. Dover Publications, New York,
1980. 288–299.
3. T. A. Brown, A note on “Instant Insanity,” Math. Mag. 41 (1968) 167–169.
4. A. P. Grecos, R. W. Gibberd, A diagrammatic solution to “Instant Insanity” problem, Math. Mag. 44 (1971)
119–124.
5. H. Liebeck, Some generalizations of the 14-15 puzzle, Math. Mag. 44 (1971) 185–189.
6. J. Mulholland, Permutation Puzzles: A Mathematical Perspective, [Link]
math302/,2015.
7. Wm. Woolsey Johnson, W. E. Story, Notes on the “15” puzzle, Amer. J. Math. 2 (1879) 393–404.
8. D. Ratner, W. Manfred, Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is
Intractable. National Conference on Artificial Intelligence, 1986.
9. D. Ratner, W. Manfred, The (n 2 − 1)-puzzle and related relocation problems, J. Symbolic Comput. 10 no. 2
(1990) 111–137.
10. E. L. Spitznagel, Jr., A new look at the fifteen puzzle, Math. Mag. 40 (1967) 171–174.
11. [Link]

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]
VOL. 90, NO. 1, FEBRUARY 2017 57
Summary. We give an elementary, nongroup theoretic proof that exactly half of the 15! arrangements of the
fifteen puzzle can be restored to the natural order.

S. MURALIDHARAN (MR Author ID: 196417) heads Decision Sciences and Algorithms lab at Tata Consul-
tancy Services in Chennai, India. His research interests include analytics and algorithms.

1 2 3 4 5 6 7 8 9 10 11 12
A D O S S N A P S P I N
13 14 15 16
W I S P B O O B O O I O T A
17 18 19
O V A L O N T A P E D I S H
20 21 22
L O G I S T I C C U R V E
23 24 25 26 27 28
S T E N O C H I P O V I N E
29 30 31 32
E D U M A X I M A L
33 34 35 36 37 38 39 40
P T A O N E O V E R E M I L
41 42 43 43
L O N G I T U D I N A L W A V E
44 45 46
O L G A I C E C U B E D E N
47 48 49 50
T E L L A L L S I N
51 52 53 54 55 56 57 58 59
S T E I N I D E M C O S E C
60 61 62
L O G D E R I V A T I V E
63 64 65 66 67
M A Z E N E B U L A N E E D
68 69 70
A R E A C A R P E T O G R E
71 72 73
V E N N N A T S W E T S

SOLUTION TO PINEMI PUZZLE

7 ||| 7 5 ||| 6 | 6 || |

| ||| 11 | | | 6 ||| 8 5

||| 10 || || 11 7 | 6 | |

4 10 | ||| 11 ||| | 6 6 ||

| 6 ||| 11 || | | | | 9

6 | 10 || 7 7 | 9 ||| |||

|| || || 6 || 8 9 || 12 9

| 9 6 5 8 ||| || | || |

| | 5 | 9 || ||| 12 | |

| 5 || | || 7 8 ||| 6 |

This content downloaded from [Link] on Wed, 15 Feb 2017 05:37:34 UTC
All use subject to [Link]