A Modern Treatment of the 15 Puzzle
Author: Aaron F. Archer
The American Source: The American Mathematical Monthly, Vol. 106, No. 9, (Nov., 1999), pp. 793799
Published by: Mathematical Association of America
Reviewed by: Sheila Lee
On our first day of class in Math 152, the following problem was on the board:
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
15 
14 

Kate presented the class with a seemingly simple challenge: by a series of moves swapping the blank cell and an adjacent cell, restore the puzzle so that the 14 and 15 are swapped with the blank still in the lower right corner. Whoever could achieve this would automatically receive an ‘A.’ We all knew it couldn’t be easy, and perhaps nearimpossible.
As it turns out, this puzzle, the 15puzzle, is impossible to solve. In “A Modern Treatment of the 15 Puzzle,” Aaron F. Archer discusses the history of the 15puzzle and presents proofs that show why it is unsolvable.
Designed by puzzlemaker Sam Loyd in the 1870s, the 15puzzle “drove the entire world crazy.” He describes, “People become infatuated with the puzzle and ludicrous tales are told of shopkeepers who neglected to open their stores; of a distinguished clergyman who stood under a street lamp all through a wintry night trying to recall the way he had performed the feat.” Of course, this madness is due to the fact that 15puzzle has no solution. Essentially, each move in the puzzle is a transposition of the blank block and an adjacent block. For the blank block to end up in its original location of the lower righthand corner, one must make an even number of moves. This is an even permutation. However, the result of the 14 and 15 switched requires an odd number of moves, which is an odd permutation. Hence, one cannot reach the desired solution.
The infamous puzzle has inspired a plethora of articles in mathematical literature. Key among them is the pair of articles published in the American Journal of Mathematics by W. W. Johnson and W. E. Story in 1879. Johnson explained why odd permutations of the puzzle are impossible to achieve, while Story showed that all even permutations are possible. The puzzle is also a popular topic in recreational mathematics.
While many references to the 15puzzle explain the impossibility of obtaining odd permutations and state Story’s result that all even permutations are possible, few proofs are known, and none of those are easy to understand. Archer hopes “to rectify that deficiency.” He also provides some generalizations of the 15puzzle, including R. M. Wilson’s extremely elegant but complicated proof, involving graph theory and Hamiltonian paths. I will focus on Archer’s simpler proof in my review.
Archer first develops some notation. The 15 pieces are blocks, and the 16 squares on the board are cells. The cells are numbered in a snakelike pattern:
1 
2 
3 
4 
8 
7 
6 
5 
9 
10 
11 
12 
16 
15 
14 
13 
If block i occupies cell j and the blank occupies a higher numbered cell, we say that block i is in slot j; otherwise it is in slot (j1).
A legal move is exchanging the blank block with one of its horizontal or vertical neighbors—“moving the blank”. Notice that if we move the blank block along the snakelike pattern, the order of the remaining blocks along the path remains unchanged. Thus, we can define an equivalence relation between placements if one can be obtained from the other by moving the blank along the snaking path. Thus, the resulting equivalence class contains 16 placements and is called a configuration. Since all placements in a given configuration have 15 blocks in the same slots, we can denote a configuration by [a_{1},…,a_{15}], where a_{i}_{ }is the slot that block i occupies in the configuration. As an example, here is the configuration C = [1,2,3,4,8,7,6,5,14,12,13,10,15,11,9]:
1 1 
2 2 
3 3 
4 4 
8 5 
7 6 
6 7 
5 8 
9

10 15 
11 12 
12 14 
16 13 
15 9 
14 11 
13 10 
Every legal move is a permutation on the slots. For example, let’s start with the initial configuration with the slots labeled as such:
1 
2 
3 
4 
8 
7 
6 
5 
9 

10 
11 
15 
14 
13 
12 
Then move the blank from cell 10 to 15 (once again, we label the slots):
1 
2 
3 
4 
8 
7 
6 
5 
9 
10 
11 
12 
15 

14 
13 
Moving the blank from cell 10 to 15 causes the permutation (10, 11, 12, 13, 14): the block originally in cell 15 (slot 14) is moved to cell 10 (and becomes slot 10), and the blocks in cells 11 through 14 get bumped up one slot (slots 10 becomes slot 11, slot 11 becomes slot 12, slot 12 becomes slot 13, and slot 13 becomes slot 14).
Now, we give some notation to permutations. Let σ_{i,j} be the permutation achieved by moving the blank from cell i to cell j. σ_{i,i+1 }is the identity (remember that moving the blank block in the snakelike pattern leaves the path unchanged), and σ_{j,i }= σ_{i,j}^{1}. Our permutations act on the right. There are only 9 more possible permutations (legal moves) in the 15puzzle:
σ_{1, 8 }= (1, 2, 3, 4, 5, 6, 7) σ_{2, 7 }= (2, 3, 4, 5, 6) σ_{3, 6 }= (3, 4, 5)_{ }_{} σ_{5, 12 }= (5, 6, 7, 8, 9, 10, 11) σ_{6, 11 }= (6, 7, 8, 9, 10)_{ }_{} σ_{7, 10} = (7, 8, 9)_{ } σ_{9, 16 }= (9, 10, 11, 12, 13, 14, 15)_{ }_{} σ_{10, 15 }= (10, 11, 12, 13, 14)_{ }_{} σ_{11, 14 }= (11, 12, 13)_{ }_{} σ_{n, n+1 }= id, n = 1, 2, …, 15_{ }_{} σ_{j,i }= σ_{i,j}^{1 }for all relevant i>j _{ }

