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 [3],
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 [1]).
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 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?
Reference
- E.R.Berlekamp, J.H.Conway, R.K.Guy, Winning Ways for Your Mathematical Plays, v2, Academic Press, 1982.
- The Lighter Side of Mathematics, R.K.Guy and R.E.Woodrow (eds), MAA, 1994.
- R. M. Wilson, Graph Puzzles, Homotopy, and the Alternating Group,
J. of Combinatorial Theory, Ser B 16, 86-96 (1974).
Endnotes
(1) As simple as the argument is, it apparently did
not come up during the decade of initial craze in the United States and
Europe that followed invention of the puzzle. The puzzle became classic
ever since and has been included into various puzzle collections, none
of which, to my knowledge, gave an explanation close in simplicity to
Don's. However, for the general case, or even for the second puzzle
distributed by Sam Loyd (the left upper corner blank with counters
arranged in the natural order) a more general argument is needed.
(2) The applet has a "Cycles" button. When the button
is checked, the permutation that represents the current state of the puzzle is shown as a product of cycles. In particular, lRLrl = (1 3 2)(4 5)(6)(7). Therefore, (lRLrl)3 = (4 5).
(3) We use this opportunity to introduce additional
sliding puzzles. The special case of the Fifteen puzzle on the cylinder
and the Möbius strip is left as an exercise.
(4) In a chapter in [2], J.A.Eidswick describes a
family of circle puzzles generalizing the one known as
Engel's Enigma. The latter, like the Happy 8 puzzle, is a
union of two cycles; but there are two distinct types of nodes -
stones and bones - that permute
independently. Generalizations compare favorably in complexity with the
Rubik cube puzzle.
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
alexb@cut-the-knot.com
Copyright © 1996-1999 Alexander Bogomolny
