PUZZLES THAT REQUIRE YOU to fit pieces into two- or three-dimensional forms are of widespread interest. Can rules be devised to simplify such a puzzle so that you need not consider every possible fitting? To look for rules I began with a common flat puzzle that forms a square. Then I reworked the puzzle on three unconventional game boards that wrap back on themselves. Finally I studied some three-dimensional puzzles invented by Adrian Fisher of Minotaur Designs. They appear to be the most difficult of their kind ever devised.

I began with a flat puzzle consisting of four pieces. How could they fit together to form a square? How many such solutions were there? The puzzle is simple enough so that you may be able to solve it mentally without actually fitting the pieces. I chose to analyze it systematically, hoping to discover rules of procedure that would serve on harder puzzles. My first game board was an empty square with four units on a side. Which piece should be played first onto the board? Since piece C extends by only two units vertically and horizontally, it has more possible positions in the square than the larger pieces do; those pieces extend three units in one or more directions. I decided to start with B, the largest piece.

B can have four orientations: T, inverted T, horizontal T with its head on the left and horizontal T with its head on the right. Since in each orientation the piece can be fitted into the square in four places, the total number of different beginning plays appears to be 16. For this first piece, however, there are really only four beginning positions, the seemingly missing 12 arise because I could rotate the piece in its own plane or turn the board upside down with the piece on it to achieve what at first glance would look like different positions. Such a reduction of orientations can be made only for the first piece played. Thereafter each additional piece must be considered in all its possible orientations. I chose the inverted-T orientation for my initial move with B.

B fits into the square in four places. Because B is symmetric about its vertical axis, however, location B2 is reduced to B1 if

you flip the puzzle. For the same reason B4 is the same as B3. Therefore B has only two unique positions in the square: B 1 and B3. It is not necessary to go further with B3 because the "holes" it leaves in units 9 and 13 of the game board are impossible to fill with any of the remaining three pieces.

I next played A. Five of the six ways it can be positioned leave impossible holes. Figure 3 shows a promising position (A1) and a futile play (A2).

Piece D is now added to A 1. Of the three ways it can be positioned, only one (D1) avoids impossible holes. Finally, piece C is added to complete the square. Since I have reduced the puzzle to a single route that results in a solution, it has only one unique solution. Id (Its mirror image is another solution 11 but not a unique one.)

By solving the puzzle in this way I learned several rules of procedure. The first piece played should be large in order to reduce the number of opening positions. The orientation of this first piece can be chosen arbitrarily because any other orientation requires only that the board be rotated in its plane or turned over. If the first piece is symmetric about at least one axis, you need not consider its mirror-image positions.

Some positions for a piece can be eliminated if they leave impossible holes, which are spaces that cannot be reached by the remaining pieces or that require unavailable shapes. One or two spaces left isolated along the side of the board are common examples. My game is dull because when the second piece is added, only one of its positions is viable. More interesting puzzles have several viable positions that you must continue to consider as more pieces are added.

While I was studying various puzzles I was also reading The Shape of Space: How to Visualize Surfaces and Three-dimensional Manifolds, by Jeffrey R. Weeks. In this fascinating book Weeks describes several games that are played on a flat surface such as my square board. They differ in that the edges of the surfaces are not real because the left and right edges are glued together, as are the top and bottom ones. If you mentally leave the square on the left side, you reenter through the corresponding unit on the right side. Similarly, an exit through the top brings you back into the square through the bottom. The square can be thought of as a flat representation of a torus, or doughout. Traveling left or right brings you around the full circle of the torus; traveling up or down takes you through the hole of the torus and back to the front. Weeks suggests that games can be played more clearly on this board if identical squares are drawn around the primary square. I call such an arrangement an extended game board.

Suppose my four puzzle pieces are played on the new board. Normally a piece cannot be played properly if it sticks out

of the square. On the new board such a play is allowed: the part that sticks "out" just sticks back in on the opposite side of the square. An example is shown in Figure 4. Note that B occupies three separate regions in the primary square.

The puzzle now has many more solutions, but are they unique? Imagine placing the normal solution on the board but shifting it one or more units horizontally, vertically or in both directions. The parts of the pieces that extend off one side of the primary square come back into it on the other side. For example, move the normal solution leftward as a whole by one unit. The leftmost parts of A and B end up on the right side of the square. Such simple displacements of the normal solutions are not new unique solutions.

A convenient way of representing the normal solution is depicted in Figure 5. B is in its normal orientation and the other pieces are clustered on its right. I call this display an expanded configuration. Imagine placing the configuration anywhere on the new board. As long as the sides of B are parallel to the sides of the board, the configuration fills the square neatly. For example, place it so that B is in the upper right of the square. Then the other pieces automatically disappear through the top and right sides of the square and reappear through the other sides to fill the square. The mirror image of this solution is also a solution but not a unique one.

Does the puzzle have other unique solutions? Yes, it does; I count four more, each with its own mirror image. One of them is shown in the illustration. Place the solution anywhere on the board; it precisely fills the square. You might enjoy finding the other solutions. You can systematically hunt for them according to the rules of procedure I have given for the normal puzzle. Or you can work with the expanded configurations, mentally flipping portions of the pieces that extend too far to the right or upward. Be wary of counting mirror-image solutions.

