Polyomino- Polyomino

"Polyominoes" leitet hier weiter. Das Buch von Solomon Golomb finden Sie unter Polyominoes: Puzzles, Patterns, Problems, and Packings .
Die 18 einseitigen Pentominos , darunter 6 gespiegelte Paare
Die 35 freien Hexominos , gefärbt nach ihrer Symmetrie.
Der einzelne freie Dominostein .

Ein Polyomino ist eine ebene geometrische Figur, die gebildet wird, indem ein oder mehrere gleiche Quadrate Kante an Kante verbunden werden. Es ist eine Polyform, deren Zellen Quadrate sind. Sie kann als endliche Teilmenge der regelmäßigen quadratischen Kachelung betrachtet werden .

Polyominos werden seit mindestens 1907 in beliebten Rätseln verwendet , und die Aufzählung von Pentominos wird bis in die Antike datiert. Viele Ergebnisse mit den Figuren von 1 bis 6 Quadraten wurden erstmals in den Jahren 1937 bis 1957 in Fairy Chess Review unter dem Namen " Dissektionsprobleme " veröffentlicht. Der Name Polyomino wurde 1953 von Solomon W. Golomb erfunden und von Martin Gardner in einer Kolumne " Mathematical Games " im November 1960 im Scientific American bekannt gemacht .

Mit Polyominos verwandt sind Polyiamonds , die aus gleichseitigen Dreiecken gebildet werden ; Polyhexe , gebildet aus regelmäßigen Sechsecken ; und andere ebene Polyformen . Polyominos wurden auf höhere Dimensionen verallgemeinert, indem Würfel zu Polywürfeln oder Hyperwürfeln zu Polyhyperwürfeln verbunden wurden.

In der statistischen Physik wird das Studium von Polyominos und ihren höherdimensionalen Analoga (die in dieser Literatur oft als Gittertiere bezeichnet werden ) auf Probleme in Physik und Chemie angewendet. Polyominoe wurden als Modelle für verzweigte Polymere und für Perkolationscluster verwendet .

Wie viele Rätsel in der Freizeitmathematik werfen Polyominos viele kombinatorische Probleme auf. Die einfachste ist das Aufzählen von Polyominos einer bestimmten Größe. Außer für spezielle Klassen von Polyominos wurde keine Formel gefunden. Es sind eine Reihe von Schätzungen bekannt und es gibt Algorithmen zu deren Berechnung.

Polyominos mit Löchern sind für manche Zwecke unpraktisch, wie zum Beispiel bei Fliesenproblemen. In manchen Kontexten werden Polyominos mit Löchern ausgeschlossen, sodass nur einfach verbundene Polyominos zugelassen werden.

Aufzählung von Polyominos

Freie, einseitige und feste Polyominos

Es gibt drei gängige Möglichkeiten, Polyominos für die Aufzählung zu unterscheiden:

  • freie Polyominos sind verschieden, wenn keines eine starre Transformation ( Translation , Rotation , Reflexion oder Gleitreflexion ) eines anderen ist (Teile, die aufgenommen und umgedreht werden können). Das Verschieben, Drehen, Reflektieren oder Gleiten, das ein freies Polyomino reflektiert, ändert seine Form nicht.
  • einseitige Polyominos sind verschieden, wenn keines eine Translation oder Rotation eines anderen ist (Stücke, die nicht umgedreht werden können). Das Verschieben oder Drehen eines einseitigen Polyominos ändert seine Form nicht.
  • feste Polyominos sind verschieden, wenn keines eine Translation eines anderen ist (Stücke, die weder gespiegelt noch gedreht werden können). Das Übersetzen eines festen Polyominos ändert seine Form nicht.

Die folgende Tabelle zeigt die Anzahl der Polyominos verschiedener Typen mit n Zellen.

