Polyomino: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
m added see also
added RLE:Pentominoes
 
(94 intermediate revisions by 32 users not shown)
Line 1: Line 1:
{{Glossary}}
{{Glossary}}
A '''polyomino''' (or simply '''omino''') is a finite collection of orthogonally connected [[cell]]s. The mathematical study of polyominoes was initiated by Solomon Golomb in 1953. Conway's early investigations of [[Conway's Game of Life|Life]] and other [[cellular automaton|cellular automata]] involved tracking the histories of small polyominoes, this being a reasonable way to ascertain the typical behaviour of different cellular automata when the patterns had to be evolved by hand rather than by computer. Polyominoes have no special significance in Life, but their extensive study during the early years lead to a number of important discoveries and has influenced the terminology of Life.
A '''polyomino''' (or simply '''omino''') is a finite collection of orthogonally connected [[cell]]s. The mathematical study of polyominoes was initiated by Solomon W. Golomb in 1953.<ref>Golomb, Solomon W. (1994). ''Polyominoes'' (2nd ed.). Princeton, New Jersey: Princeton University Press. ISBN 978-0-691-02444-8.</ref> Conway's early investigations of [[Conway's Game of Life|Life]] and other [[cellular automaton|cellular automata]] involved tracking the histories of small polyominoes, this being a reasonable way to ascertain the typical behaviour of different cellular automata when the patterns had to be evolved by hand rather than by computer. Polyominoes have no special significance in Life, but their extensive study during the early years lead to a number of important discoveries and has influenced the terminology of Life.


[[Image:Cross_small.png|framed|right|A cross.]]It is possible for a polyomino to be an [[oscillator]]. In fact, there are infinitely many examples of such polyominoes, including the [[cross]] and its larger analogues. The only other known examples are the [[block]] (which has [[period]] 1), the [[blinker]], the [[toad]], the [[star]] and (in two different phases) the [[pentadecathlon]].
[[File:Cross.png|thumb|right|A cross]]During the course of its evolution a polyomino could regain its original form, thereby constituting one phase of an [[oscillator]], as seen in the (infinite) [[cross]] family. The only other known examples are the [[block]] (which has [[period]] 1), the [[blinker]], the [[toad]], the [[star]] (and its hybrid with cross that gives another [[extensible]] family of period-3 oscillators<ref name="post155104" />) and (in two different phases) the [[pentadecathlon]]. Were a recurring polyomino displaced, it would be participating in a spaceship, though the only known examples are the [[lightweight spaceship]], the [[middleweight spaceship]], and the [[heavyweight spaceship]]. Of course, its evolution could follow other trajectories, possibly very long lived.


A polyomino can also be a spaceship, though the only known examples are the [[lightweight spaceship]], the [[middleweight spaceship]], and the [[heavyweight spaceship]].
== Sizes of polyominoes ==
Polyominoes of with n cells for n = 1, 2, 3, 4, ... are called haplominoes, dominoes, triominoes, tetrominoes, pentominoes, hexominoes, heptominoes, octominoes, and n-ominoes in general. The number of distinct polyominoes with n cells for n = 1, 2, 3, ... is given by the sequence 1, 1, 2, 5, 12, 35, 108, 369, 1285, ... (<tt>{{OEIS|A000105|tt=tt}}</tt> on the OEIS).


