Two Approaches to Analyzing the Permutations

of the 15 Puzzle
Tom Howe
May 2017

Abstract
The permutations of the 15 puzzle have been a point of focus since the
1880’s when Sam Lloyd designed a spin-off of the puzzle that was impos-
sible to solve. In this paper, we explore which permutations of the 15
puzzle are obtainable by utilizing properties of permutations and results
from graph theory. We begin our investigation by using brute force to
obtain elementary permutations of the puzzle followed by simple proofs
to show that exactly half of the permutations of the 15 puzzle may be
obtained. While this approach is sufficient to demonstrate the properties
of the 15 puzzle, a more elegant proof using properties of simple graphs
yields us results that may be extrapolated onto other similar-style puzzles
that may be represented as simple graphs. The portion of this paper that
centers around graph theory is an exposition of Richard Wilson’s 1973
paper Graph Puzzles, Homotopy, and the Alternating Group.

1 Introduction
This paper will investigate which permutations of the 15 puzzle are obtainable.
The rules of the puzzle are relatively simple: the original sequence of the num-
bers in the puzzle (pictured below) are scrambled, and the solver must restore
the original configuration by strategically moving numbered squares into the
empty space.

1
The 15 puzzle was invented by a postmaster named Noyes Chapman in Canas-
tota, New York and was distributed by the Embossing Company around 1868.
However, the puzzle rose to prominence in 1878 when a prominent American
puzzle enthusiast named Sam Lloyd claimed that he had developed a new puz-
zle which was a modified version of the 15 puzzle [5]. However, the extent to
which Lloyd contributed to the success of the puzzle in its early days is not
certain. Lloyd’s puzzle was titled the 14-15 puzzle and frustrated many curious
minds who tried to solve it. The adaptation was identical to the original puzzle
except that the numbers 14 and 15 were switched in order. As we will explore
in this paper, restoring a puzzle configuration like this to the original sequence
as shown in the figure above is impossible.

Lloyd was prepared to offer $1, 000 to anybody who could solve his tricky puzzle.
The hype around the 15 puzzle was so significant starting in January 1880 that
the inventor of the puzzle, Noyes Chapman, applied for a patent on the puzzle
in March 1880. Nearly a century later, the inventor of the Rubik’s Cube, Erno
Rubik, claimed to have been inspired by the success of Lloyd’s 14-15 puzzle to
make another sensational puzzle [5].

Since Sam Lloyd’s capitalization on the popularity of the puzzle, many other
variations of the puzzle have arisen. Many of them form an image when com-
pleted or spell out a message.

Exactly half of all permutations of the 15 puzzle may be obtained. Only those
configurations that require an even number of transpositions between the empty
space and numbered tiles may be created. Aaron Archer proved in 1999 with
a simple set of logical steps that only half of the configurations of the puzzle
could ever be obtained by merely shuffling the tiles around. This short proof
demonstrated that Sam Lloyd was a clever opportunist who took full advantage
of the hype surrounding the puzzle by promising a juicy monetary prize to
someone for accomplishing a task he knew to be impossible.

This paper considers two approaches to investigating the possible configurations

of the puzzle: a graph theory approach and an abstract algebra approach. The
approach from an abstract algebra perspective is specific to the 15 puzzle and
involves the use of permutation groups and theorems. The graph theory ap-
proach will ask the reader to consider the puzzle as a 4 × 4 graph containing 16
vertices. One advantage to the graph theory approach is its generality relative
to the abstract algebra approach.

2
2 Abstract Algebra Approach
2.1 Nine Key Permutations

The 15 puzzle’s configurations are equivalent to the set of permutations of a set

of 15 elements. That is, the set of permutations of the 15 puzzle can be thought
of as the set S15 . Let us consider the puzzle’s configuration where the open
space is in the upper right corner, and the tile labeled “1” is in the square to
its left. If numbers trail from “1” going from right to left in the first row, then
left to right in the second, then right to left in the third, and left to right in the
final row, then we have a sequence of consecutive numbers 1-15. See Figure 1
below for an illustration of this configuration.

3 2 1 4 3 2 1

4 5 6 7 5 6 7 8

11 10 9 8 12 11 10 9