n Name ( OEIS-  Sequenz) kostenlos einseitig ( A000988 ) behoben ( A001168 )
gesamt ( A000105 ) mit Löchern ( A001419 ) ohne Löcher ( A000104 )
1 monomino 1 0 1 1 1
2 Domino 1 0 1 1 2
3 tromino 2 0 2 2 6
4 Tetromin 5 0 5 7 19
5 Pentomino 12 0 12 18 63
6 hexomino 35 0 35 60 216
7 Heptomino 108 1 107 196 760
8 Octomino 369 6 363 704 2.725
9 Nonomino 1.285 37 1.248 2.500 9.910
10 decomino 4.655 195 4.460 9.189 36.446
11 undecomino 17.073 979 16.094 33.896 135.268
12 dodecomino 63.600 4.663 58.937 126.759 505.861

Ab 2004 hat Iwan Jensen die festen Polyominos bis zu n = 56 aufgezählt ; die Zahl der fixierten Polyominos mit 56 Zellen beträgt ungefähr 6,915 × 10 31 . Freie Polyominos wurden von Tomás Oliveira e Silva bis zu n = 28 und später von Toshihiro Shirakawa bis zu n = 45 aufgezählt .

Symmetrien von Polyominos

Die Diedergruppe D 4 ist die Gruppe von Symmetrien ( Symmetriegruppe ) eines Quadrats. Diese Gruppe enthält vier Drehungen und vier Spiegelungen. Sie wird durch abwechselnde Reflexionen an der x- Achse und an einer Diagonale erzeugt. Ein freies Polyomino entspricht höchstens 8 fixierten Polyominos, die seine Bilder unter den Symmetrien von D 4 sind . Diese Bilder sind jedoch nicht unbedingt unterschiedlich: Je mehr Symmetrie ein freies Polyomino hat, desto weniger eindeutige feste Gegenstücke hat es. Daher kann ein freies Polyomino, das unter einigen oder allen nicht-trivialen Symmetrien von D 4 invariant ist , nur 4, 2 oder 1 festen Polyominos entsprechen. Mathematisch sind freie Polyominos Äquivalenzklassen von festen Polyominos unter der Gruppe D 4 .

Polyominos haben die folgenden möglichen Symmetrien; die kleinste Anzahl von Quadraten, die in einem Polyomino mit dieser Symmetrie benötigt wird, ist in jedem Fall angegeben:

  • 8 feste Polyominos für jedes freie Polyomino:
    • keine Symmetrie (4)
  • 4 feste Polyominos für jedes freie Polyomino:
    • Spiegelsymmetrie bezüglich einer der Rasterlinienrichtungen (4)
    • Spiegelsymmetrie bezüglich einer Diagonalen (3)
    • 2-zählige Rotationssymmetrie: C 2 (4)
  • 2 feste Polyominos für jedes freie Polyomino:
    • Symmetrie bezüglich beider Gitterlinienrichtungen und damit auch 2-zählige Rotationssymmetrie: D 2 (2)
    • Symmetrie bezüglich beider Diagonalrichtungen und damit auch 2-zählige Rotationssymmetrie: D 2 (7)
    • 4-fache Rotationssymmetrie: C 4 (8)
  • 1 festes Polyomino für jedes freie Polyomino:
    • alle Symmetrie des Quadrats: D 4 (1).

Ebenso hängt die Anzahl der einseitigen Polyominos wie folgt von der Polyomino-Symmetrie ab:

  • 2 einseitige Polyominos für jedes freie Polyomino:
    • keine Symmetrie
    • 2-zählige Rotationssymmetrie: C 2
    • 4-fache Rotationssymmetrie: C 4
  • 1 einseitiges Polyomino für jedes freie Polyomino:
    • alle Symmetrie des Quadrats: D 4
    • Spiegelsymmetrie bezüglich einer der Gitterlinienrichtungen
    • Spiegelsymmetrie bezüglich einer diagonalen Linie
    • Symmetrie bezüglich beider Gitterlinienrichtungen und damit auch 2-zählige Rotationssymmetrie: D 2
    • Symmetrie zu beiden Diagonalrichtungen und damit auch 2-zählige Rotationssymmetrie: D 2 .

