3.2.6  Polyominoes

A plane region without "holes", formed by n edge-to-edge adjacent squares is called a polyomino (Golomb, 1994). Instead of squares we could use n equilateral triangles or n regular hexagons, and obtain, respectively, polyiamonds or polyhexes. We will restrict our discussion to polyominoes (with polyiamonds and polyhexes the situation is absolutely the same). For every polyomino we could distinguish its shape and orientation ("left" and "right" form). For polyominoes not having a reflective symmetry, we may distinguish (or not) their "left" and "right" form. According to that we have two possible equality criteria: 

  1. considering only the shape (without distinguishing "left" or "right" form); 
  2. considering both shape and orientation.

Till now, there is no formula for calculating the number of different polyominoes. We have only some results (for smaller values of n) obtained by empirical (computer) derivation. 

In a polyomino with the borders consisting of mirrors, in every border square cell we can introduce two-sided mirrors perpendicular to the internal edges at their midpoints. After a series of reflections, the ray of light will "describe" a shape called a closed Dragon curve. If we denote a reflection in a border mirror by 0, and a reflection in an internal mirror by 1, we have 0-1 words (or symbols) for polyominoes, where these words are cyclically equivalent. For n = 1 we will have only one polyomino 0000, for n = 2 the polyomino 00010001, for n = 3 two polyominoes: 000101000101 and 000100100011, for n = 4 five of them: 0001010100010101, 0001010001100011, 001001001001, 0001001100010011, and 0001001010001011, etc.

From their binary symbols we could make direct conclusions about the symmetry: every reversible word denotes polyominoes with a sense-reversing symmetry (they don't have "left" and "right" form); irreversible symbols correspond to the polyominos appearing in the "left" and "right" form (e.g., 0001001100010011 or 0001001010001011). 

We can translate these symbols (or binary numbers) into hexadecimal numbers and assign exactly one number like that to each polyomino. For example, this number could be the minimum of all cyclic-equivalent symbols (e.g. to the polyomino 00010001 correspond cyclically equivalent symbols 00100010, 01000100, 10001000 and the minimum of them is 00010001 = 11 in the hexadecimal system). Hence, we have a notation for polyominoes where exactly one number corresponds to every polyomino, and vice versa. (Open question: find the general algebraic form of the number determining a polyomino? Namely, some numbers will determine "open polyominoes", "hollow polyominoes" or "overlapping polyominoes", that are not included in our definition, and other will determine "real" polyominoes). 

Every (n+1)-omino can be derived from some n-omino by adding a single square to it. Certainly, the addition operation is a positional one, that is, the result depends on the position where the new square is added. Here are the following addition rules: 

  1. a0+0000 = a10001 (1-edge contact); 
  2. a0110+0000 = a1001 (2-edge contact); 
  3. a0110110+0000 = a1010 (3-edge contact), where a never ends with 1.

This "algebra" could be successfully used for the computer enumeration of polyominoes. In each step we need to derive (n+1)-minoes from n-minoes by adding a square, then test the equality of polyominoes obtained and finally make a complete list of the different (n+1)-minoes obtained. The main problem in such a derivation will be the occurrence of "undesired" edge contacts (e.g., in parallel edges, producing "hollow" and "overlapping" polyominoes).