12 13 14 15 13 14 15
→
Figure 1: Typical 1-15 arrangement of the 15-puzzle. Notice that both puzzles
feature the same permutation of the fifteen numbered squares despite the fact
that the blank square has a different location in each configuration.

In this configuration of consecutive numbers, moving the empty square horizon-

tally within a row does not change the permutation of the 15 elements. However,
if the empty square is moved between rows (up and down), then it can change
the permutation of the 15 elements. However, the permutation generated by this
operation is even. Three examples of these permutations are given in Figures
2-4.

3
 4 3 2 1 4 2 1 5 4 2 1
5 6 7 5 3 6 7 3 6 7
11 10 9 8 11 10 9 8 11 10 9 8
12 13 14 15 12 13 14 15 12 13 14 15
→ →
Figure 2:
The even permutation (3, 5, 4) takes place when the empty space switches
places with the number 3. 3 ends up in the old position of 5, 5 takes the place
of 4, and 4 takes the place of 3.

4 3 2 1 4 3 1 5 4 3 1
5 6 7 5 6 2 7 6 2 7
11 10 9 8 11 10 9 8 11 10 9 8
12 13 14 15 12 13 14 15 12 13 14 15
→ →
Figure 3:
The even permutation (2, 6, 5, 4, 3) takes place when the empty space switches
places with the number 2. 2 ends up in the old position of 6, 6 takes the place
of 5, 5 takes the place of 4, 4 takes the place of 3, and 3 takes the place of 2.

4 3 2 1 4 3 2 5 4 3 2
5 6 7 5 6 7 1 6 7 1
11 10 9 8 11 10 9 8 11 10 9 8
12 13 14 15 12 13 14 15 12 13 14 15
→ →
Figure 4:
The even permutation (1, 7, 6, 5, 4, 3, 2) takes place when the empty space
switches places with the number 1. The sequence of the permutation is
determined using the same counting method from the previous two figures.

Since every movement of the empty square either preserves the current con-
figuration or alters the configuration in a way characterized by an odd cycle,
each movement of the empty square results in a permutation in which an even
number of elements swap positions.

4
2.2 Analysis of Permutations
There are a total of nine permutations that can occur on the configuration of
the puzzle in Figure 1. These permutations are as follows:

• p1 = (3, 5, 4) • p6 = (5, 11, 10, 9, 8, 7, 6)

• p2 = (2, 6, 5, 4, 3)
• p7 = (11, 13, 12)
• p3 = (1, 7, 6, 5, 4, 3, 2)
• p8 = (10, 14, 13, 12, 11)
• p4 = (7, 9, 8)
• p5 = (6, 10, 9, 8, 7) • p9 = (9, 15, 14, 13, 12, 11, 10)

Note that each of these permutations are even since they contain an odd number
of elements in their respective cycles. Since these are the nine permutations
that arise from moving the empty space between rows of the puzzle, we see
that the group generated from these nine permutations < p1 , p2 , p3 , ..., p8 , p9 >
generate all permutations of the puzzle. According to Joseph Gallian’s textbook
Contemporary Abstract Algebra 4th Edition, the product of any number of even
permutations is also even.

Notice that these nine permutations also form the set of consecutive 3-cycles of
A15 :

• (1, 2, 3) = p23 p21 p−2

3 • (8, 9, 10) = p−1 2
5 p4 p5

• (2, 3, 4) = p3 p21 p−1

3 • (9, 10, 11) = p29 p27 p−2
9
• (3, 4, 5) = p21
• (10, 11, 12) = p9 p27 p−1
9
• (4, 5, 6) = p−1 2
2 p1 p2
• (11, 12, 13) = p27
• (5, 6, 7) = p26 p24 p−2
6

• (6, 7, 8) = p6 p21 p−1 • (12, 13, 14) = p−1 2

8 p7 p8
6

• (7, 8, 9) = p24 • (13, 14, 15) = p−1 −1 2

9 (p8 p7 p8 )p9

So we see that we have every consecutive 3-cycle in our set of permutations of

the puzzle. We must now prove that every 3-cycle in An can be obtained from
products of the consecutive 3-cycles of An . That is, the set of three-cycles