Die folgende Tabelle zeigt die Anzahl der Polyominos mit n Quadraten, sortiert nach Symmetriegruppen.

n keine ( A006749 ) Spiegel (90°) ( A006746 ) Spiegel (45°) ( A006748 ) C 2 ( A006747 ) D 2  (90 °) ( A056877 ) D 2  (45 °) ( A056878 ) C 4 ( A144553 ) D 4 ( A142886 )
1 0 0 0 0 0 0 0 1
2 0 0 0 0 1 0 0 0
3 0 0 1 0 1 0 0 0
4 1 1 0 1 1 0 0 1
5 5 2 2 1 1 0 0 1
6 20 6 2 5 2 0 0 0
7 84 9 7 4 3 1 0 0
8 316 23 5 18 4 1 1 1
9 1.196 38 26 19 4 0 0 2
10 4.461 90 22 73 8 1 0 0
11 16.750 147 91 73 10 2 0 0
12 62.878 341 79 278 fünfzehn 3 3 3

Algorithmen zur Aufzählung fester Polyominos

Induktive Algorithmen

Jedes Polyomino der Ordnung n +1 kann durch Addieren eines Quadrats zu einem Polyomino der Ordnung n erhalten werden . Dies führt zu Algorithmen zur induktiven Generierung von Polyominos.

Am einfachsten können bei einer gegebenen Liste von Polyominos der Ordnung n Quadrate neben jedem Polyomino an jeder möglichen Position hinzugefügt werden, und das resultierende Polyomino der Ordnung n + 1 kann der Liste hinzugefügt werden, wenn es kein Duplikat eines bereits gefundenen ist; Verfeinerungen bei der Reihenfolge der Aufzählung und Markierung benachbarter Quadrate, die nicht berücksichtigt werden sollten, reduzieren die Anzahl der Fälle, die auf Duplikate überprüft werden müssen. Dieses Verfahren kann verwendet werden, um entweder freie oder feste Polyominos aufzuzählen.

Eine ausgefeiltere Methode, die von Redelmeier beschrieben wurde, wurde von vielen Autoren verwendet, um nicht nur Polyominos zu zählen (ohne dass alle Polyominos der Ordnung n gespeichert werden müssen, um diejenigen der Ordnung n + 1) aufzuzählen , sondern auch um zu beweisen, dass Grenzen ihrer Zahl. Die Grundidee ist, dass wir mit einem einzelnen Quadrat beginnen und von dort aus Quadrate rekursiv hinzufügen. Abhängig von den Details kann es jedes n -omino n- mal zählen, einmal ausgehend von jedem seiner n Quadrate, oder kann so angeordnet sein, dass es jedes nur einmal zählt.

Die einfachste Implementierung besteht darin, jeweils ein Quadrat hinzuzufügen. Beginnen Sie mit einem Anfangsquadrat, nummerieren Sie die angrenzenden Quadrate im Uhrzeigersinn von oben mit 1, 2, 3 und 4. Wählen Sie nun eine Zahl zwischen 1 und 4 und fügen Sie an dieser Stelle ein Quadrat hinzu. Nummerieren Sie die nicht nummerierten angrenzenden Quadrate, beginnend mit 5. Wählen Sie dann eine Zahl, die größer als die zuvor gewählte Zahl ist, und fügen Sie dieses Quadrat hinzu. Wählen Sie weiter eine Zahl aus, die größer ist als die Nummer des aktuellen Quadrats, fügen Sie dieses Quadrat hinzu und nummerieren Sie dann die neuen angrenzenden Quadrate. Wenn n Quadrate erstellt wurden, wurde ein n -omino erstellt.

