"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 left-to-right. 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 right-hand 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 square-shapped 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 east-to-west 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].