Another way to connect the edges of the game board is with a twist. The top and bottom edges are connected as before, but the left and right edges are mentally twisted and then glued together. This board is a flat representation of a Klein bottle, a topological novelty. If you mentally travel leftward from unit 1, you reenter the square to the left through unit 16. Travel either upward or downward is the same as in the flat-torus board.

The normal solution fits this board but cannot always be displaced successfully. Two more unique solutions are presented in the illustration at the right. Mentally place these solutions on the primary square of an extended board. Note that they can be displaced horizontally but not vertically. Also note that B has different orientations in these solutions. Since only the left and right edges are glued together with a twist, different orientations of the first piece played can no longer always be reduced to one orientation by a rotation of the board. How many unique solutions does the puzzle now have?

You can make a fourth type of game board by also connecting the top and bottom edges with a twist. (Technically this board is not a flat representation because of the way the corners fit together. Check the lower right-hand corner of the primary square: only units 4 and 13 glue together there, rather than four different units as in the other glued boards.) Errors are more easily avoided if you play on an extended version of this board. The illustration at the left shows how B might be played. It is evident that if the piece is displaced rightward by one unit, the play is no longer valid because the piece then occupies unit 4 twice. How many unique solutions of the puzzle does this game board have?

I chose the shapes of the pieces so that a solution on a normal game board is attainable. Is there another choice of shapes for a solution that is possible on only one of the boards? On the flat-torus board five unique solutions are possible with the pieces I played. If the puzzle were changed so that it had only one square piece four units on a side, each of the boards would have only one unique solution.

Imagine other shapes for the pieces, all different. What shapes maximize the number of solutions for each board? You

might like to explore larger puzzles to see whether general results can be devised for puzzles of any size.

I explored my simple puzzle to warm up for Fisher's three-dimensional puzzles. In developing them Fisher first examined the number of ways basic cubes can be attached to form different pieces, known collectively as polycubes. There are two tricubes (three cubes joined), eight quadcubes, 29 pentacubes and 166 hexacubes.

A popular game of fitting together polycubes to form a cube three units on a side is Soma, invented by Piet Hein and introduced in 1958 [see "Mathematical Games," by Martin Gardner; SCIENTIFIC AMERICAN, September, 1958]. You can find current notes on the game along with a bibliography in Gardner's recent book Knotted Doughauts and Other Mathematical Entertainments. The game employs one tricube and six quadcubes. (The straight tricube and quadcube and the square quadcube are not used.) The game has exactly 240 solutions.

Fisher wondered how the complexity of cube puzzles depends on the number of pieces in it. If the pieces were nothing but 27 individual and unattached cube units or even nine tri-cubes, the puzzle would hardly be puzzling. It would also be dull if it consisted of only two or three pieces. Fisher concluded that the best puzzle for a cube with three units on a side is one with six pieces. To check this assumption he tested students at a preparatory school in London; the test he set for them was to solve seven cube puzzles whose pieces ranged in number from three to nine.

Recording the average time spent on each puzzle and the percentage of correct solutions, Fisher found that the puzzle with six pieces did indeed take the most time and resulted in the least success. The puzzle with five pieces scored next, closely followed by the one with seven. Fisher designed more complexity into his puzzles by choosing pieces that are approximately the same size but none of which are identical or are mirror images of one another. When they are assembled, none touches a second piece on more than two faces.

One result of Fisher's efforts is the Minotaur Cube, which is made up of three quadcubes and three pentacubes. There is only one solution to form a -cube with three units on a side. The Minotaur puzzle can also be assembled into a stepped structure called a diamond solution, which resembles a crystal formation.

I began my search for the cube solution by listing the possible locations of 31 piece A, one of the larger pieces. This time

the board was an empty cube. As with the flat puzzles, the orientation of the first piece played is arbitrary because all other orientations are reducible to the chosen one when the board is rotated. For a given orientation A has four possible locations. I next added D, which has a total of 34 possible positions for all the possible locations of A. For each of them I considered all the possible positions of E. After three 15 or four pieces had been played I began to eliminate some configurations because they created impossible holes, but still the catalogue was large when I found the solution.

One reason a puzzle with three dimensions is more difficult than a flat one is that impossible holes are not as obvious; a hole left in one level might be filled by a piece played in another level. Impossible holes sometimes show up as an isolated hole or an isolated string of two or three holes on a side of the board. Some holes on the sides or in the interior are impossible in the sense that none of the remaining pieces can fill them.

Figure 11 shows the result of playing the pieces in the sequence A, D and E. When I played E, I was concerned with the hole in unit 12 in the first level because D bordered it on two levels. Which pieces can reach down into that hole? E can, but playing it makes unit 3 on the second level impossible to fill with any of the remaining pieces. B could be played, but it too soon leads to impossibilities.

A more economical way to search for a solution might be to concentrate on the most promising initial fittings. Begin with A. How can the other pieces be played so that they occupy part of the remaining empty region in the lowest level? For example, all the pieces can be turned in such a way as to occupy a single unit on that level, but only F can be turned so that it occupies three units in a row.