Dieses Verfahren stellt sicher, dass jedes feste Polyomino genau n- mal gezählt wird, einmal für jedes Startquadrat. Es kann so optimiert werden, dass es jedes Polyomino nur einmal zählt, anstatt n- mal. Beginnen Sie mit dem Anfangsquadrat und deklarieren Sie es als das untere linke Quadrat des Polyominos. Nummerieren Sie einfach kein Quadrat, das sich in einer unteren Reihe oder links neben dem Quadrat in derselben Reihe befindet. Dies ist die von Redelmeier beschriebene Version.

Wenn man stattdessen freie Polyominos zählen möchte, kann man nach dem Erzeugen jedes n- Ominos auf Symmetrien prüfen. Es ist jedoch schneller, symmetrische Polyominos separat zu erzeugen (durch eine Variation dieser Methode) und so die Anzahl der freien Polyominos durch das Lemma von Burnside zu bestimmen .

Transfer-Matrix-Methode

Der modernste Algorithmus zum Aufzählen der festen Polyominos wurde von Iwan Jensen entdeckt . Eine Verbesserung der Methode von Andrew Conway, sie ist exponentiell schneller als die vorherigen Methoden (jedoch ist ihre Laufzeit in n immer noch exponentiell ).

Sowohl Conways als auch Jensens Versionen der Transfer-Matrix-Methode beinhalten das Zählen der Anzahl von Polyominos, die eine bestimmte Breite haben. Die Berechnung der Zahl für alle Breiten ergibt die Gesamtzahl der Polyominos. Die Grundidee der Methode besteht darin, mögliche Anfangsreihen zu berücksichtigen und dann die minimale Anzahl von Quadraten zu bestimmen, die benötigt wird, um das Polyomino der gegebenen Breite zu vervollständigen. In Kombination mit der Verwendung von Generierungsfunktionen ist diese Technik in der Lage, viele Polyominos auf einmal zu zählen, wodurch sie um ein Vielfaches schneller ausgeführt werden kann als Methoden, die jedes Polyomino generieren müssen.

Obwohl er eine ausgezeichnete Laufzeit hat, besteht der Nachteil darin, dass dieser Algorithmus exponentiell viel Speicher verwendet (viele Gigabyte Speicher werden für n über 50 benötigt), viel schwieriger zu programmieren ist als die anderen Methoden und derzeit nicht zum Zählen verwendet werden kann freie Polyominos.

Asymptotisches Wachstum der Anzahl der Polyominos

Feste Polyominos

Theoretische Argumente und numerische Berechnungen stützen die Abschätzung der Anzahl fester Polyominos der Größe n

wobei λ = 4,0626 und c = 0,3169. Dieses Ergebnis ist jedoch nicht bewiesen und die Werte von λ und c sind nur Schätzungen.

Die bekannten theoretischen Ergebnisse sind bei weitem nicht so spezifisch wie diese Schätzung. Es ist bewiesen, dass

existiert. Mit anderen Worten, A n wächst exponentiell . Die bekannteste untere Schranke für λ , die im Jahr 2016 gefunden wurde, ist 4.00253. Die bekannteste obere Schranke, die seit den 1970er Jahren nicht verbessert wurde, ist λ < 4,65 .

Um eine untere Schranke festzulegen, ist eine einfache, aber sehr effektive Methode die Verkettung von Polyominos. Definieren Sie das Quadrat oben rechts als das Quadrat ganz rechts in der obersten Reihe des Polyominos. Definieren Sie das untere linke Quadrat auf ähnliche Weise. Dann kann das obere rechte Quadrat eines beliebigen Polyominos der Größe n an das untere linke Quadrat eines beliebigen Polyominos der Größe m angehängt werden , um ein eindeutiges ( n + m )-Omino zu erzeugen . Dies beweist , A n A m ≤ A n + m . Mit dieser Gleichung kann man λ ≥ ( A n ) 1/ n für alle n zeigen . Verfeinerungen dieses Verfahrens in Kombination mit Daten für A n ergeben die oben angegebene untere Schranke.

