Redelmeier's algorithm

Redelmeier's algorithm enumerates fixed polyominoes, identifying translations while retaining different orientations. Put the leftmost cell of the bottom row at the origin. Allowed cells lie above the horizontal axis, or on it at nonnegative horizontal coordinates.

Maintain the occupied set of cells, an untried frontier of adjacent cells, and exclusions inherited from earlier branches. Remove a frontier cell $u$, occupy it, and add neighbours newly exposed by $u$. Recurse with a copy of the updated frontier. On returning, undo those new neighbours and remove $u$ from the occupied set, but keep $u$ excluded from later sibling branches.

The exclusion prevents a later branch from reconstructing a polyomino already assigned to the branch containing $u$. Requiring new cells to touch the occupied set preserves connectivity; every canonical polyomino has a branch determined by its first available frontier choice. Thus each fixed polyomino is visited once.

At size two there are two fixed polyominoes, horizontal and vertical, but one free polyomino after identifying rotations. Counting free polyominoes needs an additional treatment of symmetry.^[ref]