Tiling Rectangles with Polyominoes

In this section, we approach the problem of tiling a rectangle by using pieces taken from a set of polyominoes. Naturally, the area of the rectangle has to be equal to the sum of the areas of the individual pieces in the set. Thus, we immediately know that it would be impossible to fill a rectangle of area 11 with dominoes or one of area 10 with triominoes, although it is not immediately apparent that we could fill a rectangle of arbitrary area (greater than 2) using dominoes and triominoes.

This section comprises three parts. The first one discusses tiling a rectangle allowing repetitions of the pieces taken from a given list. The second part will consider those tilings having no fault lines. Finally, in the last part we will tile using all pieces of a given set.

The function tess uses the backtrack method to construct all possible tilings of an rectangle with pieces taken from a given list poly. The optional argument justOneSolution is included in case we do not want all solutions. The function tess uses the recursive function tessAux, which implements the backtrack mechanism: all possible candidates for the placement of the next piece are computed and the lexicographically smallest one is chosen. Each piece, including its rotations and reflections, is placed, and then tessAux is called recursively. As the method works faster if , their values are swapped before and after computing the solutions. The function getLines takes a tiling and computes the endpoints of the horizontal and vertical lines forming the rightmost boundaries of the pieces of the tiling. The function tile displays a graphic array of the solutions of given width .

For instance, here is how to get all possible ways of tiling a rectangle with the L-triomino.

Even nonpolyomino pieces are allowed. Consider, for instance, the "number 8" piece , that is, two squares touching at a vertex, together with a domino in the tiling of a rectangle. Naturally, two number 8 pieces have to always be together forming a square in any tiling.

Here are all possible tilings of a rectangle by dominoes.

In general, the number of tilings of rectangles by dominoes is well known to be the Fibonacci numbers.

Here are all possible tilings of a rectangle by dominoes and the number of tilings of rectangles, .

Here is a generating function for these numbers [7].

Or, more explicitly [7].

Let us now explore the tiling of a rectangle with the L-triomino.

The number of such tilings is somewhat expected.

Using the complete set of triominoes, we obtain the following ([5, 6], seq. A001835).

Compare this sequence with the number of tilings of a rectangle by dominoes.

We now consider both sets of dominoes and triominoes together.

Let us now compute the number of ways of tiling an rectangle with dominoes. We know that has to be even; the symmetry of the problem allows us to proceed as follows.

The elements of the diagonal correspond to [5, 6], seq. A004003. Here is the corresponding result for triominoes [8].

The contributions to this result by the individual triominoes are small.

Although there are no tilings by the L-triomino and only two by the straight triomino, together they manage to tile in 10 different ways.

In general, an rectangle can be tiled with the L-triomino whenever is divisible by 3, except when one is 3 and the other is odd [9]. Here are some more general results corresponding to other cases.

The next two examples show the time needed to get one solution versus all solutions.

Fault-Free Tilings

As the number of different solutions grows, we would like to consider only those that have not appeared in smaller instances of the problem. For example, the tilings of a rectangle by the L-triomino include all those appearing when tiling two separate rectangles.

In tiling a rectangle, we might generate fault lines. A fault line is any horizontal or vertical line that divides a tiling so that it can be regarded as the union of the tilings of two subrectangles [10]. The function tileNF computes all fault-free tilings of an rectangle by a given set of pieces poly. As before, the graphic array of the solutions is considered to be of a given width . It generates the whole set of tilings and then selects the fault-free tilings, with the help of the predicate noFaultLineQ. This last function computes the length of the horizontal and vertical lines present in the tiling and verifies that no row or column has or elements, respectively.

We use this predicate to select the tilings without fault lines appearing in the previous example.

A more abundant example shows all fault-free tilings of a rectangle using the L-triomino.

Do tilings with dominoes always have fault lines? Not always.

Here are the smallest counterexamples.

Fault-free tilings produced by 3-ominoes are also interesting.

Like the tilings without restrictions from the previous section, the contributions of the individual pieces to this total are minuscule.

The smallest examples of fault-free tilings of squares by each polyomino produce patterns of striking beauty.

Jigsaws

Let us now approach the problem of tiling an rectangle using all the pieces of a list poly of given polyominoes once and only once. We naturally need to have Length[Flatten[poly]]=n m. The pieces appearing in poly do not need to be different and, with the inclusion of several equal ones, we can control their multiplicity. The functions tessAll and jigsaw, similar to our previous functions tess and tile, provide the necessary changes, which essentially amount to dropping a piece once used.

For instance, let us compute all possible tilings that also happen to be fault free using the set of pentominoes.

We can generate a tiling of the square with pentominoes by adding a square so that the sum of the areas is 64.

Unfortunately, the family of 35 hexominoes cannot tile a rectangle. In dealing with tilings with heptominoes, we have to consider that one of them has a hole and so we cannot tile a rectangle without a hole. For instance, in attempting to tile 12 squares (I thank the anonymous reviewer for this suggestion) in which a square has been removed from each one of them (so that their total area is 756, equal to the area covered by the 108 heptominoes), we just have to change the variable avail appearing in the function tess to construct the squares appearing on the diagonal of a square. This general approach takes too long and calls for another methodology, which the author hopes to report about in a future work.