Cut The Knot!An interactive column using Java applets
by Alex Bogomolny
This article focuses on a variation of an old puzzle, called the Fifteen puzzle, invented by Sam Loyd in the early 1870's. The puzzle above contains 15 counters which can be moved using a vacant position in an attempt to reach this desired configuration. The original puzzle was constructed with the 14 and 15 counters permuted. A $1,000 prize was offered by the inventor to anyone who could solve the puzzle. Historical accounts of the puzzle indicate that it generated an excitement similar to the Rubik's cube in the 1970's. Despite this no one ever collected the prize. Why? The answer to this question is not difficult(1). Suppose you record your moves using (n,b), to indicate that you slid the counter n into the blank position. Then you would represent a sequence of moves, that start and end with the blank in the lower right hand corner, as (n1,b), (n2,b), ..., (nk,b), where k is an even number. So reachable permutations of the counters that fix the blank position are an even number of transpositions away from the desired configuration. This does not include the one which Sam Loyd was willing to pay money for, since it is a single transposition from the desired configuration. A mathematical explanation that the puzzle could not be solved (known to Loyd much earlier) surfaced in the early 1880's and the excitement petered out.
Richard Wilson , in 1974, gave a complete treatment of puzzles on graphs of which the Fifteen puzzle is a particular case. He considered labeling all but one vertex of a graph with counters and allowing a counter to move along an edge to the unlabelled vertex. He showed that 2-connected graphs without odd cycles generate precisely the even permutations of their counters (e. g. The Fifteen puzzle or similar puzzles of different sizes). The argument given in the previous paragraph could also be used here to show that only even permutations are possible. The existence of an odd cycle (but not just being an odd cycle) in a 2-connected graph (with at least 8 vertices) was enough to guarantee that any labeling could be generated. An example of a puzzle that will generate any labeling is Lucky 7 (so named and described in ).
We will give a proof here, independent of Wilson's theorem, that all permutations are possible.
Let L denote a clockwise rotation of the left cycle (click on position 1). Let little l denote a counterclockwise rotation of the left cycle (click on position 3). Similarly let R and r denote clockwise (click on position 7) and counterclockwise (click on position 5) rotations of the right circle. Then applying the sequence lRLrl(2) three times will swap counters 4 and 5, leaving the other counters fixed. With this sequence we now argue that any pair of counters can be swapped. Let x and y be any pair of counters. Rotate the outer circle (click on position 4, just below the vertical bridge) until one of either x or y is in position 5 and the other is in the left cycle. Now, if necessary, rotate the left cycle to get the other counter in position 4. Apply the sequence lRLrl three times to swap x and y. Now simply reverse the moves (both their order and direction) used to move x and y to these positions.
With digital technology it is now easy to create puzzles analogous to the Fifteen and Lucky 7 but with more elements. We can go one step further and construct puzzles that were not feasible in Sam Loyd's time. First, there is no need to restrict ourselves to planar surfaces. Fifteen can be played on a cylinder or a Möbius strip. More than that, there is no need to have the empty space either, as required by these mechanical puzzles. An interesting variation of the Fifteen puzzle that takes advantage of this great new technology is a puzzle called Sliders.
In this puzzle we are allowed to slide the rows and columns of the puzzle. On the torus version of Sliders, the counters simply wrap around the row or column they are in. Note that in this digital world there is no need for a vacant position. We can imagine, as Wilson did with the Fifteen puzzle, the slider puzzle on a graph. In addition to the 4x4 grid of vertices and edges, we would need eight new edges that connect ends of the rows and columns to form 4-cycles. The moves allowed on the graph would be to rotate the counters along these eight 4-cycles. Can we achieve all permutations of the counters or will we again be limited to just the even permutations? See what permutations of the counters you can produce.
Despite the similarities, this puzzle is much different from Sam Loyd's Fifteen puzzle. We will show that swapping the counters 14 and 15 does not result in an unsolvable arrangement. By this time you've noticed that odd permutations of the counters, as well as even ones, abound. Each move is an odd permutation.
We will first prove that the Sliders puzzle, for even sizes, played on the torus, can generate any permutation of its counters.
It is easy to see that there is enough freedom of movement to be able to move any two counters to any two positions (as long as we don't care where the other counters wind up). So consider the sequence (aBAba)(aBAba)(aBAba), where B represents moving the first row to the left, b to the right, A moves the first column up, and a moves it down. Applying this sequence swaps the counters in the 1 and 2 positions, leaving the other counters in their place. Give it a try! This shows we can swap any two counters by first moving them into these positions, swapping them, and then moving them back (taking care to reverse the moves used to get them there). Try swapping counters 5 and 12. Furthermore, (aBAba) applied five times, yields a transposition of the 1 and 2 counters in the 6x6 puzzle and (aBAba) applied seven times does likewise for the 8x8.
Note that the moves in the 3x3, 5x5, and the other odd sizes, give only even permutations of the counters. So, as with the original Fifteen puzzle, not all configurations are possible. Also, the sequence that switches the counters in positions 1 and 2 involves movements along just one row and one column. This is represented in the underlying graph by sliding counters along two 4-cycles that intersect in a single vertex. The same sequence could be used with any slider type puzzle that has two cycles that intersect in a single vertex, as long as one of the cycles is even.
Another variation of the Sliders puzzle defines the wrap around condition as though the puzzle is constructed on the surface of the Klein bottle. The columns wrap as before, but the first row wraps with the fourth and the second row with the third.
We will show that Sliders puzzle on the Klein bottle generates any configuration:
The method of proof is the same as before. We first note that it is not difficult to move any two counters to any two locations. It will be enough to find a sequence of moves that swap two counters, leaving the other counters fixed. Again let B represent moving the first row to the left (only now the bottom row moves left also), b to the right, A moves the first column up, and a moves it down. For the 3x3 puzzle on the Klein bottle, the sequence (abbAB) applied five times will swap counter 1 with counter 9. Try it! Note after doing abbAB we get the permutation (1, 9)(2, 4, 8, 3, 7). On the 4x4 puzzle (abbAB) yields the permutation (1, 16)(2, 3, 9, 14, 15, 4, 13). So if we apply it seven times we will have what we need to solve the puzzle. Likewise, (abbAB) raised to the ninth power will switch the two corner counters on the 5x5 puzzle.
The final variation of the puzzle defines the wrap around condition as though the puzzle is on the projective plane. Now the columns and rows wrap as the rows did in the Klein bottle version. The proof here follows the same line as the earlier arguments.
Again, it is easy to see that all we need to find is a sequence of moves that will swap two of the counters, leaving the rest in their place. For the odd size projective plane puzzles we can use the middle column and first row moves and apply the sequence used with the Klein bottle puzzle (or use the middle column and middle row and apply the sequence used with the torus puzzle). For even puzzles let: A and a represent moving column 3 (and column 2 along with it) up and down, respectively; and B and b represent moving the top row (and bottom row along with it) left and right, respectively. Then the sequence bAAbaBaBB applied nine times will swap the counters in positions 2 and 3. For the 6x6 puzzle, the same sequence applied fifteen times will swap the counters in positions 4 and 5. For the 8x8, applying the same sequence nine times will swap the counters in position 6 and 7. For the 10x10 apply it 39 times to swap 8 and 9. See the pattern? It would help to apply the sequence once to each of the 6x6, 8x8, and 10x10 puzzles and examine the permutation you get. How many times should it be applied to swap the 10 and 11 positions in the 12x12 puzzle?
We can formulate a similar "Puzzles on Graphs" problem as Rick Wilson did, but the situation seems far more complex. Consider a graph G which is formed by taking the union of k cycles. Place counters on the vertices and allow the counters to slide around each of these cycles. Under what conditions on the cycles and the graph will we be able to reach any configuration. The graph, so constructed, would need to be connected, but would not have to be 2-connected. There would have to be at least two cycles, and at least one of them would have to be an even cycle. For example: the graph for the 4x4 Torus Slider puzzle is the union of eight 4-cycles that are either pairwise disjoint or pairwise intersect in a single vertex; the graph for the 4x4 Klein Bottle Slider puzzle is the union of two disjoint 8-cycles and four disjoint 4-cycles (the 4-cycles each intersect the 8-cycles in two different vertices); and the 4x4 Projective Plane Slider puzzle Graph is the union of four 8-cycles that are either pairwise disjoint or intersect in 4 vertices (see picture).
If a graph G is the union of cycles C1, C2, ..., Ck and we know that G is connected, C1 is an even m-cycle, and C2 intersects it in a single vertex, then all configurations are possible. The Torus Sliders puzzle is a special case of this. Let a and A be counterclockwise and clockwise rotations of the counters on C1, and b and B be counterclockwise and clockwise rotations of the counters on C2. The sequence aBAba (used with the torus puzzle) applied m - 1 times will swap the vertex in common with the two cycles and its adjacent vertex on C2. Being connected is enough to guarantee that any two counters can be moved to these two positions. What about other ways that C2 can intersect C1? We conclude with a few special cases below(3).
If two cycles intersect in two adjacent vertices we have, as a special case, the Happy 8(4) puzzle (that is to Lucky 7 as Sliders is to Fifteen.) The graph of the Happy 8 puzzle would be the union of three cycles, C1, C2, and C3, where C1 and C2 intersect in an edge and C3 is the cycle formed by taking the union of C1 and C2 and throwing away their common edge. At least one of these cycles would be even for if C1 and C2 were both odd, then C3 would be even.
We can prove that all arrangements of the counters are possible for any size Happy 8 puzzle.
Indeed, the sequence LRlrLRc (where L and l are clockwise and counterclockwise rotations of the counters on the left circle, R and r are clockwise and counterclockwise rotations of the counters on the right circle, and c is a counterclockwise rotation of the counters on the outside cycle) will transpose the two counters at the center, bottom, right of the puzzle for all puzzle sizes containing more than 4 counters. The 4 counter Happy 8 puzzle can be solved using the sequence cl.
Suppose the cycles C1 and C2 intersect in two non-adjacent vertices. We have, as a special case of this situation, the Blithe 12 slider puzzle. The three 6-cycles pairwise intersect in two non-adjacent vertices. Try to find a sequence of rotations that swap two counters and leave the rest in their place. Can you find a sequence of rotations that only involve two of the three cycles?
Don Greenwell is Professor of Mathematical Sciences and Foundation Professor at Eastern Kentucky University. During his thirty years in teaching he has taught mathematics or computer science at Louisiana State University, Auburn University, Iowa State University, Emory University, and Arkansas State University. He holds M.S. and Ph.D. degrees from Vanderbilt University. He can be reached via his Homepage.
Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much programming exerience. He holds an M.S. degree in Mathematics from the Moscow State University and a Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at firstname.lastname@example.org
Copyright © 1996-1999 Alexander Bogomolny