Table 1. A summary of all possible permutations of slots attained by moving the blank block.
Archer proves that these permutations generate A_{15} (all even permutations), rigorously showing that all even permutations are possible. To outline his proof, Archer first shows that for n latex 3, all elements of A_{n} can be written as a product of 3cycles, then that all of these 3cycles can be written as the product of consecutive 3cycles (those of the form (k, k+1, k+2)). Finally, he shows that all of the permutations in the table above can be written as the product of consecutive 3cycles. Now, I’ll further outline the process:
Lemma 1. For n 3 the 3cycles generate A_{n }(all elements of A_{n} can be written as a product of 3cycles).
Proof: We know that all elements of A_{n} can be written as a product of an even number of transpositions (definition of A_{n}). We can group these transpositions in groups of two, and each of these groups can be written as the product of 3cycles. If a, b, c, and d are distinct, then (a, b) (c, d) = (a, b, c) (a, d, c), (a, b) (b, c) = (a, c, b), and (a, b) (a, b) =id.
Lemma 2. For n 3, the consecutive 3cycles {(1, 2, 3), (2, 3, 4), …, (n – 2, n – 1, n)} generate A_{n} (all 3cycles can be written as the product of consecutive 3cycles).
Proof: Since we know Lemma 1, it suffices to show that the consecutive 3cycles generate all 3cycles. This is proved by induction. The base case is n=3: (1, 2, 3) generates all 3cycles ( (1), (1, 2, 3), (1, 3, 2) ). For n 4, we see by induction that we can write all 3cycles not containing both 1 and n as a product of consecutive 3cycles. To generate (1, x, n), pick y $latex \in $ {1, …, n} \ {1, x, n}. Then (1, x, n) = (y, x, n) (1, x, y). This product can now be further broken down into the product of consecutive 3cycles. Finally, (1, n, x) = (1, x, n)^{2}.
Theorem 3. The cycles listed in Table 1 generate A_{15}.
Proof: The cycles in table 1 all have an odd number of elements, so they are even permutations. Thus, they generate a subgroup of A_{15}. We need to show that this subgroup is A_{15} itself. We see that this is the case:
(1, 2, …, 7)^{n} (3, 4, 5) (1, 2, …, 7)^{n} yields (1, 2, 3),…, (5, 6, 7);
(5, 6, …, 11)^{n} (7, 8, 9) (5, 6, …, 11)^{n} yields (5, 6, 7),…, (9, 10, 11);
(9, 10, …, 15)^{n} (11, 12, 13) (9, 10, …, 15)^{n} yields (9, 10, 11),…, (13, 14, 15);
for n = 2, 1, 0, 1, and 2. Thus, by Lemma 2, the cycles in Table 1 generate A_{15}.
Thus, given two configurations Cf_{1 }and Cf_{2}, Cf_{2 }can only be obtained if and only if Cf_{2 }is an even permutation of Cf_{1}. The 15puzzle is unsolvable because the desired configuration is an odd permutation of the initial configuration.
Note: supposedly, the puzzle was not created by Sam Loyd (http://mathworld.wolfram.com/15Puzzle.html). The actual inventor was Noyes Chapman.
Lots of toys and puzzles come down to group theory in the end! This is a particularly fun puzzle because of its history, but it’s also fascinating math. A similar approach could be used for other puzzles. In fact, online you can even find a 15style puzzle with hexagons.
One obvious question is that if this works with a 4by4 grid, what happens with an nbyn grid in general? The two lemmas aplpy to the nbyn case, so the part that needs generalising is the “snake” arrangement and the table of permutations you get by moving the blank by one square. Or even a 3by3 grid? It’s easy to try with a few pieces of paper on the table.
Another question that comes to mind is whether this leads to a method of solving the solvable positions of a slidingtile puzzle (like the solvable ones you get in the store with pictures of touristspots on them). In analogy with Rubik’s cube, people somewhere presumably have competitions to solve them quickly. What’s the general algorithm? Group theory should shed light on this question too.
By: Prof. Kate on January 13, 2009
at 8:40 pm
Hey u i am happy to see you here. U have Nice Blog Thank for sharing Article with me
By: Murana Table Lamps on November 13, 2009
at 2:53 am
I’ve been reading a book that mentioned that puzzle.Somehow I thought that the proof would be more simple,but good job :).
By: shredder on August 2, 2010
at 12:19 pm
Greetings from Warwickshire, England.
I thoroughly enjoyed that. Although do you need the lemmas and could you just say that because each of the permutations in the table are even, then you cannot start with an even configuration and end up with an odd configuration. Just wanted to ask this to make sure I understand. Anyway, very good post, I may be reading this blog quite often.
By: Seb Motala on November 27, 2010
at 8:10 am
I think Aaron Archer’s article in the Monthly has at least one error, which you’ve helped me verify, thanks!
By: Geoff Hagopian on April 6, 2015
at 9:48 pm
Ooops. No Archer’s article is fine. My bad!
By: Geoff Hagopian on April 6, 2015
at 10:27 pm