Die obere Schranke wird durch Verallgemeinerung der induktiven Methode der Aufzählung von Polyominos erreicht. Anstatt jeweils ein Quadrat hinzuzufügen, fügt man jeweils eine Gruppe von Quadraten hinzu. Dies wird oft als Hinzufügen von Zweigen beschrieben . Durch den Beweis, dass jedes n- Omino eine Folge von Zweigen ist, und durch den Nachweis von Grenzen für die Kombinationen möglicher Zweige erhält man eine obere Schranke für die Anzahl von n- Ominos. Im oben beschriebenen Algorithmus müssen wir beispielsweise bei jedem Schritt eine größere Zahl wählen, und es werden höchstens drei neue Zahlen hinzugefügt (da höchstens drei unnummerierte Quadrate an ein beliebiges nummeriertes Quadrat angrenzen). Dies kann verwendet werden, um eine obere Schranke von 6,75 zu erhalten. Mit 2,8 Millionen Zweigen erreichten Klarner und Rivest eine Obergrenze von 4,65.

Kostenlose Polyominos

Näherungen für die Anzahl fester Polyominos und freier Polyominos sind auf einfache Weise miteinander verbunden. Ein freies Polyomino ohne Symmetrien (Rotation oder Reflexion) entspricht 8 verschiedenen festen Polyominos, und für große n haben die meisten n- Ominos keine Symmetrien. Daher beträgt die Anzahl der festen n- Ominos ungefähr das 8-fache der Anzahl der freien n- Ominos. Darüber hinaus ist diese Näherung mit zunehmendem n exponentiell genauer .

Spezielle Klassen von Polyominos

Zur Aufzählung von Polyominos spezieller Klassen, wie der Klasse der konvexen Polyominos und der Klasse der gerichteten Polyominos , sind genaue Formeln bekannt .

Die Definition eines konvexen Polyominos unterscheidet sich von der üblichen Definition der Konvexität , ähnelt aber der Definition der orthogonalen konvexen Hülle . Ein Polyomino heißt vertikal oder spaltenkonvex, wenn sein Schnittpunkt mit einer vertikalen Linie konvex ist (mit anderen Worten, jede Spalte hat keine Löcher). In ähnlicher Weise heißt ein Polyomino horizontal oder reihenkonvex, wenn sein Schnittpunkt mit einer horizontalen Linie konvex ist. Ein Polyomino heißt konvex, wenn es zeilen- und spaltenkonvex ist.

Ein Polyomino heißt gerichtet, wenn es ein Quadrat, die Wurzel , enthält , so dass jedes zweite Quadrat durch Bewegungen um ein Quadrat nach oben oder rechts erreicht werden kann, ohne das Polyomino zu verlassen.

Gerichtete Polyominos, Spalten- (oder Reihen-)konvexe Polyominos und konvexe Polyominos wurden effektiv durch die Fläche n sowie durch einige andere Parameter wie den Umfang unter Verwendung von Erzeugungsfunktionen aufgezählt .

Ein Polyomino ist gleich, wenn seine Fläche gleich seinem Umfang ist. Ein gleichberechtigtes Polyomino muss aus einer geraden Anzahl von Quadraten bestehen; jede gerade Zahl größer als 15 ist möglich. Zum Beispiel sind das 16-Omino in Form eines 4 × 4-Quadrats und das 18-Omino in Form eines 3 × 6-Rechtecks ​​beide gleich. Bei Polyominos mit weniger als 15 Quadraten überschreitet der Umfang immer die Fläche.

Fliesen mit Polyominos

In Haltungsmathematik , sind Herausforderungen oft posierte für Fliesen einen vorgeschriebenen Bereich oder die gesamte Ebene, mit polyominoes und die damit verbundenen Probleme werden in sucht Mathematik und Informatik .

Tiling von Regionen mit Sätzen von Polyominos

