"How can it be that mathematics, being after all a product of human thought
independent of experience, is so admirably adapted to the objects of
reality?"
Albert Einstein
"Though this be madness, yet there is method in't."
Shakespeare
PERMUTATION PUZZLES
We shall describe several permutation puzzles. A "permutation
puzzle" is a puzzle consisting of several movable pieces connected
to a mechanism which controls their possible movements and which
has the following five properties listed below. Before listing
the properties, we define the "puzzle position" to be the data
consisting of the location of all the individual pieces along
with their orientation, if any. The five properties of a permutation
puzzle are:
(1) there is an enumeration of the movable pieces P1, ..., Pn
in such a way that each move of the puzzle corresponds to a
unique permutation of the numbers in T = {1, 2, ..., n},
(2) if the permutation of T in (1) corresponds to more than one
puzzle move then the the two positions reached by those
two respective moves must be indistinguishable,
(3) each move, say M, must be "invertible" in the sense that
there must exist another move, say M^(1), which restores the
puzzle to the position it was at before M was performed,
(4) if M1 is a move corresponding to a permutation f1 of T
and if M2 is a move corresponding to a permutation f2 of T
then M1*M2 (the move M1 followed by the move M2) corresponds
to the permutation f1*f2,
(5) each puzzle must be given an attainable "solved position"
which the puzzler can (in principle) attain.
NOTATION: As in step (4) above, we shall always write successive
puzzle moves lefttoright.
15 PUZZLE
One of the earliest and most popular permutation puzzles is the
"15 puzzle". The "solved position" looks like

 1  2  3  4 

 5  6  7  8 

 9  10  11  12 

 13  14  15  

These numbered squared represent sliding blocks which can only move
into the blank square. We shall sometimes label the blank square as "16"
for convenience. The moves of the puzzle consist of sliding numbered
squares (such as 12, for example) into the blank square (e.g., swapping
12 with 16). In this way, each move of this puzzle may be regarded as
a permutation of the integers in {1, 2,..., 16}.
Exercise: Check that the 5 conditions of a permuation puzzle are
satisfied by the 15 puzzle.
Not every permutation of the {1, 2, ..., 16} corresponds to a
possible position of the puzzle. For example, the position

 1  2  3  4 

 5  6  7  8 

 9  10  11  12 

 13  15  14  

cannot be attained from the previous position. (The mathematical
reason for this will be explained later.) Apparently, the puzzle
inventor Sam Loyd applied for a U.S. patent for the above puzzle
(the one with the 14, 15 swapped) but since it could not be
"solved"  i.e., put in the correct order 1, 2, ..., 15  no
working model could be supplied, so his patent was denied. (This
is in spite of the fact that there were apparently thousands of
them on the market already.)
The moves of the 15 puzzle may be denoted as follows: suppose
we are in a position such as

 *  u  *  * 

 l  16  r  *  16 denotes the
 blank square
 *  d  *  *  u,r,d,l denote
 any of the
 *  *  *  *  1, 2, ..., 15

