From the Outside In
From the Outside In
Solving Generalizations of the Slothouber-Graatsma-Conway Puzzle
Abstract and Keywords
This chapter discusses Slothouber–Graatsma–Conway puzzle, which asks one to assemble six 1 × 2 × 2 pieces and three 1 × 1 × 1 pieces into the shape of a 3 × 3 × 3 cube. The puzzle has been generalized to larger cubes, and there is an infinite family of such puzzles. The chapter's primary argument is that, for any odd positive integer n = 2k + 1, there is exactly one way, up to symmetry, to make an n × n × n cube out of n tiny 1 × 1 × 1 cubes and six of each of a set of rectangular blocks. The chapter describes a way to solve each puzzle in the family and explains why there are no other solutions. It then presents several related open problems.
The Slothouber-Graatsma-Conway puzzle asks you to assemble six 1 × 2 × 2 pieces and three 1×1×1 pieces into the shape of a 3×3×3 cube, as shown in Figure 9.1. The puzzle can be quite difficult to solve on a first pass; it has only one solution up to the symmetries of the cube. By contrast, the well-known 3 × 3 × 3 Soma Cube has 240 different solutions.
If you have never tried to solve this puzzle, immediately stop reading and give it a shot! Your local hardware or hobby shop can provide the wooden cubes and glue, or you might find that the puzzle is not too hard to render on paper, or you might be able to find the puzzle at your favorite puzzle shop or online megastore.
The Slothouber-Graatsma-Conway puzzle has been generalized to larger cubes, and it is an infinite family of such puzzles, communicated by Andy Liu, that is the focus of this chapter. Our main result is the following.
For any odd positive integer n = 2k + 1, there is exactly one way, up to symmetry, to make an n × n × n cube out of n tiny 1 × 1 × 1 cubes and six of each of the following rectangular blocks:
Following Perković , let us call the 3 × 3 × 3 puzzle (when k = 1) the Slothouber-Graatsma-Conway puzzle, combining references to the puzzle’s sources in the literature. Certainly, the figures that appear in Cubics: A Cubic Constructions Compendium by the architects Graatsma and Slothouber , (p.128)
pp. 82–83, 108–109 show how to assemble the cube, even if these and other constructions in their book are not specifically offered as puzzles. Berlekamp, Conway, and Guy , pp. 736–737 describe the puzzle, unnamed but attributed to one of the book’s coauthors, with the 1×1×1 pieces considered as empty holes left by the other six pieces. The puzzle is given different names—such as “Slothouber-Graatsma puzzle” , “Conway’s Curious Cube” , and “Pack It In” TM—in different books and online puzzle resources.
The 5 × 5 × 5 puzzle in our family (when k = 2) is not to be confused with another 5 × 5 × 5 packing puzzle due to Conway, variously called “Blocks-in-a-Box” , “Conway’s puzzle” , and “Conway’s Cursed Cube” . That puzzle, which Conway created along with our 3 × 3 × 3 puzzle when he was a student at Cambridge, consists of three 1 × 1 × 3 rods, one 1 × 2 × 2 square, one 2 × 2 × 2 cube, and thirteen 1 × 2 × 4 planks. Our 5 × 5 × 5 puzzle is also attributed to Conway , but Conway shares credit for the puzzle with O’Beirne . This puzzle has been produced and sold under the names “Made to Measure” and “Shipper’s Dilemma” (it is one of several puzzles to be given the latter name). It was offered as Problem 213 in the problem section of Math Horizons in February 2008, communicated by Ben Bielefeld . Following a hint given in the September issue , Mark Sand’s Special Topics class at Dana College (Blair, Nebraska) found the unique solution, as evidenced by the model the class created from colorful Cuisenaire® rods taped together (Figure 9.2). (p.129)
The 7 × 7 × 7 puzzle in our family is attributed to Conway and Thiessen in Jerry Slocum mechanical puzzle collection (http://webapp1.dlib.indiana.edu/images/splash.htm?scope=lilly/slocum)
1 Placing Pieces
The two images in Figure 9.3 are taken from BurrTools, a fabulous free software package by Andreas Röver that solves packing puzzles of various types. The images show the solution of the 9×9×9 puzzle from two different perspectives, exhibiting the three-fold rotational and antipodal symmetries that are present in all solutions.
The main theorem is proved by means of a sequence of lemmas that restrict the placement of certain pieces, starting with the smallest and thinnest. We begin the proof by restricting the placement of the 1 × 1 × 1 tiny cubes. We define a slice of an n × n × n cube as any n × n square of cells a fixed distance from one of the six outer faces of the cube. For example, Figure 9.4 shows an orange slice of a 5 × 5 × 5 cube at distance 2 from the back left face.
Lemma 1 (Slice).
Each slice contains exactly one tiny cube.
Proof. Each of the slices of the cube is a square of size n × n. Since n is odd, a slice contains an odd number of cells. Notice that apart from the tiny cubes, each puzzle piece has two even side lengths, so it must intersect each slice in an even number of cells, regardless of its orientation with respect to the slice. For example, the blue 2 × 2 × 3 piece in Figure 9.4 intersects the orange slice in a 2 × 2 square. Thus, each slice must contain an odd number of tiny cubes, and so it must contain at least one of them. Since there are only n tiny cubes to go around, there must be exactly one in each slice.
While it is not needed for the rest of the proof, note that any piece except a tiny cube must intersect a slice in the same number of shaded and unshaded cells of a checkerboard coloring of the slice. For example, the blue piece in Figure 9.4 intersects two shaded and two unshaded cells of the slice. This further restricts the placement of each tiny cube, because in a checkerboard coloring of the entire cube, it must occupy a cell that is the same color as the corner cells of each slice that contains it.
The next step is to restrict the flat 1×2k×2 pieces to the outer faces of the cube.
Lemma 2 (Flat).
Each face of the cube has exactly one 1×2k×2 piece lying flat on it.
Proof. By Lemma Slice, there exists a tiny cube in the second slice away from each of the six outside faces. The single cell between this tiny cube and the outside face can only be filled by a 1×2k×2 piece: it can’t be filled by another tiny cube (doing so would put two tiny cubes in the same slice), and all of the other pieces are too thick.
We can now, finally, place a couple of tiny cubes in the outermost slices of the cube.
Lemma 3 (Corners).
The only tiny cubes in the outside slices of the cube are two tiny cubes in opposite corners of the cube.
Proof. No tiny cube can be in the interior of an outside slice or in the middle of one of its edges. To see this, consider Figure 9.5a, a bird’s-eye view of a tiny cube attempting to occupy the yellow cell on the bottom slice of a cube of arbitrary size. What pieces can occupy the adjacent cells labeled a, b, c, and d? By Lemma Slice, no other tiny cube can do it; and by Lemma Flat, at most one (p.131)
of the four cells can be occupied by a 1×2k×2 piece lying flat on the bottom face. Thus, the other three labeled cells must be occupied by pieces of height at least 2 above the bottom face. But this would leave an unfillable cell directly above the tiny cube in yellow.
The same type of reasoning applies in Figure 9.5b, with the tiny cube attempting to occupy the yellow cell on the edge of a slice. In this case, one of cells a and c could be part of a 1×2k×2 piece lying flat against the southern face, but as before this would still lead to an unfillable gap above the tiny cube in yellow.
With two corner cells now occupied by tiny cubes, we can place all of the 1×2k×2 pieces.
Lemma 4 (Propeller).
Three 1×2k×2 pieces surround each of the two corner tiny cubes, as shown in Figure 9.6b.
Proof. There are three cells adjacent to each corner tiny cube. If a piece thicker than a 1×2k×2 piece occupies one of these three cells, at most one of the other two cells could be occupied (necessarily by a 1×2k×2 piece). So these three adjacent cells must be occupied by three 1×2k×2 pieces lying flat against three different outer faces of the cube.
For k > 1, there are only two possible ways to place each of these three pieces up to symmetry, and Figure 9.6a shows why one of these can’t work: the red cell between the piece and right front face can’t be filled, because none of the three 1×2k×2 pieces adjacent to the tiny cube in the opposite corner can reach it. The propeller shape displayed in Figure 9.6b is then the only possible configuration, up to reflecting the propeller’s orientation.
piece next to a tiny corner cube. Placing all six pieces this way, and putting the final tiny cube in the central cell, completes the 3×3×3 puzzle.
For k > 2, we cannot yet place the propeller of three 1×2k×2 pieces adjacent to the other corner tiny cube, because we have not yet ruled out either of its two possible orientations. Regardless of which orientation is correct, we are forced to place two more tiny cubes as shown in Figure 9.7a, because no other remaining piece can fill either of those two cells without leaving an unfillable gap of width 1 next to one of the three nearby outer faces. When k = 2, the second propeller must be oriented antipodally with respect to the first one to allow the six 2×3×2 pieces to fill in the cells between the two propellers (in only one way), completing the 5×5×5 puzzle.
The next few diagrams are drawn as bird’s-eye views to more easily display the possible placements of important pieces. The labels on the pieces are heights above the bottom face, with all the cells below a labeled piece occupied. (p.133)
Figure 9.7b has an n in the upper right corner, because, regardless of which orientation is chosen for the propeller around that tiny cube, the column under that cell is now occupied.
In the final lemma, we place the 3 × (2k − 2) × 2 pieces and then the 2 × (2k − 1) × 2 pieces. I then explain why this lemma is essentially the final one we need.
Lemma 5 (Three).
For k > 2, each outside face of the cube has a 3×(2k − 2)×2 piece on it. The piece is oriented to have height 3 away from the face, and it is adjacent to a 1× 2k × 2 piece already placed. This forces the placement of the 2 × (2k − 1) × 2 pieces as well.
Proof. By Lemma Slice, there exists a tiny cube in the fourth slice away from each outside face. Due to the four tiny cubes already placed, this tiny cube must lie in the inner (n − 4)×(n − 4)×(n − 4) cube. The three cells between this tiny cube and the outer face can be filled only with a 3 × (2k − 2) × 2 piece: all other remaining piece dimensions are either larger than 3 or are even.
Where does the 3×(2k − 2)×2 piece lie on the bottom face? Not in the four types of placements shown in Figure 9.8: those leave unfillable gaps of width 1 in the spaces marked with an x.
So the only possible placement of the 3 × (2k − 2) × 2 piece is against the right wall, as shown in Figure 9.9a. Note the gap of width 3 above height 2 on the far left: this gap can only be filled with another 3×(2k − 2)×2 piece, which must be placed in the position outlined with dashes to avoid unfillable gaps of width 1.
The outlined 3 ×(2k − 2)×1 piece rests on top of a 1×2k×2 piece. By the symmetry of the pieces already placed, this forces all 3 ×(2k −2)×2 pieces to be adjacent to 1 × 2k × 2 pieces in the same way. Two such pieces are shown in Figure 9.9b. (p.134)
With the 3 ×(2k −2)×1 pieces now placed, the only way to fill in the gaps made by them is with tiny cubes and the red 2 × (2k − 1) × 2 pieces as shown in Figure 9.10.
When k = 3, filling in the central cell of the cube with the remaining tiny cube and choosing the antipodal orientation for the opposite corner is the only way to complete the 7 × 7 × 7 cube. When k = 4, the antipodal orientation is also the only orientation that allows the 9 × 9 × 9 cube to be filled in with the six 4 × (2k − 3) × 2 pieces, in exactly one way.
Finally, here’s the wonderful punchline to finish the proof of Theorem 1: replicate Lemma “Three” as Lemma “Five”, and then as Lemma “Seven”, and so on, up to Lemma “k” if k is odd or Lemma “k − 1” if k is even. To replicate, simply replace instances of the number 3 throughout the lemma with the number 5, and then with the number 7, and so on. (Of course, you’ll also need to alter related numbers by 2 at each step as well.) The point is that configurations of pieces already placed form thicker propellers, allowing an (p.135) identical argument to be made in each subsequent version of the lemma. For example, in the proof of Lemma “Five”, the 5 ×(2k−4)×2 pieces are forced to be adjacent to the 3 ×(2k−2)×2 pieces already placed, and the 4 ×(2k−3)×2 pieces will fill the gaps.
2 Puzzling On
Several open questions immediately come to mind. Are there other interesting infinite families of packing puzzles whose solutions are unique in a nontrivial way? Can some of the pieces we used in our family be subdivided, but still have the puzzle admit only one solution up to symmetry? And is there a snazzier proof of the uniqueness result just presented? Here’s a nice fact: if the outer cells of the solution to the n × n × n cube are shaved off, what’s left is the unique solution to the (n −2)×(n −2)×(n −2) cube. But I have so far been unable to use this idea as the basis of an alternate proof, one that works inside out instead of outside in.
There is a further generalization of the Slothouber-Graatsma-Conway puzzle that allows for even side lengths. For n > 2, make an n × n × n cube with n pieces of size 1 × 1 × 1 and three of each of the following rectangular blocks:
Notice that when n is odd, the pieces are exactly the same as those in the family considered earlier. When n is even, you get six of most of the pieces but only three pieces of size (n/2)×(n/2)×2. Our uniqueness proof for odd n doesn’t even get off of the ground for even n: Lemma Slice is no longer true, because the slices now have an even number of cells, and half of the pieces can intersect slices in an odd number of cells. There is no longer a unique solution for each n. BurrTools shows that there are 43 solutions to the 4 × 4 × 4 puzzle, up to symmetry, and 173 solutions to the 6×6 ×6 puzzle. It would be nice to know how the number of solutions grows as n increases.
Thanks go to Ben Bielefeld for introducing us to the 5×5×5 puzzle; to Andy Liu for introducing me to the generalizations for odd n; and to Bill Cutler and his puzzle-solving software for first assuring me several years ago that there is only one solution to the 7 × 7 × 7 puzzle.
 Anon. Hint in Problem Section. Math Horizons 16 no.1 (2008) 33.
 B. Bielefeld. Problem 213 in Problem Section. Math Horizons 15 no. 3 (2008) 32.
 E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning Ways for Your Mathematical Plays. Academic Press, Waltham, MA, 1982. (The second edition of Winning Ways was published by A K Peters in 2004.)
 S. T. Coffin. The Puzzling Word of Polyhedral Dissections. Recreations in Mathematics. Oxford University Press, Oxford, 1990.
 S. T. Coffin. Geometric Puzzle Design. A K Peters/CRC Press, Boca Raton, FL, 2007.
 J. H. Conway. Private communication, 2007.
 W. Graatsma and J. Slothouber. Cubics: A Cubic Constructions Compendium. Cubics Constructions Centre, Heerlen, the Netherlands, 1970.
 M. S. Perković. Famous Puzzles of Great Mathematicians. American Mathematical Society, Providence, RI, 2009.
 P. van Delft and J. Botermans. Creative Puzzles of the World. Key Curriculum Press, Berkeley, CA, 1993.