In Rätseln wird häufig verlangt, eine bestimmte Region mit einem bestimmten Satz von Polyominos, wie den 12 Pentominos, zu kacheln. Die Bücher von Golomb und Gardner haben viele Beispiele. Ein typisches Puzzle besteht darin, ein 6×10-Rechteck mit den zwölf Pentominos zu kacheln; die 2339 Lösungen dafür wurden 1960 gefunden. Wo mehrere Kopien der Polyominos in der Menge erlaubt sind, definiert Golomb eine Hierarchie verschiedener Regionen, die eine Menge möglicherweise kacheln kann, wie Rechtecke, Streifen und die gesamte Ebene, und zeigt, dass unentscheidbar ist, ob Polyominos aus einer gegebenen Menge die Ebene kacheln können , indem man Sets von Wang-Kacheln auf Sets von Polyominos abbildet.

In Jigsaw Sudokus wird ein quadratisches Gitter mit polynominoförmigen Regionen gekachelt (Sequenz A172477 im OEIS ).

Kacheln von Regionen mit Kopien eines einzelnen Polyomino

Eine andere Klasse von Problemen fragt, ob Kopien eines gegebenen Polyominos ein Rechteck kacheln können , und wenn ja, welche Rechtecke sie kacheln können. Diese Probleme sind für bestimmte Polyominos ausführlich untersucht worden, und Ergebnistabellen für einzelne Polyominos sind verfügbar. Klarner und Göbel zeigten , dass für jeden polyomino es eine endliche Menge von ist prime Rechtecke es Fliesen, so dass alle anderen Rechtecken es Fliesen können von dieser prime Rechtecke mit Ziegeln gedeckt werden. Kamenetsky und Cooke zeigten, wie verschiedene disjunkte (sogenannte "löchrige") Polyominos Rechtecke kacheln können.

Jenseits von Rechtecken gab Golomb seine Hierarchie für einzelne Polyominos an: Ein Polyomino kann ein Rechteck, einen halben Streifen, einen gebogenen Streifen, eine vergrößerte Kopie seiner selbst, einen Quadranten, einen Streifen, eine halbe Ebene , die ganze Ebene, bestimmte Kombinationen oder keine von diesen. Darunter gibt es bestimmte Implikationen, die sowohl offensichtlich sind (wenn ein Polyomino beispielsweise die halbe Ebene kachelt, dann die gesamte Ebene kachelt) als auch weniger (wenn ein Polyomino beispielsweise eine vergrößerte Kopie von sich selbst kachelt, dann den Quadranten kachelt). . Polyominos der Ordnungen bis zu 6 werden in dieser Hierarchie charakterisiert (mit dem Status eines Hexominos, das später gefunden wurde, um ein Rechteck zu kacheln, zu diesem Zeitpunkt ungelöst).

2001 zeigten Cristopher Moore und John Michael Robson, dass das Problem, ein Polyomino mit Kopien eines anderen zu kacheln, NP-vollständig ist .

Kacheln der Ebene mit Kopien eines einzelnen Polyomino

Die beiden Nonominos mit Kacheln erfüllen das Conway-Kriterium nicht.

Auch das Kacheln der Ebene mit Kopien eines einzelnen Polyominos wurde viel diskutiert. Es wurde 1965 festgestellt, dass alle Polyominos bis hin zu Hexominos und alle bis auf vier Heptominos das Flugzeug kacheln. Es wurde dann von David Bird festgestellt, dass alle bis auf 26 Octominos das Flugzeug kacheln. Rawsthorne fand heraus, dass alle bis auf 235 Polyominos der Ordnung 9 Kacheln, und solche Ergebnisse wurden von Rhoads (bis Ordnung 14) und anderen auf höhere Ordnungen ausgedehnt. Polyominoes, die die Ebene kacheln, wurden nach den Symmetrien ihrer Kacheln und nach der Anzahl der Aspekte (Ausrichtungen) klassifiziert, in denen die Kacheln in ihnen erscheinen.

Die Untersuchung, welche Polyominos die Ebene kacheln können, wurde durch das Conway-Kriterium erleichtert : Mit Ausnahme von zwei Nonominos bilden alle kachelenden Polyominos bis zur Ordnung 9 einen Patch von mindestens einer Kachel, die sie erfüllt, mit Ausnahmen höherer Ordnung häufiger.

