Editing Polyomino (section)

===Algorithms for enumeration of fixed polyominoes===

====Inductive algorithms====
Each polyomino of size ''n''+1 can be obtained by adding a square to a polyomino of size ''n''. This leads to algorithms for generating polyominoes inductively.

Most simply, given a list of polyominoes of size ''n'', squares may be added next to each polyomino in each possible position, and the resulting polyomino of size ''n''+1 added to the list if not a duplicate of one already found; refinements in ordering the enumeration and marking adjacent squares that should not be considered reduce the number of cases that need to be checked for duplicates.<ref>Golomb, pp. 73–79</ref> This method may be used to enumerate either free or fixed polyominoes.

A more sophisticated method, described by Redelmeier, has been used by many authors as a way of not only counting polyominoes (without requiring that all polyominoes of size ''n'' be stored in size to enumerate those of size ''n''+1), but also proving upper bounds on their number. The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each ''n''-omino ''n'' times, once from starting from each of its ''n'' squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When ''n'' squares have been created, an ''n''-omino has been created.

This method ensures that each fixed polyomino is counted exactly ''n'' times, once for each starting square. It can be optimized so that it counts each polyomino only once, rather than ''n'' times. Starting with the initial square, declare it to be the lower-left square of the polyomino. Simply do not number any square that is on a lower row, or left of the square on the same row. This is the version described by Redelmeier.

If one wishes to count free polyominoes instead, then one may check for symmetries after creating each ''n''-omino. However, it is faster<ref>Redelmeier, section 4</ref> to generate symmetric polyominoes separately (by a variation of this method)<ref>Redelmeier, section 6</ref> and so determine the number of free polyominoes by [[Burnside's lemma]].

====Transfer-matrix method====
Currently, the most effective algorithms belong to the transfer-matrix paradigm. They may be called transfer matrix algorithms (TMAs) for short. Andrew Conway<ref>{{cite journal |last=Conway |first=Andrew | year=1995 | title=Enumerating 2D percolation series by the finite-lattice method: theory | journal=Journal of Physics A: Mathematical and General | volume=28 |issue=2 | pages=335–349 | zbl=0849.05003 | doi=10.1088/0305-4470/28/2/011|bibcode=1995JPhA...28..335C }}</ref> first implemented a TMA in the 90s, and calculated 25 terms of the fixed polyomino sequence ({{OEIS link|id=A001419}} in the OEIS). Iwan Jensen refined Conway's methods and implemented a TMA in parallel for the first time in a pair of papers in the early 2000s.<ref>{{cite journal |last=Jensen |first=Iwan | year=2001 | title=Enumerations of Lattice Animals and Trees | journal=Journal of Statistical Physics | volume=102 |issue=1 | pages=865–881 | doi=10.1023/A:1004855020556| arxiv=cond-mat/0007239 |bibcode=2001JSP...102..865J }}</ref><ref>{{cite conference |last=Jensen |first=Iwan | year=2003 | title=Counting Polyominoes: A Parallel Implementation for Cluster Computing | conference=International Conference on Computer Science (ICCS) | pages=203–212 | doi=10.1007/3-540-44863-2_21}}</ref> He calculated 56 terms. Because of this work, any TMA is sometimes also called Jensen's Algorithm. In 2024, Gill Barequet and his student Gil Ben-Shachar made another improvement by running a TMA on 45° rotation of the square grid, which is an equivalent problem but computationally easier.<ref>{{cite conference |last1=Barequet |first1=Gill | last2=Ben-Shachar |first2=Gil |year=2003 | title=Counting Polyominoes, Revisited | conference=Symposium on Algorithm Engineering and Experiments (SIAM) | pages=133–143 | doi=10.1137/1.9781611977929.1| arxiv=2310.20632 }}</ref> This approach holds the polyomino-counting record, with 70 terms. 

As a rule, TMAs are much faster than the previous methods, but still run in time that is exponential in ''n''. Roughly, this is achieved by fixing a width (in the diagonal case, a diagonal width), and counting polyominoes that fit in rectangles of that width. If this is done, it is only necessary to keep track of a polyomino's boundary, and since multiple polyominoes can correspond to a single boundary, this approach is faster than one generating every polyomino. Repeating this for every width gives every polyomino. 

Although it has excellent running time, the tradeoff is that this algorithm uses exponential amounts of memory (many [[gigabyte]]s of memory are needed for ''n'' above 50), is much harder to program than the other methods, and cannot currently be used to count free polyominoes.