The 15–Puzzle

The 15–puzzle is a children’s game (for children of all ages) to which we apply the theory of the symmetric group in order to make some adult observations.

The 15–puzzle is a 44 frame holding movable squares, numbered from 1 to 15 with one space left vacant (Figure-1). The squares may be moved horizontally or vertically into the vacant space, but no square may be lifted out of its plane. A simple move consists of sliding one square into the blank space, thus in effect moving the blank space to an adjacent position either horizontally or vertically.

The puzzle was first introduced in the 1870’s by its creator Sam Loyd, who was famous for many ether puzzle creations and for his chess problems. The task he proposed was to reverse the positions of blocks 14 and 15 by a sequence of simple moves and return the other squares to their starting position. Loyed wrote that his creation kept many people occupied for hours but no person succeeded its claiming the prize he offered for the solution.

Well, no surprize! We will prove no solution is possible. More generally, one may ask, what positions can be achieved by applying a sequence of simple moves starting position. For example, given the three positions in Figure-3, we will be able to tell rather quickly that only one of the positions may he reached from the starting position by a series of simple moves.

Now we set up the notation which permits us to solve this problem. Use the numbers 1-16 to indicate the locations in the frame which hold the squares. In the starting position, square 1 is in the location 1, square 2 is in the location 2 and so on; the blank space is in location 16 and we assign the number 16 to the “blank” square. The location numbers remain fixed; the numbered squares in the locations may change. After a series of simple moves, the numbered squares will be in different locations and the new position may be viewed as a permutation of the set {1, 2, 3  …… 16}.

Here, we describe the way in which the symmetric group enters the problem. Any permutation $$\sigma \in S_{16}$$ may be applied to an arrangement “A” of the puzzle to produce a new arrangement $$\sigma(A)$$, by the following rule:-

The square in location i of A is moved to the location $$\sigma(i)$$ in $$\sigma(A)$$ for each i = 1, 2, 3 ….16 .

For example, when the transposition (12, 16) is applied to the starting position, the square in location 12, which is the square numbered 12, is moved into the location of the blank square (location 16) and the blank square is moved to location 12, with the result in Figure-2.

In this case the permutation (12, 16) is accomplished by a simple move. If we apply the transposition (12, 16) to the arrangement indicated as position-I in the Figure-3, then the squares numbered 11 and 13 would be inter-charged; because they occupy locations 12 and 16. If is not evident that this could be accomplished by a series of simple moves. We are not assuming that every permutations of the starting position can be reached by a series simple move. In fact, the problem is precisely to determine which permutation can be achieved by a series of simple move. At this point we are simply describing the connection between permutations in $$S_{16}$$ and arrangement  of the squares in the puzzle frame.

For any permutations A of the square in the frame there is a unique permutation $$\sigma in S_{16}$$ such that $$\sigma(SP)=A$$, where  SP is the starting position. This gives the correspondence of arrangements with group elements. We now describe the permutations in $$S_{16}$$ that correspond to arrangements that arise after a series of simple move. We make a restriction by insisting that the blank square be returned to position 16.

——————————————————————-

Author: Neelam Saikia,

MSc. 2nd semester, Dept. of Mathematical Sciences,

Tezpur University.

——————————————————————-