(1, 2, 3), (2, 3, 4), ...(n − 3, n − 2, n − 1), (n − 2, n − 1, n)

form all 3-cycles in An . Additionally, we must show that every permutation of

An can be written as a product of 3-cycles.

5
Theorem 2.1. Every permutation in An is a product of 3-cycles
Proof. We will first show that every permutation of An can be written as a
product of 3-cycles. First, suppose that α ∈ An . We note that we can write
every permutation as a product of 2-cycles (Gallian 103). Let α be written as a
product of 2-cycles (x1 , y1 )(x2 , y2 ), ...(xk , yk ). k must be an even number since
it is expressing an even permutation α as a product of odd cycles. Therefore,
it is possible to group the transpositions into pairs and consider any potential
pairs of 2-cycles. There are three possible cases that arise in each pair.

Case 1: The two 2-cycles in the pair share the same elements- If this
is the case, then the pair of 2-cycles may be removed from the product since
(ab) ∗ (ab) = e.

Case 2: The two 2-cycles in the pair share one element, but each
2-cycle has a distinct element- In this instance, the pair of 2-cycle can be
written as a 3-cycle like so: (ab) ∗ (bc) = (acb).

Case 3: The two 2-cycles in the pair do not share a common element-
If the two 2-cycles are of the form (ab) ∗ (cd) = (bdc)(acb).

Thus, every permutation α ∈ An can be written as a product of 3-cycles. Now,

let us turn our attention to proving that the set of consecutive 3-cycles of An
can generate all others.
Theorem 2.2. The set of consecutive 3-cycles of An can form all other 3-cycles
of An
Proof. We will prove that the set of consecutive 3-cycles of An generates all
other 3-cycles of An by induction. Let us consider the base case A3 . We begin
with A3 because this is the smallest group of even permutations with a 3-cycle.
Looking at the 3-cycle (1 2 3), we observe that we may obtain the other 3-cycle
in A3 : (1 2 3)2 =(1 3 2). We have obtained all 3-cycles in A3 .

Let us prove another base case, A4 , for good measure. The consecutive 3-cycles
in A4 are (1 2 3) and (2 3 4). We may obtain all other 3-cycles in A4 via the
following operations:

• (1, 2, 3) = (1, 2, 3) • (1, 4, 3) = (2, 3, 4)2 (1, 2, 3)

• (1, 3, 2) = (1, 2, 3)2 • (1, 3, 4) = (1, 2, 3)2 (2, 3, 4)

• (1, 2, 4) = (1, 2, 3)(2, 3, 4)2 • (2, 3, 4) = (2, 3, 4)

• (1, 4, 2) = (2, 3, 4)(1, 2, 3)2 • (2, 4, 3) = (2, 3, 4)2

6
Let us now assume that the theorem holds true for some positive integer k where
k ≥ 3. Let us then consider the k + 1st case: We have the set of consecutive
3-cycles

(1, 2, 3), (2, 3, 4), ..., (k − 3, k − 2, k − 1), (k − 2, k − 1, k), (k − 1, k, k + 1)

Our mission is to show that we may create any 3-cycle with k + 1 in it from this
list. Note that our inductive hypothesis allows us to assume that the 3-cycles,
excluding (k − 2, k − 1, k) generate all 3-cycles in Ak . Let us consider three cases
to prove that any 3-cycle containing k + 1 is obtainable.

Case 1: Generate the 3-cycle with the form (a,k+1,k):

(a, k, k − 1) ∗ (k − 1, k, k + 1) = (a, k, k + 1)
Where a < k − 1. Note that our obtained 3-cycle may be squared to give us
(a, k + 1, k).

Case 2: Generate the 3-cycle with the form (a, k + 1, k − 1):

(a, k − 1, k) ∗ (k, k − 1, k + 1) = (a, k − 1, k + 1)
Where a < k − 1. note that our obtained 3-cycle may be squared to give us
(a,k+1,k-1).

Case 3: Generate the 3-cycle with the form (b,a,k+1):

(b, a, k) ∗ (a, k + 1, k) = (a, k + 1, b)
Where a, b < k − 1. We borrowed our 3-cycle (a, k + 1, k) from the result of case
1. Also observe that our obtained 3-cycle may be squared to give us (a, b, k + 1).

We have now proved that for any An where n ≥ 3, the set of consecutive 3-cycles
generates every 3-cycle in
The results above indicate that the set of permutations obtained by moving the
blank space between rows in the puzzle yield all possible permutations of A15 .
Thus, all even permutations of the 15 puzzle are possible to obtain. However,
none of the odd permutations may be obtained.

3 Graph Theory
Another way of thinking about the 15 puzzle is through graph theory. The
puzzle is essentially a 4 × 4 grid with 16 vertices. The paper “Graph Puz-
zles, Homotopy, and the Alternating Group”, authored by Richard M. Wilson
provides a series of proofs to theorems which delve into the nature of the 15
puzzle. The paper focuses on methods of labeling a graph with 15 elements and
a blank vertex. Sliding elements into the blank vertex yields a blank vertex in
the formerly occupied vertex.

7
Definition 3.1 (Labeling). A labeling on G is a bijective mapping f : V (G) →
{1, 2, ..., n, ∅}.
The vertex x with f (x) = ∅ is said to be unoccupied in f . That is, x is the
empty vertex. [4]
Definition 3.2 (Adjacent Labeling). Labelings f , g on G are adjacent if and
only if g can be obtained from f by sliding a label along an edge of G onto the
unoccupied vertex.
This relation of adjacency of labelings is symmetric and irreflexive and defines
a simple graph denoted puz(G). The vertices of puz(G) are labelings of G, and
two vertices of puz(G) are connected by an edge if and only if they are adjacent.
Each component of puz(G) is composed of labelings that may be obtained from
a series of “slides” which swap the empty vertex with an adjacent vertex’s label.
We now define a couple additional terms before proceeding with the proof.
Definition 3.3 (Bipartite Graph). A graph in which the vertices may be par-
titioned into two parts denoted A and B such that no two vertices within A (B)
are adjacent.
Definition 3.4 (Non-Separable Graph). Any graph that may not be discon-
nected by removing one vertex.
Theorem 3.1. Let G be a finite simple non-separable graph other than a polygon
or a theta graph. Then puz(G) is connected unless G is bipartite, in which case
puz(G) has exactly two components. In this latter case, labelings f ,g on G
having unoccupied vertices at even (or respectively, odd) distance in G are in
the same component of puz(G) if and only if f g −1 is an even (or respectively,
odd) permutation of V (G). [4]
The proof of this theorem will support our previous finding that exactly half
of the permutations of the 15 puzzle may be obtained starting from any given
arrangement. We first outline key definitions and put forward two propositions.

Let us define a path p in a graph G as a sequence

p = (x0 , x1 , x2 , ..., xn )

of vertices of G where xi−1 and xi are adjacent in G, i = 1, 2..., n. We call p a

path from the initial vertex, x0 , to the final vertex xn . A path p is said to be
simple when x0 , x1 , x2 , ...xn are distinct with the possible exception that x0 = xn
in which case p is a simple closed path. Also define ρ = (xn , ..., x2 , x1 , x0 ) to be
the reverse of p.

For each p = (x0 , x1 , x2 , ..., xn ) in G, let us define a permutation σp as the

product of 2-cycles shown below:

σp = (xn−1 , xn ), ..., (x2 , x3 , )(x1 , x2 ), (x0 , x1 )

8
The following two propositions are evident from these definitions.

Proposition 1: Labelings f , g on a graph G are in the same component of

puz(G) iff f = gσp for some path p in G from f −1 (∅) to g −1 (∅).

Let us define Γ(x, y) = ΓG (x, y) to be the set of all permutations σp of V (G)

where p is a path from x to y in G. We will abbreviate Γ(x, y) = ΓG (x, y) with
the expression Γ(x) = ΓG (x) if x = y.

Note that paths can be written transitively. For instance, if p is a path from x
to y and q a path from y to z, then one of the paths from x to z is the product
qp. In other words, σp σq = σqp . We are now ready to consider the second
proposition.

Proposition 2: For each vertex x of G, Γ(x) is a group of permutations of V (G),

each fixing x. If p is a path from x to y in G, then Γ(x, y) = σp Γ(x) = Γ(y)σρ
and Γ(y) = σp Γ(x)σp−1 .