The possible moves are generated by the four basic moves
R = R_{u,r,d,l} = (r 16) = swap r and 16
L = L_{u,r,d,l} = (l 16) = swap l and 16
U = U_{u,r,d,l} = (u 16) = swap u and 16
D = D_{u,r,d,l} = (d 16) = swap d and 16
Exercise: Verify that the 5 defining properties of a permutation
puzzle are satisfied by this example.
We shall call the 15 puzzle a "planar puzzle" since all its
pieces lie on a flat board.
DEVIL'S CIRCLES (or HUNGARIAN RINGS)
This is a planar puzzle consisting of two or more interwoven
ovals, each of which has several labeled (by colors or numbers)
pieces, some of which may belong to more than one oval. A puzzle
move consists of shifting an oval by one or more "increments",
and hence all the pieces on it, along the oval's grooved track.
The pieces are equally spaced apart (in spite of the typed
depiction below) and those pieces which lie on more than one
oval can be moved along either oval.
For simplicity, consider the puzzle consisting of only two
ovals, each having 6 pieces (I have added *'s to make the shape
of the ovals clearer on the page):
7 * * 6
* 1 *
8 2 10 5
* 3 *
9 4
The pieces 1 and 3 can be moved along either oval. Note that
each move corresponds to a unique permutation of the numbers in
{1, 2, ..., 10}. For example, rotating the righthand oval
clockwise one increment corresponds to the permutation
[ 1 2 3 4 5 6 7 8 9 10 ]
[ 6 1 2 3 4 5 7 8 9 10 ],
which we may write in cycle notation as (6 5 4 3 2 1). This new
position may be depicted as
7 * * 1
* 2 *
8 3 10 6
* 4 *
9 5
Exercise: Verify that the 5 defining properties of a permutation
puzzle are satisfied by this example.
EQUATOR
This puzzle is in the shape of a sphere but has 3 circular
bands encircling a sphere, each having 12 squareshapped pieces and
each band intersecting each other at a 90 degree angle. Each
pair of circles intersects at two points, or "nodes", and at each such
node there is a puzzle piece shared by the two circular
bands. There are 6 nodes total. The total number of movable pieces is
therefore 3x12  6 = 30.
On the sphere is painted a map of the earth. The longitudinal
band circles the equator, one latitudinal band passes through
North America and the other latitudinal band passes through
Europe and Africa. A move of the puzzle consists of rotating
one of the bands (along with all the pieces it contains) in
either direction. Successive puzzle moves may change the "orientation"
of a piece, as we will see later. When the 30 pieces are such
that the puzzle is a correct map of the Earth then we call the
position "solved".
For ease of drawing, let us redraw the globe of the Earth
using the "Mercatur projection", i.e., as a wall map:
1 1 1 1
2 13 12 22
3 14 11 21
4 23 24 15 25 26 10 27 28 20 29 30
5 16 9 19
6 17 8 18
7 7 7 7
The "solved" position
Sometimes we shall also denote 1 by NP ("north pole") and 7 by SP
("south pole").
This description is a little misleading due to the fact that it tells
us where a piece is but not, for example, whether it is
upside down or not. We shall ignore this problem for now
and simply describe how a move affects the position of a
piece. We see from the above labeling that any move of the
Equator puzzle corresponds to a unique permutation of the
integers in {1, 2, ..., 30}. For example, the move which
rotates the equator easttowest by 30 degrees corresponds
to the permutation
(4 30 29 20 28 27 10 26 25 15 24 23).
Now we shall show to assign an orientation to a piece.
We shall regard an orientation (which is, after all, simply an
indication of what angle the piece is "twisted") as an integer
0, 1 ,2, or 3. First, if a piece is not in its correct
position, it gets an orientation of 0. If a piece is in its
correct position then it gets a 0, 1, 2, or 3, depending on
its angle from the correct angle (i.e., the angle the
piece has in the "solved" position):
0



3  1



2
For example, a piece which has been rotated by 90 degrees
counterclockwise from its correct orientation gets an orientation
of 3.
In general, the labels for the pieces of the Equator puzzle
should be choosen from the set given by the Cartesian product of
the set of integers used to label the positions, {1, 2, ..., 30},
by the set of integers used to label the orientations:
S = {1, 2, ..., 30}x{0,1,2,3}
= { (m,n)  1 <= m <= 30, 0 <= n <= 3}.
Each move of the Equator corresponds to a unique permutation of
the set S. There are 120 elements of S, call them
S = {s1, s2, ..., s120}.
If we identify the set S with the set T = {1, ..., 120} then
we move of the Equator corresponds to a unique permutation of
the set T.
Exercise: Verify that the Equator puzzle satisfies the 5 defining
properties of a permutation puzzle.
Question: Can you show the following: If a piece is correctly
oriented then its antipodal piece is also correctly oriented?
NOTATION: We introduce notation for 3 basic moves of the
Equator puzzle which generate all possible puxzzle moves.
Let us label the three circular bands on the globe as C1, C2, and
C3. Let C1 be the band which, in the solved position, contains the
pieces labeled 1, 2, ..., 12; let C2 be the band which, in the
solved position, contains the pieces labeled 7, 13, ..., 22; and
let C3 be the band which, in the solved position, contains the
pieces on the equator. Let r1 be the puzle move associated to
the rotation of C1 given by
[ 1 2 3 4 5 6 7 8 9 10 11 12 ]
[ 2 3 4 5 6 7 8 9 10 11 12 1 ].
Let r2 be the puzzle move associated to the rotation of C2 given by
[ 1 13 14 15 16 17 17 18 19 20 21 22 ]
[ 13 14 15 16 17 17 18 19 20 21 22 1 ].
Let r3 be the puzzle move associated to the rotation of C3 given by
[ 4 23 24 15 25 26 10 27 28 20 29 30 ]
[ 30 4 23 24 15 25 26 10 27 28 20 29 ].
It is clear after a little thought that each of these moves
corresponds to a permutation of the 120 position/orientation labels
of the pieces of the equator puzzle. Furthermore, such a permutation
determines the puzzle position uniquely since it specifies the
facet's position and orientation.
Exercise: Verify that the remaining properties of a permutation puzzle
are satisfied.
Solution strategy, in brief:
First, ignore the orientation of the pieces. Just try to get the
pieces in their correct position. One of the most remarkable properties
of this puzzle is that GAP (a group theory computer program we will
discuss more later) is, in practice, very efficient at solving this
part of the solution. (This is remarkable in view of the fact that GAP
is not very good at solving the corresponding problem for the Rubik's
cube, for example, so there is no reason to expect it to be good at
solving this problem.)
Second, once the pieces are in the correct position, they must be
correctly oriented by a catalog of "node" moves designed for that
purpose. Some "node" moves are included below. Some notation: if x, y,
and z are moves, let
[x,y,z] = x^(1)*y^(1)*z^(1)*x*y*z.
We call a move of the form [r1^(3k),r2^(3m),r3^(3n)] a "node move"
since it only affects the nodes (where the circles intersect). The
table below records where each node goes as well as its effect on the
orientation. For example, [r1^3,r2^3,r3^3] will swap the NP and
SP, while rotating the NP by 90 degrees in a counter clockwise
direction. Moreover, it will fix the position of the piece labeled
as 20 but will rotate it by 90 degrees clockwise. The position entry in a
block is the position the piece moves to. The angle entry, if any,
is the angle the piece gets rotated by. No angle entry means, of
course, that the piece is not rotated. No position entry means that
the piece was not moved (but may have been rotated). If a move has no
effect on the position or the angle then we fill in the block with a
"".
In the following table, NP, SP have been denoted by 1,7, resp., for
brevity.
move\piece  1  7  4  10  15  20

m123  7,90ccw  1,90cw  10,180  4,180  90ccw  90cw
m132  7,180  1,180  90ccw  90cw  20,90cw  15,90ccw
m231  7,180  1,180  90cw  90ccw  20,90cw  15,90ccw
m213  90cw  90ccw  10,90cw  4,90ccw  20  15
m312  90ccw  90cw  10,90cw  4,90ccw  20  15
m321  7,90ccw  1,90cw  10,180  4,180  90cw  90ccw
A  180  180  180  180    
m321^2          180  180
B      180  180    
n123  1,90ccw  7,90cw  10  4  20,90ccw  15,90cw
D      90cw  90ccw  90cw  90ccw
where
m123 = [r1^3,r2^3,r3^3],
m132 = [r1^3,r3^3,r2^3],
m231 = [r2^3,r3^3,r1^3],
m213 = [r2^3,r1^3,r3^3],
A = m123*m132*m213,
B = C*m321^2*C^(1), C = (1 4)(7 10) = r1^3,
n123 = [r1^3,r2^3,r3^3], D = [r1^3,r2^3,r3^3].