Polystrips are a subset of polyominoes conforming to the following rules:
- each piece consist of 1 or more cells
- no cell can have more than two neighbours
- the cells should not enclose a hole
Free polyominoes are distinct when none is a rigid transformation (translation, rotation, reflection or glide reflection) of another (pieces that can be picked up and flipped over). Translating, rotating, reflecting, or glide reflecting a free polyomino does not change its shape (Wikipedia)
For example, there are 30 free heptastrips (polystrips with length 7). Here are all of them, packed into a 14x15 grid.
Write a program / function that takes a positive integer
n as input and enumerates the distinct free
n=1 --> 1 (A single square)
n=2 --> 1 (There is only one possible 2-polystrip made of 2 squares)
n=3 --> 2 (One is composed of 3 squares joined in a line and the other one is L-shaped)
n=4 --> 3 (One straight, one L-shaped and one Z-shaped)
. . .
n polystrips 1 1 2 1 3 2 4 3 5 7 6 13 7 30 8 64 9 150 10 338 11 794 12 1836 13 4313 14 10067 15 23621
This is code-golf, so the shorter code is better. I would highly appreciate detailed explanations of the algorithm and the code.
Partial reference implementation in J
I decided to describe each piece in "vector" format and I only need n-2 blocks to describe an n-polystrip piece (there is only 1 2-polystrip and it's returned explicitly). The blocks describe the relative direction: 0 - no change; 1 - turn left; 2 - turn right. It doesn't matter which direction one will start but only to indicate where the next cell is to be put. There can be any number of consecutive 0s, but 1s and 2s are always single. This implementation is partial, because it doesn't account for the holes - solutions for n>6 count the pieces with holes too.