Tiling with Polyominoes

Squares tiles can be readily fitted together to cover the rectangular floor of a bathroom. If the floor happens to have dimensions that are whole-number multiples of a tile's width, you don't even have to trim any tiles to complete the pattern.

If each tile consists not of a single square but of a certain number of squares joined together along their edges to form a unit, the problem of determining whether you can use such tiles to cover a rectangular floor flawlessly gets more complicated.

Indeed, mathematicians have proved that the general question of whether it's possible to cover the plane (or even a smaller region, such as a rectangle) with identical copies of a given finite set of tiles (or even a single geometric figure) is, in principle, computationally undecidable. In other words, there's no cookbook recipe or handbook procedure that you can routinely apply to indicate whether you can fit together copies of an arbitrary shape to form a rectangle.

Mathematicians, however, have solved a variety of special cases of the tiling problem in two dimensions, particularly those that involve shapes known as polyominoes--forms that cover connected squares on a checkerboard. The term polyomino was coined in 1953 by mathematician Solomon W. Golomb, now at the University of Southern California in Los Angeles.

There is only one type of monomino (the unit square by itself) and one domino (two squares stuck together along one edge). There are two distinct trominoes (three squares) and five different tetrominoes (four squares). As the number of connected squares increases, the number of different possible configurations grows rapidly.

Simple polyominoes.

Polyominoes are the basis of thousands of mathematical puzzles. Cristopher Moore of the Santa Fe Institute in New Mexico has focused on the problem of determining how many different tilings of rectangles of various widths are possible using a given type of polyomino. In a recent preprint (http://xxx.lanl.gov/abs/math.CO/9905012), he calculates the number of ways a rectangle 4 units wide and n units long can be tiled with right trominoes.

Suppose you have a 4 x n rectangle, where n is a multiple of 3. It turns out that you need to consider only three types of interfaces when fitting right trominoes together into a strip of the required width and length. For example, two trominoes fit together to form a 2 x 3 rectangle, and two such rectangles stacked one on top of the other produce a 4 x 3 rectangle. There are four ways to do the stacking. These configurations all result from what Moore describes as a "straight" interface for building rectangular strips.

Two other interfaces are also possible: deep jog and shallow jog.

Examples of interfaces with a deep jog (left) and a shallow jog (right).

Because the number of possible interfaces is limited to three, Moore could derive a formula that gives the number of different ways to tile rectangles of different sizes. There are four ways to produce a 4 x 3 rectangle (see above), 18 ways to produce a 4 x 6 rectangle, 88 ways to produce a 4 x 9 rectangle, and 468 ways to produce a 4 x 12 rectangle. By definition, there is only one way to build a 4 x 0 rectangle.

[Technical details: The number of ways of tiling a m x n rectangle with any finite collection of shapes, where m is fixed, can be found by calculating the nth power of a matrix whose rows and columns correspond to the various interface shapes a partial tiling may have, Moore says. For the three interfaces possible for right trominoes, he solves a system of linear equations to obtain the formula, or generating function, G (z) = (1 - 6z)/(1 - 10z + 22z² + 4z³). The terms of the Taylor expansion of G give the number of ways to tile rectangles of size 4 x 0, 4 x 3, 4 x 6, and so on: 1, 4, 18, 88, 468, 2672, 16072, . . ..]

Moore also worked out formulas giving the number of different ways to tile rectangles of width 5 with right trominoes and rectangles of width 4 with L tetrominoes and T tetrominoes.

You can prove that T tetrominoes cannot tile any rectangles of width 5, 6, or 7. Indeed, a rectangle can be tiled with T tetrominoes only if its length and width are both multiples of 4.

Nonetheless, that still leaves a lot of different patterns you can try out when tiling your bathroom floor with polyominoes.

References:

Gardner, M. 1988. Polyominoes. In Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Mathematical Puzzles and Games. Chicago: University of Chicago Press.

Golomb, S.W. 1994. Polyominoes: Puzzles Patterns, Problems, and Packings, 2nd. ed. Princeton, N.J.: Princeton University Press.

Klarner, D.A. 1998. My life among the polyominoes. In Mathematical Recreations: A Collection in Honor of Martin Gardner, D.A. Klarner, ed. Mineola, N.Y.: Dover.

Moore, C. Preprint. Some polyomino tilings of the plane. Available at http://xxx.lanl.gov/abs/math.CO/9905012.

Peterson, I. 1990. Beyond chaos: Ultimate unpredictability. Science News 137(May 26):327.

______. 1990.Islands of Truth: A Mathematical Mystery Cruise. New York: W.H. Freeman.

______. 1987. Pieces of a polyomino puzzle. Science News 132(Nov. 14):310.

______. 1986. Games mathematicians play. Science News 130(Sept. 20):186.

Cristopher Moore has a Web page at http://www.santafe.edu/~moore/.

Additional information about polyomino tiling can be found at http://www.treasure-troves.com/math/PolyominoTiling.html, http://www.ics.uci.edu/~eppstein/junkyard/polyomino.html, and http://www.cwi.nl/~jankok/etc/Polyomino.html.

Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.