Posted by: sclee09 | November 7, 2008

Reading Project: The 15-puzzle

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. 793-799
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 near-impossible.

As it turns out, this puzzle, the 15-puzzle, is impossible to solve.  In “A Modern Treatment of the 15 Puzzle,” Aaron F. Archer discusses the history of the 15-puzzle and presents proofs that show why it is unsolvable. 

Designed by puzzlemaker Sam Loyd in the 1870s, the 15-puzzle “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 15-puzzle 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 right-hand 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 15-puzzle 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 15-puzzle, 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 (j-1).   

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 [a1,…,a15], where ai 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 15-puzzle:

σ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 A15 (all even permutations), rigorously showing that all even permutations are possible.  To outline his proof, Archer first shows that for n \geq latex 3, all elements of An can be written as a product of 3-cycles, then that all of these 3-cycles can be written as the product of consecutive 3-cycles (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 3-cycles.  Now, I’ll further outline the process:

Lemma 1.  For n \geq 3 the 3-cycles generate An (all elements of An can be written as a product of 3-cycles).

Proof: We know that all elements of An can be written as a product of an even number of transpositions (definition of An).  We can group these transpositions in groups of two, and each of these groups can be written as the product of 3-cycles.  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.  \square

Lemma 2.  For n \geq 3, the consecutive 3-cycles {(1, 2, 3), (2, 3, 4), …, (n – 2, n – 1, n)} generate An (all 3-cycles can be written as the product of consecutive 3-cycles).

Proof: Since we know Lemma 1, it suffices to show that the consecutive 3-cycles generate all 3-cycles.  This is proved by induction.  The base case is n=3: (1, 2, 3) generates all 3-cycles ( (1), (1, 2, 3), (1, 3, 2) ).  For n \geq 4, we see by induction that we can write all 3-cycles not containing both 1 and n as a product of consecutive 3-cycles.  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 3-cycles.  Finally, (1, n, x) = (1, x, n)2.  \square

Theorem 3.  The cycles listed in Table 1 generate A15.

Proof: The cycles in table 1 all have an odd number of elements, so they are even permutations.  Thus, they generate a subgroup of A15.  We need to show that this subgroup is A15 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 A15.  \square

Thus, given two configurations Cf1 and Cf2, Cf2 can only be obtained if and only if Cf2 is an even permutation of Cf1.  The 15-puzzle 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.

Advertisements

Responses

  1. 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 15-style puzzle with hexagons.

    One obvious question is that if this works with a 4-by-4 grid, what happens with an n-by-n grid in general? The two lemmas aplpy to the n-by-n 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 3-by-3 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 sliding-tile puzzle (like the solvable ones you get in the store with pictures of tourist-spots 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.

  2. Hey u i am happy to see you here. U have Nice Blog Thank for sharing Article with me

  3. I’ve been reading a book that mentioned that puzzle.Somehow I thought that the proof would be more simple,but good job :-).

  4. 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.

  5. I think Aaron Archer’s article in the Monthly has at least one error, which you’ve helped me verify, thanks!

  6. Ooops. No Archer’s article is fine. My bad!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: