Tiling Rectangles With Polyominoes

Tiling Rectangles With Polyominoes

What shapes can you make out of buckyballs?

A polyomino is a shape that consists of unit squares pasted together. This is an extension of the word domino, two squares placed side by side. But the word poly means meny, hence we may have many squares arranged to form a particular shape. Can this piece be used, over and over again, to tile a rectangle? If so, the order of the polyomino is the smallest number of pieces that will tile a rectangle. It is notoriously difficult to determine the order of even modest polyominoes.

Of course the polyomino might already be a rectangle, as illustrated by the domino. Thus it's order is 1 (not very interesting). A triominoe, three squares pasted together, can assume only two distinct shapes. The straight line has order 1 and the L shape has order 2. The 5 distinct tetrominoes have order 1, 1, 2, 4, and 0. The troublesome tetromino, that looks like a set of stairs, has order 0 because it cannot tile a rectangle. As you march along the floor of the rectangle, you must always slide another piece under the notch of the previous piece, and the pattern propagates forever. You can tile the first quadrant, but not a finite rectangle.

If you are familiar with the Hex ™ puzzle, which has been on the market for decades, you already know the 12 pentominoes well. The hex puzzle asks you to tile a 6×10 rectangle with these 12 pieces. This is an interesting problem in itself, and I have written a C program to find all the solutions, as well as the 5×12, 4×15, and 3×20 rectangles.

When I was in junior high I built the 35 distinct hexominoes out of lego and tried to fit them into a 14×15 frame. I even thought about marketing the puzzle, since the Hex puzzle (based on the 12 pentominoes) attained commercial success. But try as I might, I could not fit the 35 pieces into the frame. The puzzle wouldn't sell well if there was no solution! Finally I had an epiphany and applied the checkerboard argument. Most pieces cover 3 white squares and 3 black, but an odd number of hexominoes cover 4 white squares and 2 black, or 2 white squares and 4 black. This is a contradiction, hence there is no solution. (Wikipedia hexomino also gives this checkerboard proof.) Of course I could always toss out one of these offending pieces and try to tile a 12×17 rectangle with the remaining 34 pieces, but that is not aesthetically pleasing. I mean, which one do you toss out? The 35 hexominoes can however be packed into a right triangle, as shown by this program. This is a stroke of good fortune; 210 is a triangular number, and the triangle covers 110 white squares and 100 black squares. An example solution is shown below.

Other packings include the 15×15 square with a 3×5 rectangle removed from the center, and a rhombus 15 units high and 29 units wide with its center square removed. ssquare rhombus

You can pack all ominoes, from the single square up to the 35 hexominoes, into a rectangle that is 13 by 23.

There are 108 heptominoes, one has a hole in it and cannot participate in a solid packing. If you want a rectangle with a hole in the center, allowing for all 108, that's 108*7+1, 757, which is prime, so no dice there. All this is in wikipedia heptomino. However, I found that the 107 simply connected pieces can make a rather long rectangle 107 by 7. My first software took weeks and got nowhere, but then I change the order in which it considered the pieces, saving the nice corner pieces for last, and it found a solution in 21 seconds.

Returning to a single polyomino, most of the pentominoes have order 0 because they have the same tongue-in-groove problem as the stair tetrominoe. The viable pentominoes have order 1 (5 in a row), 2 (L shape), 2 (Utah), and 10 (4 in a row with a square above the second).

Most of the hexominoes are easily solved, i.e. they tile a rectangle with just a few pieces or they don't - except for the Y hexominoe, 5 squares in a row and another above the second. Here we have a simple shape consisting of 6 squares pasted together, yet we must write a computer program to determine whether it tiles a rectangle. I wrote such a program in 1987, and was the first to discover that this shape does indeed tile a rectangle, and its order is 92. Using variations of this program, I have discovered many other tilings. I find these patterns quite fascinating. They illustrate the incredible complexity and beauty of mathematics.

Click here for a parade of tiled rectangles. The base polyominoes in these patterns have orders ranging from 2 to 396. Note that these patterns and the software that produced them are copyright © Karl Dahlke, 2001, and cannot be used for commercial purposes (such as puzzles and games) without written consent.

Each picture in the previous link is actually derived from a matrix of letters. In other words, my software prints the solution as a grid of letters, which is then post-processed to produce the picture. Here is an example of such a matrix.

``````---------
aaabbbbbb
aaaaabbbb
aaaabbbbb
aaaaaabbb
---------
``````

