Fun Fact - Polyominoes Make Interesting Puzzles

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 triomino, 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 are 4 in a row (order 1), a 2 by 2 square (order 1), the L piece (order 2), 3 in a row with 1 above the second (order 4), and the shape that looks like a set of stairs (no order, or order 0). Place a stair piece in the lower left corner, and a second piece must slide its tab under the gap created by the first. A third piece slides its tab under the gap created by the second, and so on, propagating along the floor forever. You can tile the first quadrant, but not a finite rectangle.

Most of the pentominoes have order 0 because they have the same tongue-in-groove problem as the stair tetromino. The rectifiable pentominoes are: 5 in a row (order 1), L shape (order 2), Utah (order 2), and 4 in a row with a square above the second (order 10).

Most of the hexominoes are easily solved, except for the Y hexomino, 5 squares in a row and another above the second. Here we have a modest 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 since discovered many other tilings. I find these patterns quite fascinating. They illustrate the incredible complexity and beauty of mathematics.

Y hexomino tiles a rectangle 23 by 24

Given any positive number n divisible by 4, there is a polyomino of order n. We can construct one in the shape of a boot. The toe of the boot is a set of stairs sticking out of the base of a tall rectangle. The opposite corner, at the back of the calf, has a corresponding gap. An odd number of boots stand next to each other, alternating right side up and up side down, and another boot lies across the top, its tow in the gap of the first boot. The result is half a rectangle, a composite shape of order 2. One can prove, geometrically, that such a boot has order n; I'll leave the details to you. These are known as Golomb's boots, named after Solomon Golomb. Here are some examples.

boots 1

boots 2

boots 3

As shown above, a boot that is 2 squares wide and 4k+2 squares tall has order 4k+4. But if a boot has nonstandard dimensions it may not tile a rectangle at all, or it may have an unpredictable order. The 2 by 9 boot has order 468.

Nonstandard boot tiles a rectangle 78 by 108

An open conjecture says that the order of every polyomino is even. This is not true when pairs of polyominoes conspire to tile a rectangle. Consider two pentominoes, the cross and the C. Place a C on each side of the cross to build a 5 by 3 rectangle showing order 3. However all the individual polyominoes seem to have even order, and in many cases an even order can be demonstrated through a geometric argument. Consider the tetromino with 3 in a row and 1 above the middle square. Since the shape comprises an even number of squares, any tiled rectangle has even area, and an even width or height. Overlay a black and white checkerboard on the rectangle. There are just as many white squares as black. Each piece consumes 3 white squares and 1 black, or 3 black and 1 white. Each piece introduces an excess or deficiency of 2 white squares. Excess must equal deficiency, hence the order is even. The checkerboard argument applies to many polyominoes, including the octomino shown below. Still others can be handled by black and white stripes etc.

Octomino tiles a rectangle 41 by 48

As of this writing, some polyominoes remain unsolved. My computer chugs on them in its spare time.

Here are two more tilings, two of many. All of these are my creations; please contact me if you would like to use them in posters, puzzles, etc.

Piece with flagpole tiles a rectangle 30 by 32

The following shape is built from 15 squares, hence the width or height of its presumed rectangle is divisible by 3. Overlay red, bllue, and yellow stripes to prove this shape has order divisible by 3.

L Piece tiles a rectangle 30 by 30

Traditional Hex Puzzle

If you are familiar with the Hex ™ puzzle, which has been on the market since 1965, 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, and I have written a C program to find all the solutions, as well as the 5×12, 4×15, and 3×20 rectangles.

12 pentominoes tile a 6 by 10 rectangle

Extended Hex Puzzle

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, as described above. 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 isosceles triangle. 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.

35 hexominoes in a triangular pattern

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.

35 hexominoes in a rhombus pattern

There are 108 heptominoes, but 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 program 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.

107 heptominoes in a long rectangle

Further Reading

Polyominoes and Tilings
Tiling the plane with pentagons