Mehrere Polyominos können größere Kopien von sich selbst kacheln, und das rekursive Wiederholen dieses Prozesses ergibt eine Reptilienkachelung der Ebene. Zum Beispiel ist es für jede positive ganze Zahl n möglich, n 2 Kopien des L-Trominos, L-Tetrominos oder P-Pentominos zu einer einzigen größeren Form ähnlich dem kleineren Polyomino, aus dem es gebildet wurde, zu kombinieren .

Eine gemeinsame Figur mit verschiedenen Polyominos kacheln

Eine minimale Kompatibilitätszahl für die T- und W- Pentominos .

Das Kompatibilitätsproblem besteht darin, zwei oder mehr Polyominos zu nehmen und eine Figur zu finden, die mit jedem gekachelt werden kann. Die Polyomino-Kompatibilität wurde seit den 1990er Jahren umfassend untersucht. Jorge Luis Mireles und Giovanni Resta haben Websites mit systematischen Ergebnissen veröffentlicht, und Livio Zucca zeigt Ergebnisse für einige komplizierte Fälle wie drei verschiedene Pentominos. Das allgemeine Problem kann schwer sein. Die erste Kompatibilitätszahl für die L- und X-Pentominos wurde 2005 veröffentlicht und hatte 80 Kacheln jeder Art. Viele Polyominopaare haben sich durch systematische Erschöpfung als unvereinbar erwiesen. Es ist kein Algorithmus bekannt, um zu entscheiden, ob zwei beliebige Polyominos kompatibel sind.

Polyominos in Puzzles und Spielen

Zusätzlich zu den oben beschriebenen Kachelproblemen gibt es mathematische Freizeiträtsel, bei denen ein Polyomino gefaltet werden muss, um andere Formen zu erzeugen. Gardner schlug mehrere einfache Spiele mit einem Satz kostenloser Pentominos und einem Schachbrett vor. Einige Varianten des Sudoku- Puzzles verwenden nichtnominoförmige Regionen im Raster. Das Videospiel Tetris basiert auf den sieben einseitigen Tetrominos (im Spiel "Tetriminos" geschrieben), und das Brettspiel Blokus verwendet alle freien Polyominos bis hin zu Pentominos.

Etymologie

Das Wort polyomino und die Namen der verschiedenen Ordnungen von polyomino alle Back-Formationen aus dem Wort sind Domino , ein gemeinsames Stück Spiel , bestehend aus zwei Quadraten, mit dem ersten Buchstaben d- fancifully als Version des Präfix interpretierte di- Bedeutung „zwei ." Der Name Domino für die Spielfigur stammt vermutlich von dem gefleckten Maskenkleid Domino , vom lateinischen Dominus .

Die meisten numerischen Präfixe sind griechisch. Polyominos der Ordnung 9 und 11 haben häufiger die lateinischen Präfixe nona- (nonomino) und undeca- (undecomino) als die griechischen Präfixe ennea- (enneomino) und hendeca- (hendecomino).

Siehe auch

  • Perkolationstheorie , die mathematische Untersuchung von zufälligen Teilmengen ganzzahliger Gitter. Die endlichen zusammenhängenden Komponenten dieser Teilmengen bilden Polyominos.
  • Young-Diagramm , eine spezielle Art von Polyomino, das in der Zahlentheorie zur Beschreibung ganzzahliger Partitionen und in der Gruppentheorie und Anwendungen in der mathematischen Physik verwendet wird, um Darstellungen der symmetrischen Gruppe zu beschreiben.
  • Blokus , ein Brettspiel mit Polyominos.
  • Squaregraph , eine Art ungerichteter Graph, der als Sonderfall die Graphen von Ecken und Kanten von Polyominos enthält.

Anmerkungen

Externe Links

Online-Polyomino-Solver

Veröffentlichungen