Polyominoes

The straightforward approach presented in the previous section has many disadvantages. The representation of polyominoes as 0-1 matrices is wasteful because they are very sparse. In this section we consider a polyomino to be a list of unit squares, where a square is specified by the Cartesian coordinates of its bottom-left vertex; further, these coordinates will be encapsulated as complex numbers. So, a polyomino will be a list of Gaussian integers; that is, complex numbers having integral real and imaginary parts. We thus define the following type.

In this definition we cannot use the pattern _Complex.. because only numbers with nonzero imaginary parts have head Complex.

To determine whether two figures are equivalent, we consider the action of the dihedral group , where r rotates the figure by 90° and f turns it over. Given a polyomino, we then have at most eight different equivalent polyominoes.

If we were using a matrix m to describe the positions of the squares forming a polyomino, we could perform a 90° rotation with Reverse[Transpose[m]] and a reflection with Transpose[m].

The following functions act on a given polyomino p; rot and ref correspond to the transformations r and f. The function cyclic computes the list of the rotations of p and is used in the construction of produced by the function dihedral. (In this case cyclic is equal to NestList[rot,p,3].) The function canonical computes a standard representation of p by removing repetitions and sorting. The functions liC and polC convert a list of complex numbers into a list of points to be drawn as lines or as polygons. The arguments of the functions cyclic and allPieces are not restricted to polyominoes as they will also be used for the other families.

The function draw generates the graphical object with an optional second argument specifying the plot range. Note also the change in the representation of a polyomino; the function canonical places the polyomino in the first quadrant touching both axes. Here is an example.

The function allpieces computes all eight equivalent figures (or less for some polyominoes).

The following incremental method generates all n-ominoes. Having generated the set of all -ominoes, we take each of its members and append a square to each of its squares in all four possible directions. Once we have this extended set containing all the n-ominoes, we obtain their canonical representation and proceed to eliminate the redundant ones.

We can now compare the time taken to generate all pentominoes with the time it took in the previous section. Because Mathematica uses dynamic programming to retain the generated n-ominoes, the time it takes to recompute old values will only amount to how long it takes to retrieve them and hence would be negligible. So for a fair comparison, we have to start anew so that all previous values are cleared. Let us restart the Mathematica kernel and evaluate the following after all initialization cells are evaluated.

We can now obtain the number of free n-ominoes (free meaning equivalent under rotation and reflection) ([5, 6] seq. A000105).

As an illustration, let us generate all 108 heptominoes, because it is not until that a hole appears. According to our definition, a polyomino can have one or many interior holes. Can you spot the one having a hole among the following heptominoes? (That is the reason we color the squares; otherwise, it would be impossible to distinguish it.)

We can also obtain the one-sided (no reflections allowed) or "chiral" polyominoes by running the following cell, which redefines function allPieces, rerunning the previous function polyominoes, and computing the table as was done before ([5, 6] seq. A000988). At the end of the generation of this table, we have to recover the original definition of allPieces because it is needed in the next section. The easiest way is to restart the Mathematica kernel, evaluate the initialization cells, and continue with the cells in the next section.