These propositions, conjunction with Theorem 3.2 (below) and an assortment

of lemmas prove Theorem 3.1.
Theorem 3.2. Let G be a finite simple graph other than a polygon or the graph
θ0 . Then, for any vertex x of G,
Γ(x) =sym(V (G) − {x}),
unless G is bipartite, in which case
Γ(x) =alt(V (G) − {x}).

Note that sym(X) denotes the symmetric group of labelings on the set X while
alt(X) denotes the alternating group of labelings on the set X where X is the
set of vertices of G. Because of our propositions, it will suffice to show that
alt(V (G) − {x}) ⊂ Γ(x).

Let us now prove a theorem which will help us prove Theorem 3.2 by induction.
Definition 3.5 (Arc). An arc is a finite tree with exactly two monovalent
vertices–namely, its ends.
Theorem 3.3 (The Handle Theorem). Let G be a non-separable, simple graph
with at least three vertices and suppose that K is a non-separable proper subgraph
of G with non-empty edge set. Then we can write G = H ∪ A, where H is a
non-separable subgraph of G containing K, A an arc-subgraph of G, and H ∩ A
consists only of the ends of A.

9
Proof. This proof will require the consideration of two cases:

Case 1: |V (H)| = |V (G)|

In this instance, we notice that the subgraph H contains every vertex that G
contains. Since H is a proper subgraph of G and contains all vertices of G, it
may only omit one edge of G at most. If H omitted more than one edge of
G, then we would be able to find a larger subgraph of G and brand the new
subgraph H.

Case 2: |V (H)| < |V (G)|

In this instance, we notice that the subgraph H does not contain every vertex
that G contains. Suppose that a vertex v is in V (G) but not V (H). Let u be
a vertex of H. Since G is 2-connected, there is a cycle C containing v and u.
Following this cycle from v to u, Let w be the first vertex in H. Continuing
on the cycle from u to v, let x be the last vertex in H. If x 6= w, let A be
the path (x, v1 , v2 , . . . , vk , v = vk+1 , vk+2 , . . . , vm , w), that is, the portion of the
cycle between x and w containing no vertices of H except x and w. Since H
together with A is 2-connected, it is G, as desired [2].

If x = w then x = w = u. Let y be a vertex of H other than u. Since G is

2-connected, there is a path P from v to y that does not include u. Let vj be
the last vertex on P that is in {v1 , . . . , v, . . . , vm }; without loss of generality,
suppose j ≥ k + 1. Let z be the first vertex on P after vj that is in H. Then let
A be the path (u, v1 , . . . , v = vk+1 , . . . , vj , . . . , z), where from vj to z we follow
path P . Now H ∪ A is a 2-connected subgraph of G, but it is not G, as it does
not contain the edge {u, vm }, contradicting the maximality of H. Thus x 6= w
[2].

The Handle Theorem provides the basis of induction that we perform on simple,
non-separable graphs. We make the case that any non-separable graph is either
bipartite or not bipartite. Thus, every simple, non-separable graph G is such
that all labelings may be obtained from an initial labeling or only half may
be obtained. The only two exceptions to this are the polygon graphs and the
graph θ0 as shown below. However, the purpose of the following section is to
demonstrate that when pulling handles off of non-separable, simple graphs, we
can always remove a handle such that θ0 is not obtained. Before we launch into
this induction, let us define a measure of complexity for graphs.

Definition 3.6 (Betti number). The Betti number is a measure of the com-
plexity of graphs. A given graph G has a Betti number denoted β and is defined
as follows:
β(G) = |E(G)| − |V (G)| + 1.

10
If we add a handle (an arc) to a polygon, we obtain a group of graphs called
the θ−graphs which are non-separable graphs with two vertices of degree three
which have exactly three paths connecting them. θ-graphs also have a Betti
number of 2. The most simple of these graphs, we will call it U , is pictured
below.

a b

Every θ-graph is a subdivision of U . In other words, every θ-graph may be

