Python implementation based on [1] to count the number of fixed polyominoes [2] for every possible number of tiles. According to [1], "a polyomino is a geometrical shape consisting of a number of square tiles, with each two of them sharing a side". If rotations and reflections are allowed, then the set of polyominoes is called free. Otherwise, it is called fixed. For instance, with 5 tiles we get the following [1] :
Since the algorithm implemented in this repository has exponential complexity, it is recommended for sizes up to 15. For higher number of tiles a faster algorithm such as the one found in [3] should be used. A great introductory source with examples is [1].
The code has been developed and tested on Python 3.9.4. Apart from the optional pprint module, which is used to "pretty print" a dictionary, only Python3 built-in modules have been used.
In the following table the number of different fixed polyominoes of size up to and including 46 according to [3], is presented:
Polyomino Size | Number of Fixed Polyominoes |
---|---|
1 | 1 |
2 | 2 |
3 | 6 |
4 | 19 |
5 | 63 |
6 | 216 |
7 | 760 |
8 | 2725 |
9 | 9910 |
10 | 36446 |
11 | 135268 |
12 | 505861 |
13 | 1903890 |
14 | 7204874 |
15 | 27394666 |
16 | 104592937 |
17 | 400795844 |
18 | 1540820542 |
19 | 5940738676 |
20 | 22964779660 |
21 | 88983512783 |
22 | 345532572678 |
23 | 1344372335524 |
24 | 5239988770268 |
25 | 20457802016011 |
26 | 79992676367108 |
27 | 313224032098244 |
28 | 1228088671826973 |
29 | 4820975409710116 |
30 | 18946775782611174 |
31 | 74541651404935148 |
32 | 293560133910477776 |
33 | 1157186142148293638 |
34 | 4565553929115769162 |
35 | 18027932215016128134 |
36 | 71242712815411950635 |
37 | 281746550485032531911 |
38 | 1115021869572604692100 |
39 | 4415695134978868448596 |
40 | 17498111172838312982542 |
41 | 69381900728932743048483 |
42 | 275265412856343074274146 |
43 | 1092687308874612006972082 |
44 | 4339784013643393384603906 |
45 | 17244800728846724289191074 |
46 | 68557762666345165410168738 |
[1] Github of the book: Louridas, Panos. Real-world Algorithms: A Beginner's Guide. MIT Press, 2017
[2] Redelmeier, D. Hugh. "Counting polyominoes: yet another attack." Discrete Mathematics 36.2 (1981): 191-203.
[3] Jensen, Iwan. "Enumerations of lattice animals and trees.", Journal of statistical physics 102.3 (2001): 865-881.