==Sizes of polyominoes==
=== Haplominoes ===
Polyominoes of with n cells for n = 2, 3, 4, ... are called dominoes, triominoes, tetrominoes, pentominoes, hexominoes, heptominoes, octominoes, and n-ominoes in general. The number of distinct polyominoes with n cells for n = 1, 2, 3, ... is given by the sequence 1, 1, 2, 5, 12, 35, 108, 369, 1285, ... (Sloane's [http://www.research.att.com/~njas/sequences/A000105 A000105]).
There is only [[dot|one]] '''haplomino''' (also called '''monomino''' or '''dot''') and by itself it dies after one [[generation]]. Several objects, such as the [[middleweight spaceship]], produce dot [[spark]]s.


===Dominoes===
It can be stabilised into [[lone dot agar]] and the [[barberpole]] family, the [[rotor]]s of which are [[phoenician]].
There is only one '''domino''' and by itself it dies after one [[generation]]. A number of objects, such as the heavyweight spaceship and the pentadecathlon, produce domino [[spark]]s.


===Triominoes===
=== Dominoes ===
There is also only [[domino|one]] '''domino''' and by itself it too dies after one generation. A number of objects, such as the [[heavyweight spaceship]] and the [[pentadecathlon]], produce domino sparks.
 
Based upon that instant dying property of the domino, [[Squaredance]] is a low density domino-based [[agar]] and [[phoenix]].
 
=== Triominoes ===
There are exactly two distinct '''triominoes'''. The term is rarely used in Life, because the two objects in question are simply the [[blinker]] and the [[pre-block]].
There are exactly two distinct '''triominoes'''. The term is rarely used in Life, because the two objects in question are simply the [[blinker]] and the [[pre-block]].


===Tetrominoes===
=== Tetrominoes ===
There are five distinct '''tetrominoes''', each of which is shown below. The first is the [[block]], the second is the [[T-tetromino]], and the remaining three rapidly evolve into [[beehive]]s.
There are five distinct '''tetrominoes''', each of which is shown below. The first is the [[block]], the second is the [[T-tetromino]] (a [[traffic light]] [[predecessor]]), and the remaining three rapidly evolve into [[beehive]]s. The fourth is commonly referred to as a [[tail]] and is often attached to small [[still life]]s, for example combining with [[tub]] to form [[tub with tail]].
 
<center>
{{EmbedViewer
|pname        = tetrominoes
|position    = center
|viewerconfig = #C [[ THUMBSIZE 2 ]]
|caption      = The five distinct tetrominoes, from left to right: {{nowrap|O, T, I, J, Z}}
|style        = width:360px;
}}
</center>


[[Image:Tetrominoes.png|framed|center|The five distinct tetrominoes.<br />'''Manipulate via Java:''' [http://www.conwaylife.com/?p=tetrominoes click here]<br />'''Download [[RLE]]:''' [http://www.conwaylife.com/pattern.asp?p=tetrominoes.rle click here] ]]
=== Pentominoes ===
There are 12 distinct '''pentominoes'''. [[John Conway]] assigned them all letters in the range O to Z, loosely based on their shapes, and they are all shown below in order.
Unlike triominoes and tetrominoes, it has been proven that none of the pentominoes can work as [[induction coil]]s.


===Pentominoes===
{| style="margin-left: auto; margin-right: auto"
There are 12 distinct '''pentominoes'''. [[:Category:Patterns found by John Conway|John Conway]] assigned them all letters in the range O to Z, loosely based on their shapes, and they are all shown below in order.
| [[File:Opentomino small.png|thumb|center|O]]
* The O-pentomino is a [[traffic light]] [[predecessor]], though not one of the more common ones.
| [[File:Ppentomino small.png|thumb|center|P]]
* The P-pentomino is a common [[spark]] that dies in [[generation]] 4.
| [[File:Qpentomino small.png|thumb|center|Q]]
* The Q-pentomino is a traffic light predecessor.
| [[File:Rpentomino small.png|thumb|center|R]]
* The [[R-pentomino]] is a [[methuselah]] and by far the most well-known pentomino.  
| [[File:Spentomino small.png|thumb|center|S]]
| [[File:Tpentomino small.png|thumb|center|T]]
|-
| [[File:Upentomino small.png|thumb|center|U]]
| [[File:Vpentomino small.png|thumb|center|V]]
| [[File:Wpentomino small.png|thumb|center|W]]
| [[File:Xpentomino small.png|thumb|center|X]]
| [[File:Ypentomino small.png|thumb|center|Y]]
| [[File:Zpentomino small.png|thumb|center|Z]]
|}
 
<center>
{{EmbedViewer
|pname        = pentominoes
|position    = center
|viewerconfig = #C [[ THUMBSIZE 2 WIDTH 1200 HEIGHT 700 ]]
|caption      = The 12 distinct pentominoes
|style        = width:360px;
}}
</center>
 
* The O-pentomino is a [[traffic light]] [[predecessor]]. Its most common grandparent is 3o$3o$bo$2bo$2bo!.
* The P-pentomino or [[crotchet]] dies in [[generation]] 4.
* The Q-pentomino (also known as "long leg") is a traffic light predecessor.
* The [[R-pentomino]] is a [[methuselah]] and by far the most well-known pentomino.
* The S-pentomino dies in generation 5.
* The S-pentomino dies in generation 5.
* The T-pentomino is a common [[parent]] of the [[T-tetromino]].
* The T-pentomino is a common [[parent]] of the [[T-tetromino]].
* The U-pentomino dies in generation 4.
* The U-pentomino or [[short table]] dies in generation 4.
* The V-pentomino evolves into a [[loaf]] in generation 3.
* The V-pentomino evolves into a [[loaf]] in generation 3.
* The W-pentomino is a common loaf predecessor.
* The W-pentomino is a common loaf grandparent.
* The X-pentomino is a traffic light predecessor.
* The X-pentomino is a traffic light predecessor.
* The Y-pentomino dies in generation 3.
* The Y-pentomino dies in generation 3, creating [[obo spark]]s along the way.
* The Z-pentomino dies in generation 3.
* The Z-pentomino dies in generation 3.


{|
=== Hexominoes ===
|-
There are 35 distinct '''hexominoes''', the majority of which behave uninterestingly. The most interesting and well-known examples are [[century]], [[line-of-six spark]], [[stairstep hexomino]], [[table]], [[toad]], [[Pre-beehive]] and [[Z-hexomino]].
|[[Image:Opentomino_small.png|framed|center|O]]
 
|[[Image:Ppentomino_small.png|framed|center|P]]
<center>
|[[Image:Qpentomino_small.png|framed|center|Q]]
{{EmbedViewer
|[[Image:Rpentomino_small.png|framed|center|R]]
|pname        = hexominoes
|[[Image:Spentomino_small.png|framed|center|S]]
|position    = center
|[[Image:Tpentomino_small.png|framed|center|T]]
|viewerconfig = #C [[ THUMBSIZE 2 WIDTH 1200 HEIGHT 700 ZOOM 12 ]]
|-
|caption      = The 35 distinct hexominoes
|[[Image:Upentomino_small.png|framed|center|U]]
|style        = width:360px;
|[[Image:Vpentomino_small.png|framed|center|V]]
}}
|[[Image:Wpentomino_small.png|framed|center|W]]
</center>
|[[Image:Xpentomino_small.png|framed|center|X]]
 
|[[Image:Ypentomino_small.png|framed|center|Y]]
* The 1st hexomino is the [[line-of-six spark]], which dies in generation 12.
|[[Image:Zpentomino_small.png|framed|center|Z]]
* The 2nd hexomino (also known as "long long leg") stabilizes into two blinkers at generation 40.<ref group="note">Four copies of this hexomino arranged in a certain way can make a [[Kok%27s galaxy]] [[predecessor]].</ref><ref name="xp2_111zy2s"/>
|}
* The 3rd hexomino evolves into a [[block]] in generation 4.
* The 4th hexomino evolves into a [[traffic light]] in generation 9.
* The 5th hexomino dies in generation 4.
* The 6th hexomino evolves into a block in generation 4.
* The 7th hexomino is a [[grandparent]] of the [[boat]].
* The 8th hexomino evolves into a block in generation 4.
* The 9th hexomino is the [[table]], which becomes the line-of-six spark in 3 generations and therefore dies in generation 15.
* The 10th hexomino is the [[Z-hexomino]], which dies in generation 45.
* The 11th hexomino dies in generation 5.
* The 12th hexomino dies in generation 7 via the P-pentomino.
* The 13th hexomino converges to the same evolutionary sequence as the [[pi-heptomino]] and stabilizes at generation 176, leaving behind 6 blocks, 5 blinkers, and two [[pond]]s.
* The 14th hexomino dies in generation 5 via the P-pentomino.
* The 15th hexomino evolves into a block in generation 3.
* The 16th hexomino is a parent of the [[aircraft carrier]].
* The 17th hexomino dies in generation 5.
* The 18th hexomino is a parent of the [[stairstep hexomino]].
* The 19th hexomino converges to the same evolutionary sequence as the stairstep hexomino.
* The 20th hexomino also converges to the same evolutionary sequence as the stairstep hexomino.
* The 21st hexomino is the period-2 oscillator [[toad]].
* The 22nd hexomino evolves into a boat in generation 4.
* The 23rd hexomino dies in generation 6.
* The 24th hexomino is the century and stabilizes at generation 103, leaving behind 3 blocks and a blinker.
* The 25th hexomino is the [[ghost Herschel]] and dies in generation 6.
* The 26th hexomino is generation 1 of the R-pentomino and stabilizes at generation 1,102, leaving behind 8 blocks, 4 blinkers, 4 beehives, two boats, a ship, and a loaf and having created six escaping gliders.
* The 27th hexomino is a parent of the loaf.
* The 28th hexomino dies in generation 4.
* The 29th hexomino is a [[pre-beehive|parent of the beehive]].
* The 30th hexomino dies in generation 4.
* The 31st hexomino is a great grandparent of the pond.
* The 32nd hexomino dies in generation 3.
* The 33rd hexomino dies in generation 9.
* The 34th hexomino is a parent of the [[pi-heptomino]].
* The 35th hexomino is the stairstep hexomino and lasts 63 generations, leaving a [[blockade]].
 
=== Heptominoes ===
There are 108 distinct '''heptominoes'''. Those with names in common use are the [[B-heptomino]], the [[bullet heptomino]], the [[C-heptomino]], the [[crinkly heptomino]], the [[E-heptomino]], the [[F-heptomino]],the [[H-heptomino]], the [[I-heptomino]], the "[[long]] long long [[leg]]", the [[Herschel]], and the [[pi-heptomino]].
 
Of the 108 heptominoes:
* 26 die completely. <!-- This contradicts both Lifeline and ColorfulGalaxy's census -->
* 16 become [[beehive]]s.
* 10 become [[block]]s.
* 10 become [[honey farm]]s.
* 6 become [[loaf|loaves]].
* 6 follow the [[pi-heptomino]] sequence.
* 5 become [[traffic light]]s.
* 4 become [[lumps of muck]].
* 3 become [[blinker]]s.
* 3 follow the [[butterfly]] sequence.
* 3 become [[glider]]s.
* 1 becomes a [[boat]].
* 1 follows the [[century]] sequence.
* 1 becomes a [[pulsar]].
* 1 becomes an [[R-pentomino]].
* 2 become two blocks: one with spacing [[Half-blockade|(4,1)]] and another with offset (5,0).
* 1 becomes two blinkers.
* 1 becomes two loaves.
* 1 becomes 2 traffic lights plus 2 blocks.
 
The remaining 7 have their own names due to being common methuselah sequences: the B, C, E, F, H, and I heptominoes and the Herschel.
 
All 108 heptominoes were either analyzed in 1970 or classified as "unknown so far" in [[Lifeline Volume 1]].
 
=== Octominoes ===
There are 369 distinct '''octominoes'''. Despite the abundance of octominoes, [[two-glider octomino|the following fairly common octomino]] (which evolves into a different octomino after two generations), which stabilizes after 386 generations into two [[traffic light]]s and four [[beehive]]s, is often referred to as simply ''the'' octomino:
[[File:Octomino.png|thumb|center|The octomino and its two-generation successor.]]
This leaves a [[toad]] at gen 21, but it does not survive after gen 153.
 
== Switch engine ==
[[Charles Corderman]] discovered the [[switch engine]] by running an exhaustive computer search on all decominoes and lower polyominoes. The machine that discovered the nonomino seed was unique, possessing an unusual architecture.
 
== Larger polyominoes ==
In April {{year|2023}}, yushimitsu announced completion of a Catagolue census of all polyominoes with {{nowrap|population &le; 18}}.<ref name="post160531" /> Some of the results are 18-ominoes that produce a [[jam]], a [[mazing]], and a [[cis-queen bee shuttle]]; 17-omino predecessors for [[mold]] and [[blocker]]; a 14-omino that produces a [[block-laying switch engine]] and a 16-omino that produces a [[glider-producing switch engine]]; several [[Methuselah|long-lasting patterns]].
 
=== Enumeration ===
<tt>{{OEIS|A000105|tt=tt}}</tt> contains counts of polyominoes up to 50 cells. It has been shown that there exists a constant <tt>{{lim|n->∞|{{sqrt|a(n)|n}}}} = {{lim|n->∞|{{frac|a(n)|a(n-1)}}}} = λ</tt>, where <tt>4.00253<ref>Gill Barequet, Günter Rote, Mira Shalah (November 12, 2015). [https://link.springer.com/chapter/10.1007/978-3-662-48350-3_8 ''λ > 4''].</ref> < λ &le; 4.5252<ref>Gill Barequet, Mira Shalah (June 28, 2019). [https://arxiv.org/abs/1906.11447 ''Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes''].</ref></tt> is Klarner's constant. Additionally, it appears the sequence <tt>{{frac|a(n)|a(n-1)}}</tt> is strictly increasing (converging to <tt>λ</tt>) with strictly decreasing first differences for all <tt>n > 13</tt>.
 
== Nomenclature ==
The name is a back-formation from 'domino', which explicitly refers to a pair of orthogonally connected live cells. According to the Life Lexicon, the pluralised name can be spelt two different ways: 'polyominos' and 'polyominoes' are both acceptable; the Life Lexicon follows Golomb in using the longer form. The same applies to the systematic names of each of the polyomino sizes.


===Hexominoes===
== See also ==
There are 35 distinct '''hexominoes''', the majority of which behave in uninteresting ways. The most interesting and well-known examples are [[century]], [[stairstep hexomino]], [[table]], [[toad]] and [[Z-hexomino]].
* [[Polyplet]]
* {{CategoryLink|Polyominoes}}


===Heptominoes===
== Notes ==
There are 108 distinct '''heptominoes'''. Those with names in common use are the [[B-heptomino]], the [[bullet heptomino]], the [[C-heptomino]], the [[Herschel]] and the [[pi-heptomino]].
<references group="note"/>


===Octominoes===
== References ==
There are 369 distinct '''octominoes'''. Despite the abundance of octominoes, the following fairly common octomino (or its two-generation successor) is often referred to as simply ''the'' octomino:
<references>
[[Image:Octomino.png|framed|center|The octomino and its two-generation successor.]]
<ref name="xp2_111zy2s">[[Ash]] on {{LinkCatagolue|xp2_111zy2s|style=brief}}</ref>
<ref name="post155104">{{LinkForumThread
|format = ref
|p      = 155104
|title  = Re: Oscillator Discussion Thread
|author = Matthias Merzenich
|date  = December 22, 2022
}}</ref>
<ref name="post160531">{{LinkForumThread
|format = ref
|p      = 160531
|title  = Re: Thread for your unsure discoveries
|author = yushimitsu
|date  = April 16, 2023
}}</ref>
</references>


==See also==
== External links ==
*[[Polyplet]]
* {{LinkLexicon|lex_p.htm#polyomino}}
* {{LinkForumThread|f=12|t=3978|title=Polyominoes beyond CA}}
* {{LinkForumThread|f=12|t=3036|title=Polyomino tilings}}
* {{LinkForumThread|f=2|t=5888|title=UC-based polyomino oscillators and spaceships}}
* {{cite web|url=https://press.princeton.edu/books/paperback/9780691024448/polyominoes|title=Polyominoes: Puzzles, Patterns, Problems, and Packings|publisher=Princeton University Press|author=Solomon W. Golomb}} Revised and expanded second edition.


==External links==
[[Category:Polyominoes| ]]
*[http://www.argentum.freeserve.co.uk/lex_p.htm#polyomino Polyomino] at the Life Lexicon
[[Category:Mathematical miscellany]]

Latest revision as of 10:48, 19 September 2026

A polyomino (or simply omino) is a finite collection of orthogonally connected cells. The mathematical study of polyominoes was initiated by Solomon W. Golomb in 1953.[1] Conway's early investigations of Life and other cellular automata involved tracking the histories of small polyominoes, this being a reasonable way to ascertain the typical behaviour of different cellular automata when the patterns had to be evolved by hand rather than by computer. Polyominoes have no special significance in Life, but their extensive study during the early years lead to a number of important discoveries and has influenced the terminology of Life.

A cross

During the course of its evolution a polyomino could regain its original form, thereby constituting one phase of an oscillator, as seen in the (infinite) cross family. The only other known examples are the block (which has period 1), the blinker, the toad, the star (and its hybrid with cross that gives another extensible family of period-3 oscillators[2]) and (in two different phases) the pentadecathlon. Were a recurring polyomino displaced, it would be participating in a spaceship, though the only known examples are the lightweight spaceship, the middleweight spaceship, and the heavyweight spaceship. Of course, its evolution could follow other trajectories, possibly very long lived.

Sizes of polyominoes

Polyominoes of with n cells for n = 1, 2, 3, 4, ... are called haplominoes, dominoes, triominoes, tetrominoes, pentominoes, hexominoes, heptominoes, octominoes, and n-ominoes in general. The number of distinct polyominoes with n cells for n = 1, 2, 3, ... is given by the sequence 1, 1, 2, 5, 12, 35, 108, 369, 1285, ... (A000105 on the OEIS).

Haplominoes

There is only one haplomino (also called monomino or dot) and by itself it dies after one generation. Several objects, such as the middleweight spaceship, produce dot sparks.

It can be stabilised into lone dot agar and the barberpole family, the rotors of which are phoenician.

Dominoes

There is also only one domino and by itself it too dies after one generation. A number of objects, such as the heavyweight spaceship and the pentadecathlon, produce domino sparks.

Based upon that instant dying property of the domino, Squaredance is a low density domino-based agar and phoenix.

Triominoes

There are exactly two distinct triominoes. The term is rarely used in Life, because the two objects in question are simply the blinker and the pre-block.

Tetrominoes

There are five distinct tetrominoes, each of which is shown below. The first is the block, the second is the T-tetromino (a traffic light predecessor), and the remaining three rapidly evolve into beehives. The fourth is commonly referred to as a tail and is often attached to small still lifes, for example combining with tub to form tub with tail.

x = 39, y = 2, rule = B3/S23 2o6b3o6b4o6b3o6b2ob$2o7bo19bo7b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ]]
The five distinct tetrominoes, from left to right: O, T, I, J, Z
(click above to open LifeViewer)
RLE: here Plaintext: here

Pentominoes

There are 12 distinct pentominoes. John Conway assigned them all letters in the range O to Z, loosely based on their shapes, and they are all shown below in order. Unlike triominoes and tetrominoes, it has been proven that none of the pentominoes can work as induction coils.

O
P
Q
R
S
T
U
V
W
X
Y
Z
x = 71, y = 40, rule = B3/S23 2o8b5o6bo$2o19bo$o20b3o7$21bo$3o7b4o7b2o$2b2o9bo8b2o8$69b2o$obo8b3o54b 2o$3o9bo56bo$12bo7$2bo9bo$4o7b3o$12bo6$2o$bo$b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 WIDTH 1200 HEIGHT 700 ]]
The 12 distinct pentominoes
(click above to open LifeViewer)
RLE: here Plaintext: here
  • The O-pentomino is a traffic light predecessor. Its most common grandparent is 3o$3o$bo$2bo$2bo!.
  • The P-pentomino or crotchet dies in generation 4.
  • The Q-pentomino (also known as "long leg") is a traffic light predecessor.
  • The R-pentomino is a methuselah and by far the most well-known pentomino.
  • The S-pentomino dies in generation 5.
  • The T-pentomino is a common parent of the T-tetromino.
  • The U-pentomino or short table dies in generation 4.
  • The V-pentomino evolves into a loaf in generation 3.
  • The W-pentomino is a common loaf grandparent.
  • The X-pentomino is a traffic light predecessor.
  • The Y-pentomino dies in generation 3, creating obo sparks along the way.
  • The Z-pentomino dies in generation 3.

Hexominoes

There are 35 distinct hexominoes, the majority of which behave uninterestingly. The most interesting and well-known examples are century, line-of-six spark, stairstep hexomino, table, toad, Pre-beehive and Z-hexomino.

x = 82, y = 43, rule = B3/S23 6o7b5o8b5o8b5o8b4o9b4o9b4o$17bo11bo11bo13b2o11bo11b2o$68bo8$4o9b4o9bo 13bo13bo13bo9b4o$bobo9bo2bo9b4o9b4o9b4o9b4o11bo$29bo12bo12bo12bo11bo8$ 4o10bo13bo10b3o10b3o10b3o10b3o$b2o10b4o9b4o11b3o10b2o11b2o10b3o$15bo 12bo26bo11bo8$3o10bo13bo11b3o10b3o10b3o10b3o$ob2o9b3o10b3o12bo12bo11b 2o11b2o$15b2o11b2o11b2o10b2o12bo11bo8$3o10bo13bo11b2o11bo13bo11b2o$3o 10b3o10b3o11b3o9b3o10b3o11b2o$14b2o11b2o11bo11bobo10bobo12b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 WIDTH 1200 HEIGHT 700 ZOOM 12 ]]
The 35 distinct hexominoes
(click above to open LifeViewer)
RLE: here Plaintext: here
  • The 1st hexomino is the line-of-six spark, which dies in generation 12.
  • The 2nd hexomino (also known as "long long leg") stabilizes into two blinkers at generation 40.[note 1][3]
  • The 3rd hexomino evolves into a block in generation 4.
  • The 4th hexomino evolves into a traffic light in generation 9.
  • The 5th hexomino dies in generation 4.
  • The 6th hexomino evolves into a block in generation 4.
  • The 7th hexomino is a grandparent of the boat.
  • The 8th hexomino evolves into a block in generation 4.
  • The 9th hexomino is the table, which becomes the line-of-six spark in 3 generations and therefore dies in generation 15.
  • The 10th hexomino is the Z-hexomino, which dies in generation 45.
  • The 11th hexomino dies in generation 5.
  • The 12th hexomino dies in generation 7 via the P-pentomino.
  • The 13th hexomino converges to the same evolutionary sequence as the pi-heptomino and stabilizes at generation 176, leaving behind 6 blocks, 5 blinkers, and two ponds.
  • The 14th hexomino dies in generation 5 via the P-pentomino.
  • The 15th hexomino evolves into a block in generation 3.
  • The 16th hexomino is a parent of the aircraft carrier.
  • The 17th hexomino dies in generation 5.
  • The 18th hexomino is a parent of the stairstep hexomino.
  • The 19th hexomino converges to the same evolutionary sequence as the stairstep hexomino.
  • The 20th hexomino also converges to the same evolutionary sequence as the stairstep hexomino.
  • The 21st hexomino is the period-2 oscillator toad.
  • The 22nd hexomino evolves into a boat in generation 4.
  • The 23rd hexomino dies in generation 6.
  • The 24th hexomino is the century and stabilizes at generation 103, leaving behind 3 blocks and a blinker.
  • The 25th hexomino is the ghost Herschel and dies in generation 6.
  • The 26th hexomino is generation 1 of the R-pentomino and stabilizes at generation 1,102, leaving behind 8 blocks, 4 blinkers, 4 beehives, two boats, a ship, and a loaf and having created six escaping gliders.
  • The 27th hexomino is a parent of the loaf.
  • The 28th hexomino dies in generation 4.
  • The 29th hexomino is a parent of the beehive.
  • The 30th hexomino dies in generation 4.
  • The 31st hexomino is a great grandparent of the pond.
  • The 32nd hexomino dies in generation 3.
  • The 33rd hexomino dies in generation 9.
  • The 34th hexomino is a parent of the pi-heptomino.
  • The 35th hexomino is the stairstep hexomino and lasts 63 generations, leaving a blockade.

Heptominoes

There are 108 distinct heptominoes. Those with names in common use are the B-heptomino, the bullet heptomino, the C-heptomino, the crinkly heptomino, the E-heptomino, the F-heptomino,the H-heptomino, the I-heptomino, the "long long long leg", the Herschel, and the pi-heptomino.

Of the 108 heptominoes:

The remaining 7 have their own names due to being common methuselah sequences: the B, C, E, F, H, and I heptominoes and the Herschel.

All 108 heptominoes were either analyzed in 1970 or classified as "unknown so far" in Lifeline Volume 1.

Octominoes

There are 369 distinct octominoes. Despite the abundance of octominoes, the following fairly common octomino (which evolves into a different octomino after two generations), which stabilizes after 386 generations into two traffic lights and four beehives, is often referred to as simply the octomino:

The octomino and its two-generation successor.

This leaves a toad at gen 21, but it does not survive after gen 153.

Switch engine

Charles Corderman discovered the switch engine by running an exhaustive computer search on all decominoes and lower polyominoes. The machine that discovered the nonomino seed was unique, possessing an unusual architecture.

Larger polyominoes

In April 2023, yushimitsu announced completion of a Catagolue census of all polyominoes with population ≤ 18.[4] Some of the results are 18-ominoes that produce a jam, a mazing, and a cis-queen bee shuttle; 17-omino predecessors for mold and blocker; a 14-omino that produces a block-laying switch engine and a 16-omino that produces a glider-producing switch engine; several long-lasting patterns.

Enumeration

A000105 contains counts of polyominoes up to 50 cells. It has been shown that there exists a constant limn->∞(n√a(n)) = limn->∞(a(n)a(n-1)) = λ, where 4.00253[5] < λ ≤ 4.5252[6] is Klarner's constant. Additionally, it appears the sequence a(n)a(n-1) is strictly increasing (converging to λ) with strictly decreasing first differences for all n > 13.

Nomenclature

The name is a back-formation from 'domino', which explicitly refers to a pair of orthogonally connected live cells. According to the Life Lexicon, the pluralised name can be spelt two different ways: 'polyominos' and 'polyominoes' are both acceptable; the Life Lexicon follows Golomb in using the longer form. The same applies to the systematic names of each of the polyomino sizes.

See also

Notes

  1. ↑ Four copies of this hexomino arranged in a certain way can make a Kok's galaxy predecessor.

References

  1. ↑ Golomb, Solomon W. (1994). Polyominoes (2nd ed.). Princeton, New Jersey: Princeton University Press. ISBN 978-0-691-02444-8.
  2. ↑ Matthias Merzenich (December 22, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  3. ↑ Ash on Catagolue: here
  4. ↑ yushimitsu (April 16, 2023). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
  5. ↑ Gill Barequet, Günter Rote, Mira Shalah (November 12, 2015). λ > 4.
  6. ↑ Gill Barequet, Mira Shalah (June 28, 2019). Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes.