“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:
- 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},
- 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,
- 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,
- 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,
- 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 permutation 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.
2×2 RUBIK’S CUBE
The “pocket” Rubik’s cube has 6 sides, or faces, each of which has 2×2=4 facets, for a total of 24 facets:
______________
/______/u_____/ |
/______/______/| | 6 sides: front (f), back (b),
| | | | | left (l), right (r),
| | | r/| up (u), down (d)
|______f______ /| |
| | | | |
| | | |/
|______|______|/
Fix an orientation of the Rubik’s cube in space. Therefore, we may label the six sides as f, b, l, r, u, d, as in the picture. It has 8 subcubes. Each face of the cube is associated to a “slice” of 4 subcubes which share a facet with the face. The face, along with all of the 4 cubes in the “slice”, can be rotated by 90 degrees clockwise. We denote this move by the upper case letter associated to the lower case letter denoting the face. For example, F denotes the move which rotates the front face by 90 degrees to clockwise.
______________
/______/u_____/ | |
/______/______/| | |
/ \ | _|_ | | | |
| | / | \ | r/| | The move F
| |__ /__f__\___ /| | |
| | __ | | | | | |
| | |\__|__/ | |/ \ /
| |______|______|/
We label the 24 facets of the 2×2 Rubik’s cube as follows:
+--------------+
| 1 2 |
| u |
| 3 4 |
+--------------+--------------+--------------+--------------+
| 5 6 | 9 10 | 13 14 | 17 18 |
| l | f | r | b |
| 7 8 | 11 12 | 15 16 | 19 20 |
+--------------+--------------+--------------+--------------+
| 21 22 |
| d |
| 23 24 |
+--------------+
The 24 facets will be denoted by xyz where x is the face on which the facet lives and y, z (or z, y – it doesn’t matter) indicate the 2 edges of the facet. Written in clockwise order:
front face: fru, frd, fld, flu
back face: blu, bld, brd, bru
right face: rbu, rbd, rfd, rfu
left face: lfu, lfd, lbd, lbu
up face: urb, urf, ulf, ulb
down face: drf, drb, dlb, dlf
Exercise: Verify that the properties of a permutation puzzle are satisfied for this puzzle.
For future reference, we call this system of notation (which we will also use for the 3×3 and 4×4 Rubik’s cube) the “Singmaster notation”.
3×3 RUBIK’S CUBE
Much has been written on the Rubik’s cube (see, for example, [Ru] or[Si]). In this section we shall, for the most part, simply introduce enough basic notation to allow us to check that the puzzle is in fact a permutation puzzle.
The Rubik’s cube has 6 sides, or faces, each of which has 3×3 = 9 facets, for a total of 54 facets. We label these facets 1, 2, …, 54 as follows:
+--------------+
| 1 2 3 |
| 4 u 5 |
| 6 7 8 |
+--------------+--------------+--------------+--------------+
| 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 |
| 12 l 13 | 20 f 21 | 28 r 29 | 36 b 37 |
| 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 |
+--------------+--------------+--------------+--------------+
| 41 42 43 |
| 44 d 45 |
| 46 47 48 |
+--------------+
then the generators, corresponding to the six faces of the cube, may be written in disjoint cycle notation as:
F:= (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11),
B:= (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27),
L:= ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35),
R:= (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24),
U:= ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19),
D:= (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40).
Exercise: Check this.
The notation for the facets will be similar to the notation used for the 2×2 Rubik’s cube. The corner facets will have the same notation and the edge facets will be denoted by xy, where x is the face the facet lives on and y is the face the facet borders to. In clockwise order, starting with the upper right-hand corner of each face:
front face: fru, fr, frd, fd, fld, fl, flu, fu
back face: blu, bl, bld, bd, brd, br, bru, bu
right face: rbu, rb, rbd, rd, rfd, rf, rfu, ru
left face: lfu, lf, lfd, ld, lbd, lb, lbu. lu
up face: urb, ur, urf, uf, ulf, ul, ulb, ub
down face: drf, dr, drb, db, dlb, dl, dlf, df
Exercise: Verify that the properties of a permutation puzzle are satisfied for this puzzle.
Yet Another Mathblog 