## 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.

If you are familiar with the Hex ™ puzzle, which has been on the market for decades, then you already know the 12 pentominoes well. The Hex puzzle asks you to tile a 6×10 rectangle with these 12 pieces. There are thousands of solutions, yet finding even one can be a challeng. See this program for help.

UURRRRXTTT
UUURFXXXTZ
LGAFFFXWTZ
LGAAAFWWZZ
LGGGAWWCZC
LLIIIIICCC

Most of the pentominoes have order 0 because they have the same tongue-in-groove problem as the stair tetromino. (See the W pentomino above.) 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.

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.

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.

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.

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

I'll close with 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.

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.

### 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. 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, 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.
 A AB ABS ABSS ABSSC ABBSCC DGGICEE DGGICEUU DDGICEUUU DFGIIEEHUL DFFNIWWHHL4 KFNNWWWHHL44 KFFNMMWHLLL4O KKKNNMVV5544O9 KTTTQMVVV55OO99 2TTTQMMV5577OO99 222QQQPJJJJ777393 Z2YYQPPPP1J876333X Z2ZYRRRP11J886663XX ZZZYYYRRR11188866XXX

Here is a rhombus with a hole in the center.

 ``` P NPPPP QNNNNPZZZ QQQQ44N4Z1Z66 IIIIQUU444Z116SSS CCCCCIIUUUM111669SSSW BBBBBCHHFFXUMMMM699888WWW AAAAAABHHHHFXX*OOM998833WWRRR DDDDDGGJFFXXXLOO9Y8553RRR DGGGGJKFLLLLOYYY55333 JJJJKEEEELOYTTT55 KKKEVVE72YTTT KVVV77222 V7722 7 ```

There are 108 heptominoes, but one has a hole in the middle and cannot participate in any tilings. If the remaining 107 pieces form a rectangle it has to be 107 by 7, since 107 and 7 are prime numbers. Indeed such a tiling is possible.

BbbeiiikkkmFFFFFCCssdddDDxxJJJJJubbbOOOOAAwwPPPvvvEEEEEEkkLLLLjjwwwwqDDDDpuuuuxxxWzzzQQnnMMMMJYYYYVVVRRGGGG
BhbeeeiiikmFmmKFKCCsssddDDxxxJJuuubbbbAOOAAwwPnvnvvvEXqqkkkkLLjjjjwwqqqqDppppuxWWWWWzQQQnnMooJYYKYVVRRRIGdG
BhbbbeikkkmmmKKKKKCCsddllDDDxxRuzuurAAAAOvAAwPnnnhXXXXXqqqkVLttjttlwqWWqDDpUpuxxfWHHzQQnnMMoJJJJKVVrRRIIGdd
BhhbaeecccfffgIIIIICslllppRRRRRzzrrrAEPPPvAwwPnTnhhhhXqqSVVVVVtttillllWWUUUUUuxffffHzzSmntoooJKKKKrrrrBIIId
ByhaaaccOcfgfgjjjIILLlpppooRozzzrrBrAEPPNvvvvPQTTTTThhSSSSSgVCiiiieellWWMUssEEffTTFHHHSmmttoYXXXZKrUUrBINNd
ByhhyaacOffgggjLLLLLClpHpHooozaaaBBBEEPPNvQQQQQDTZZZZcSccggggCCGiiGeeeeWMssssETTTFFHSSSmtttYYYXXZZZUUUBBNdd
ByyyyaOOOOOgjjjCCCCCCHHHHHoaaaaBBBEEENNNNNQDDDDDDZZZccccggCCCCGGGGGeMMMMMsEEEETTFFFFSSmmmtYYYXXZZZUUBBBNNNN