Introduction

Counting polyominoes is a classic contest problem because the statement is short but the search space explodes quickly. A good solution depends on two ideas: generate shapes incrementally, and canonicalize them so that equivalent rotations and reflections are counted only once when the problem asks for free polyominoes.

Know What You Are Counting

A polyomino is a connected set of unit squares joined edge to edge. Contest problems usually ask for one of two variants:

• fixed polyominoes: rotations and reflections count as different
• free polyominoes: rotations and reflections count as the same

That distinction completely changes duplicate handling. A brute-force search over board placements is usually the wrong starting point, because the board itself is not the object being counted. The object is the connected shape.

Generate by Expanding the Boundary

The standard recursive idea is simple:

1. start with one cell
2. keep a frontier of empty cells adjacent to the current shape
3. add one frontier cell at a time
4. normalize the result so duplicates collapse to one canonical form

For small n, this approach is practical and easy to reason about. For larger n, contest setters usually expect a more specialized method such as Redelmeier’s algorithm, but canonical generation is still the best place to build intuition.

A Runnable Python Approach

The following program counts free polyominoes of size n by generating shapes recursively and normalizing across all 8 symmetries of the square.

1def transforms(cells):
2    pts = list(cells)
3    for _ in range(4):
4        pts = [(c, -r) for r, c in pts]
5        yield pts
6        yield [(-r, c) for r, c in pts]
7
8
9def normalize(cells):
10    variants = []
11    for variant in transforms(cells):
12        min_r = min(r for r, _ in variant)
13        min_c = min(c for _, c in variant)
14        shifted = sorted((r - min_r, c - min_c) for r, c in variant)
15        variants.append(tuple(shifted))
16    return min(variants)
17
18
19def count_polyominoes(n):
20    seen = set()
21
22    def dfs(shape):
23        key = normalize(shape)
24        if key in seen:
25            return
26        seen.add(key)
27
28        if len(shape) == n:
29            return
30
31        frontier = set()
32        for r, c in shape:
33            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
34                nxt = (r + dr, c + dc)
35                if nxt not in shape:
36                    frontier.add(nxt)
37
38        for cell in frontier:
39            dfs(shape | {cell})
40
41    dfs({(0, 0)})
42    return sum(1 for shape in seen if len(shape) == n)
43
44
45for n in range(1, 6):
46    print(n, count_polyominoes(n))

This is not the fastest possible algorithm, but it is correct for small sizes and illustrates the central contest technique: represent shapes structurally instead of placing them on a huge grid.

Why Canonicalization Is the Hard Part

Without normalization, the same shape is generated many times from different growth orders. For free polyominoes, you also need to collapse rotations and reflections.

That is why normalize is the key function. It does three things:

• applies every symmetry
• shifts each version so its top-left cell is at the origin
• chooses the lexicographically smallest representation

Once every shape maps to the same canonical signature, a hash set can remove duplicates efficiently.

Contest-Level Optimization Ideas

If constraints go beyond small n, the baseline recursive solution may time out. Common upgrades include:

• Redelmeier’s algorithm to avoid generating duplicates in the first place
• memoization on normalized boundary states
• pruning using bounding boxes or symmetry rules
• counting fixed polyominoes first, then reducing by symmetry only if the problem allows it

Another important optimization is to avoid rebuilding large temporary structures unnecessarily. In Python especially, recursion overhead and repeated sorting can dominate runtime long before the mathematical search space becomes the only problem.

How to Read the Output

For free polyominoes, the first few counts are well known:

• size 1: 1
• size 2: 1
• size 3: 2
• size 4: 5
• size 5: 12

Those values make excellent sanity checks. If your program does not match them, the bug is usually in connectivity handling or symmetry normalization.

Common Pitfalls

• Mixing up fixed and free polyominoes. That changes the answer immediately.
• Generating cells on a board and forgetting that translation should not matter.
• Removing duplicates by sorting cell lists without accounting for rotations and reflections.
• Forgetting to ensure connectivity after each expansion.
• Using an elegant brute-force approach on input sizes that require a contest-grade enumeration algorithm.

Summary

• Polyomino counting is fundamentally a connected-shape enumeration problem.
• The first question is whether rotations and reflections count as the same shape.
• A practical baseline solution grows shapes one cell at a time from the frontier.
• Canonical normalization is what makes duplicate removal work.
• For larger constraints, move from naive generation toward Redelmeier-style enumeration and stronger pruning.