Polyomino Count [60A]

Contributed by Francis Glassborow

A polyomino is a shape made up of a number of squares that are joined along complete sides. For a fuller explanation try Mathworld's Polyomino page.

Once you understand what a polyomino is note that there are two classifications of what makes two polyominoes of the same size count as different. In the fixed form two polyominoes that can be rotated to match are consider equivalent. The free form allows turning over (effectively reflection) as well. Mathematically the free form set of polyominoes of any size are a subset (proper subset for all but dominoes and triominoes) of the set of fixed ones.

The project is to write a program that will count the number of distinct polyominoes of any given size. The user of the program should be prompted for the number of squares and whether they want a count of the fixed or free ones of that size.

Program elements

Probably the most important programming concept to solve this problem is the concept of a canonical form. In a computing or mathematical sense that means a single standard form which is used to represent all equivalent forms. For example, in high-school algebra 3x + 4, x3 + 4, 4 + 3x, x + x + x + 4 etc. are all equivalent expressions but only the first one is in canonical form. In order to count the number of distinct polyominoes of a specific size you will need to decide on some way to represent all members of an equivalence class.

Hints

Before you start a program design try some simple cases by cutting out shapes for tetrominoes (4 squares) and pentominoes (5 squares) and explore the difference between the fixed and free versions.

Extensions

Try counting the number of polyominoes that have holes in the middle. Th smallest of these is the heptomino formed by taking a three by three block and removing the centre square and one of the corner squares.

For something more demanding try the 3-dimensional analogue with cubes joined by complete faces. Note that there are still only one version of the two cube and two versions of the three cube, but after that the results diverge.