obtained by dividing the three arcs of U into multiple edges by inserting vertices
on each arc. We will first note that Wilson proves that Theorem 3.2 is true for
θ-graphs. Thus, Theorem 3.2 is true for graphs with a Betti number of 2. We
now suppose that Theorem 3.2 is true for some graph G with β(G) ≥ 3. Let us
write G as H ∪A where H is a non-separable subraph of G with β(H) = β(G)−1
and A is an arc with only its end vertices in H. Below, we demonstrate that we
may choose H to be a graph other than θ0 (pictured below).

a b

f g c

e d

Note that we are only at risk of picking θ0 to be H if G has Betti number 3

and is of the form of one of eight graphs. Four of these graphs pictured below.
We show further below that we may avoid picking θ0 to be H by strategically
choosing which arc we designate to be A.

11
 a b a b

f g c f g c

e d e d
a b a b

f g c f g c

e d e d

Furthermore, each of these graphs can have one arc removed to yield a θ −graph
that is not θ0 . We will address each of the four graphs one case at a time.

Case 1:

a b a b

f g c f g c

e e
d
→ d

The resulting graph is a θ − graph that is not θ0 . This graph is designated as

H while the arc connecting vertices b and g is designated as the arc A.

Case 2:

a b a b

f g c f g c

e e
d
→ d

The resulting graph is a θ − graph that is not θ0 . This graph is designated as

H while the arc connecting vertices b and c is designated as the arc A.

12
Case 3:

a b a b

f g c f g c

e e
d
→ d

The resulting graph is a θ − graph that is not θ0 . This graph is designated as

H while the arc connecting vertices e and f is designated as the arc A.

Case 4:

a b a b

f g c f c

e e
d
→ d

The resulting graph is a θ − graph that is not θ0 . This graph is designated as

H while the arc connecting vertices c and f is designated as the arc A.

The remaining four cases are similar to the four shown, and the process of
removing an arc to yield a θ-graph that is not θ0 is also similar to the processes
shown above.

Now that we have established that H need not be θ0 , we may proceed with
induction assuming that Theorem 2 holds for H. With Theorem 2 established
for the graph H, we can write alt(V (G) − {x}) ⊂ ΓH (x) for each x ∈ V (H).
There is a result in graph theory analogous to our earlier proof that the group of
three cycles of a set of permutations form the whole group An . Wilson gives a
short proof of this in his paper. We now borrow one more theorem from Wilson.
Theorem 3.4 (Theorem 4). Let Γ be a transitive permutation group on X and
suppose that Γ contains a 3-cycle. If Γ is primitive (in particular, if Γ is double
transitive), then alt(X) ⊂ Γ.
Since ΓG (x) contains ΓH (x) which contains 3-cycles, we can invoke the result
of Theorem 4 and merely show that ΓG (x) is doubly transitive on V (G) − {x}.
Wilson demonstrates that this fact is true, and thus we have proven Theorem
2 for any graph G for which β(G) ≥ 2 excluding θ0 . Note that graphs with a

13
Betti number of 1 are polygon graphs which are excluded in the hypotheses for
Theorems 3.1 and 3.2. Theorem 3.1 follows closely from Theorem 3.2.

Because the 15-puzzle may be represented as a collection of 16 vertices arranged

in a 4 × 4 grid which is a bipartite graph, only half of its vertex lableings may
be obtained given a starting configuration. This furthers our findings from
the abstract algebra section of this paper. Because resolving the 14-15 puzzle
would require a single transposition (which means that this would be an odd
permutation of the tiles), the original configuration of the 15 puzzle may not be
obtained from the original configuration of the 14-15 puzzle.

References
[1] Joseph A. Gallian. Contemporary Abstract Algebra 7th ed.. Cengage Learn-
ing, Belmont, California, 2010. Print.
[2] David Guichard. Communication. Walla, Walla, WA.

[3] David Guichard. An Introduction to Combinatorics and Graph Theory Cre-

ative Commons, San Francisco, California, 2017. Web.
[4] Richard M. Wilson. Graph Puzzles, Homotopy, and the Alternating Groups.
Journal of Combinatorial Theory 16, 86-96, 1974. Web.

[5] The history of the 15 puzzle. [Link]

Web.
[6] Archer, A. F. A Modern Treatment of the 15 Puzzle. The American Mathe-
matical Monthly 106, 793-799, 1999. Web.

14