Feature Column from the AMS

Cubes

6. Cube puzzles

A variety of puzzles and toys are based on cubes. Far and away the most famous is Rubik's cube invented by Erno Rubik in 1974. For those young enough not to have lived through the Rubik's cube craze, the Rubik's cube consists of an ingenious mechanism for rotating the face panels of the cube with respect to one another. The Rubik's cube spawned a whole family of other similar puzzles, including one based on the dodecahedron. These puzzles encouraged the study of the groups associated with the puzzles. A variety of questions of a mathematical nature resulted from the puzzle. For example, what position(s) of the cube requires the largest number of "moves" to restore to its original position?

Another family of puzzles which involve the cube uses decompositions of the cube. The 3 x 3 x 3 cube can be thought of as being decomposed into pieces where 1 x 1 x 1 cubes are attached to each other along a square face. The most famous of these decompositions is the SOMA cube of Piet Hien, but there are other decompositions which are mathematically at least as interesting. These decompositions differ in the number of ways that the pieces can be assembled to get back the original cube and the difficulty of finding a solution. Some companies market families of cube decomposition puzzles rated by difficulty.

One of the most famous of mathematically based puzzles is the Tower of Hanoi. This puzzle, originated by E. Lucas, and its accompanying "story" have challenged young and old alike because of the complexity of the solution to what seems a simple challenge. The puzzle involves three poles with rings of different diameter placed initially on one of the poles in order of size, with the largest ring on the bottom. (The diagram shows the initial position of three rings on a pole; the color is present only to clarify the diagram.)

Three rings on one pole of a Tower of Hanoi

The goal of the puzzle is to move all of the rings from the initial pole to one of the other poles so that no ring of larger diameter is ever placed on one of smaller diameter and one ring at a time is moved. Solving the problem with 3 rings is not difficult (it involves 7 moves); the 4-ring version of the Tower of Hanoi requires 15 moves to solve. This might suggest a possible connection with the n-cube, because the numbers are one less than the number of vertices in ann-cube where n = 3 and n = 4!

A nifty connection between n-cubes and the Tower of Hanoi problem was indeed discovered by the geometer Donald W. Crowe, an emeritus professor at the University of Wisconsin in Madison. Crowe noticed a connection between the moves to solve the Tower of Hanoi puzzle and a way to construct a Hamiltonian circuit on ann-cube. A Hamiltonian Circuit (HC) of a graph is a tour of the vertices (moving along edges of the graph) which visits each vertex once and only once and returns to the vertex from which the tour started. Using the n binary coordinates to represent the vertices of an n-cube, one dimension corresponding to one ring, Crowe showed that each move of a ring could be coded by moving along an edge of the cube. Interestingly, it did not turn out that every HC of an n-cube always leads to a solution of a Tower of Hanoi with n rings.

The diagram below shows that a 3-cube has an HC.

Since one can think of building up the 4-cube from two copies of the 3-cube one can easily piece together the HC's on the separate copies of the 3-cube to get an HC on the 4-cube. The way this works can be seen in the diagram below. The HC in each of the separate cubes is now shown in blue, and the edges that are in the 4-cube that were added to complete an HC in the 4-cube are shown in red. Note that to get an HC on the 4-cube, one corresponding edge of each of the HC's in the component 3-cube had to be omitted. To avoid clutter in the diagram (below) the additional 6 edges joining corresponding vertices of the 3-cubes to create a 4-cube have been omitted.

For a variety of reasons HC's on an n-cube are of interest. A natural question is to ask how many different HC's there are on then-cube. The crux of the issue, as is typically the case in enumeration problems, is the meaning of the term "different." The usual definition of different for Hamiltonian circuits is that they use different edges. However, for a very symmetric object like the cube, one might want to consider two HC's different if no symmetry of the cube transfers one HC into another.