Make a list of these basic shapes. Then list the ways they can be combined to fill all the empty region. Four arrangements are shown in the top illustration on the left. The first two are more promising than the second two because of the number of pieces involved. Remember that the pieces will have to be compatible on the second level. Since the first two arrangements require only two pieces, they should be investigated before the arrangements requiring three pieces.

Which pieces can provide the first arrangement while also being compatible on the second level? There are only two

possibilities: either D and B or B and C. The rest of the search continues as the empty region on level 2 is filled with the remaining basic shapes. If the search reaches a dead end, return to the second promising arrangement that filled the first level. This procedure might reduce the chore of cataloguing all the possible fittings of the pieces. It does not guarantee success; for that only the full catalogue will do.

The Minotaur Supercube, which has four units on an edge, consists of eight pentacubes and four hexacubes. To say that it is difficult is an understatement. In designing it Fisher determined that the most challenging puzzle of this size is one with 12 pieces. As in the case of the smaller puzzle, the pieces are roughly the same size, but this time no piece is large enough to extend across the entire board.

The Supercube offers several puzzles. There are two ways the pieces can be assembled as a large cube. One of the solutions has a delightful twist. You can pick up several pieces as a whole and reposition them on the remaining part of the cube so that the final assembly is a "diamond solution." Similar stepped structures can also be built employing more than 200 other arrangements of the pieces, but not one of them can be "flipped" into a cube. In addition the pieces can be rearranged to form two cubes (three units on a side) and a small pyramid.

Finding a solution to the large cube formation calls for great patience or 1t keen intuition. To sample the complexity of the puzzle I began with one of the "uglier" hexacubes, turning it so that five of its basic cubes were in the lowest level of the game board. The hexacube had four possible locations in that level. It could be raised to the next level and to the one after that, each time having four more possible locations. Thus the piece has a total of 12 opening plays.

Choosing one of the plays, I added another hexacube. It had 96 possible positions. If two pieces are played, the puzzle has about 1,200 possible routes. I tested one route by playing a third piece, a pentacube. It had 44 possible positions. I explored each of them by considering the holes left in the game board and the remaining pieces. After I had played four or five pieces some impossible holes started to appear. Clearly this puzzle is difficult. Yet I have been told that one person found the solution that flips into a diamond and the solution to the two small cubes and the pyramid in about six hours.

Fisher has also studied larger puzzle structures. Of the 29 different pentacubes, you can form a cube with five units on a side with any 25. There are many such solutions. If you use all the different hexacubes and the square quadcube, you can build a cube that is 10 units on a side.

Fisher has also constructed pyramid puzzles that consist of pieces he calls "wedgehedrons." In designing the puzzle he began with two tetrahedron pyramids that are connected by an octahedron. These units can be connected in three ways so that no two tetrahedron faces touch each other. One of the ways results in a shape Fisher calls a wedge. The pieces for the wedgehedrons puzzle consist of different attachments of two wedges arranged so that no two tetrahedron faces and no two octahedron faces touch each other. When the pieces are assembled, this rule about similar faces not touching also applies to adjacent pieces.

The Minotaur Pyramid consists of five wedgehedrons with four tetrahedrons along each edge. Hidden within it are four empty tetrahedron spaces. The Minotaur Giant Pyramid consists of 10 wedgehedrons, has five tetrahedrons along each edge and contains five empty tetrahedron spaces hidden from view. Five of its pieces are identical with those of the smaller pyramid. Fisher has studied even larger pyramids, some of which require components made from the other two ways of connecting two tetrahedrons by means of an octahedron. All the pyramid puzzles are perplexing because the odd angles and curious "feel" prevent the player from developing any intuition about the fit of the pieces. You might enjoy searching for rules of procedure for solving these puzzles.

I leave you with a final challenge. Can Fisher's smaller cube puzzle be played on a board that has connected sides? The connections can either be direct or be made by means of a twist that is a quarter turn or a half turn. If they are direct, you can assemble the cube in the normal way and then displace it through the sides of the game board. Can you find new unique solutions for the cube on these boards? A simple example is shown in Figure 16.

Fisher's cube and pyramid puzzles are available from Minotaur Designs. North American readers should write to 247 Montgomery Street, Jersey City, N.J. 07302, all others should write to 42 Brampton Road, St. Albans, Hertfordshire AL1 4PT, U.K The smaller puzzles cost $20 (£12.50), the larger ones cost $38 (£24).

Bibliography

THE SHAPE OF SPACE: HOW TO VISUALIZE SURFACES AND THREE-DIMENSIONAL MANIFOLDS. Jeffrey R. Weeks. Marcel Dekker, Inc., 1985.

KNOTTED DOUGHNUTS AND OTHER MATHEMATICAL AMUSEMENTS. Martin Gardner. W. H. Freeman and Company, 1986.

The Society for Amateur Scientists (SAS) is a nonprofit research and educational organization dedicated to helping people enrich their lives by following their passion to take part in scientific adventures of all kinds.