The two pieces, indicated by the letters a and b, are 180° rotations of each other. They fit together to form a rectangle. Thus this polyomino has order 2. Click here for the machine-readable matricies that led to the pictures you saw earlier. An image magick program turns each ascii matrix into a picture.

Sometimes we can assert, via a combinatorial argument, that the order of a polyomino is a multiple of some number, even though we don't know what the order is, or even if the polyomino tiles a rectangle at all. In most cases we can assert an even order. The existence of an odd order polyomino is still an open question. Knowing something about the order in advance can be helpful in certain situations. For instance, if the order is divisible by 7, and you've found a rectangle with 56 tiles, you don't have to look for rectangles consisting of 54 tiles, or even 50. If you've ruled out everything up through 49, you're done; the order is 56. I have used this on more than one occasion to simplify my search. Here are some of the techniques used to constrain the order of a polyomino.

The gun theorem examines all polyominoes of width two. It is so named because the only interesting polyominoes in this class, which tile rectangles, look like guns. One shape, consisting of only ten squares, remains unresolved. Nobody knows if it tiles a rectangle or not. Click here for the gun theorem.

Like the last shape in the gun theorem, some polyominoes are especially troublesome. They may tile a large region - perhaps the entire quadrant - but they can't tile a rectangle. Here is an analysis of several specific shapes. None of these shapes tiles a rectangle, but that fact is far from obvious.

An L polyomino looks like the capital letter L. In other words, the shape is a rectangle with a rectangular notch removed from one corner. Many L polyominoes lead to interesting tilings. Here is a complete description of the L polyominoes. (Coming soon.)

The low order polyominoes can be completely characterized, although this task is not as simple as it first appears. For instance, the polyominoes of order 2 all look like broken rectangles, as indicated by the letter matrix shown earlier. Here is a complete characterization of the polyominoes with order <= 4. (Coming soon.)

Are you interested in sets of polyominoes? The general problem is undecidable, yet many interesting questions are within reach. People have explored pairs of pentominoes or hexominoes, asking which pairs can tile a rectangle. For instance, the C and + pentominoes have order 3 (as a set), even though neither can tile a rectangle on its own. My tiling program can analyze a set of polyominoes, provided all shapes in the set have the same number of squares. I am not investigating sets at this time, since the individual polyominoes are keeping me (and my computer) occupied. But if you would like me to analyze a particular set of shapes, please let me know.

You may be wondering about higher dimensions. Three dimensional polyominoes are built by pasting unit cubes together. Some can be used to tile rectangular boxes; others cannot. And the same is true in higher dimensions, beyond the boundaries of our imagination. An interesting inconsistency emerges as we move from 2 to 3 dimensions. In 2 dimensions a Flatlander would notice that some of the pieces in the "solution" were reflected through a mirror. He cannot imagine the 3-dimensional being that picked some of the pieces "up" and "flipped them over". He can only assume there were two sets of pieces, some left-handed and some right-handed, and somebody used pieces from either set, as he wished, to tile the rectangle. Indeed, polyomino tilings aren't very interesting if you don't do this. In contrast, we 3-dimensional beings are content with the 24 spatial orientations. It doesn't occur to us to reflect some of the pieces through a mirror, probably because we can't. Indeed, these reflections don't seem to be necessary - there are plenty of interesting patterns without them.

The thre smallest spacial tetrominoes are formed by placing a cube on top of an L triomino. These all have order 2. Interestingly, the stair tetromino, which could not tile a rectangle in the plane, has order 6 in 3 dimensions (Left as an exercise for the reader). The flat pentomino that looks like the letter C also has order 6. The spatial pentomino formed by placing a cube ontop of a 2×2 square has order 4. This is just the edge of a glorious, uncharted wilderness.

My tiling software, referenced earlier, would have to be completely restructured to handle 3-dimensional polyominoes.

There are of course other interesting web sites devoted to polyominoes. Click here for more information on sets of polyominoes, or rectifyable polyominoes. Wikiverse also has an entry for polyominoes.

If you are interested in tilings, or mathematical patterns in general, Brian Wichmann has assembled a large collection, from all branches of mathematics. They are available on a CD-ROM, carefully indexed and thoroughly documented. I was proud to contribute to this work. You can purchase this compilation, The World of Patterns, ISBN 981-02-4619-6, from WorldScientific.com.

You may also be interested in the book, Polyominoes, by Solomon W. Golomb. This is rated 5.0 out of 5 stars.