The Naive Approach

In this section we generate n-ominoes using a straightforward approach. We consider all possible 0-1 matrices and select those that are orthogonally connected, that is, that have no isolated blocks of ones. To check this property we read the first one and change its sign. We then mark those adjacent to it and repeatedly spread this changing of signs to those adjacent to them until no further changes occur. At the end, the new matrix cannot contain a one if the original matrix represented a connected shape.

The following function provides a canonical form for our matrices. It pushes the entire configuration up and to the left so that neither the first row nor the first column are all zero.

Our strategy is to generate all 0-1 matrices (there are of them), select those having n ones that are connected, convert them to canonical form, and, finally, remove repetitions from this list. For example, for , out of 65536 possible matrices we get only 1820 that have four ones, and, of those, 113 are connected. Only 19 are left when we select those with a different canonical form.

Although this is the simplest way, it takes nearly an hour to complete for , which forces us to look for another approach. If, instead of selecting those binary numbers having n digits that are 1 out of all possible, we generate them directly (there are of them), we will save a substantial amount of time. The function bin[n, b] computes all lists of length b having n ones.

We get the 63 canonical forms for the case more quickly.

However, some of these patterns are still equivalent under rotations and reflections, so more processing is needed. Although we have substantially reduced the computing time, we will not pursue this approach any further because there is a faster and more general alternative.