Polyomino

Fläche, die aus n zusammenhängenden Quadraten besteht
(Weitergeleitet von Tetromino)

Ein Polyomino (Kunstwort, abgeleitet von Domino) ist eine Fläche, die aus zusammenhängenden Quadraten besteht.

Für kleine sind auch die Bezeichnungen Monomino (), Domino (), Tromino (), Tetromino (), Pentomino (), Hexomino (), Heptomino (), Oktomino (), Nonomino oder Enneomino (), Dekomino (), Undekomino (), Dodekomino () usw. üblich.

Definition

Bearbeiten

Ein Polyomino oder  -Mino ist eine Figur  , die aus   kongruenten Quadraten besteht, für die gilt

  1. je zwei Quadrate haben entweder keinen Punkt oder eine Ecke oder eine Kante gemeinsam,
  2. zu je zwei verschiedenen Quadraten   und   aus   gibt es eine Folge   von benachbarten Quadraten aus  .

Dabei heißen zwei Quadrate benachbart, wenn die Menge ihrer gemeinsamen Punkte eine Seite ist. Folgende Beispiele stellen demnach keine Polyominos dar.

Für besondere Anwendungen wird zusätzlich gefordert:

 
Polyomino mit Loch

Darstellung über Zusammenhangsgraphen

Bearbeiten

Jedem Polyomino   lässt sich ein Zusammenhangsgraph zuordnen, indem man jedes Quadrat aus   als Knoten und das Benachbartsein zweier Quadrate durch eine Kante wiedergibt. Nachfolgend wird dies anhand der 5 Tetrominos dargestellt.

Konstruktion

Bearbeiten
 
Die 5 Tetrominos

Bestimmung der Anzahlen

Bearbeiten

Es gibt verschiedene Ansätze, die Anzahl der Polyominos zu bestimmen. Am häufigsten wird nur bis auf Kongruenz unterschieden. In praktischen Sachverhalten sind jedoch häufig nur orientierungserhaltende Bewegungen für das Zur-Deckung-Bringen zugelassen, also nur Drehungen und Verschiebungen und keine Achsenspiegelungen. Auch bei dem Spiel Tetris ist dies der Fall. Kongruente Polyominos, die eine unterschiedliche Orientierung besitzen, werden dabei als verschieden angesehen

nicht-orientierungserhaltende Bewegung
 
Die 12 Pentominos
 
Die 35 Hexominos

  bezeichnet die Anzahl Polyominos, die sich bis auf Kongruenz aus   Quadraten bilden lassen.   ist die Anzahl unter Beachtung der Orientierung, d. h. zueinander spiegelbildliche (wie oben illustriert) werden als verschieden betrachtet.   bezeichnet die Anzahl unter Beachtung der Orientierung und aller möglichen Lagen, dabei werden sogar zwei zueinander gedrehte, aber sonst gleiche Polyominos als verschieden angesehen. Vor allem   ist von Interesse.

   [1]  [2]  [3]
1 1 1 1
2 1 1 2
3 2 2 6
4 5 7 19
5 12 18 63
6 35 60 216
7 108 196 760
8 369 704 2.725
9 1.285 2.500 9.910
10 4.655 9.189 36.446
11 17.073 33.896 135.268
12 63.600 126.759 505.861
13 238.591 476.270 1.903 890
14 901.971 1.802.312 7.204.874
15 3.426.576 6.849.777 27.394.666

Werden ausschließlich einfach zusammenhängende Polyominos gezählt, so ergeben sich von   an abweichende Zahlen.[4]

Rekursive Fortsetzung

Bearbeiten

Algorithmus

Bearbeiten

Man kann leicht ein rekursives Verfahren beschreiben, das es gestattet, aus der Kenntnis aller  -Minos   alle  -Minos zu gewinnen. Es lässt sich zunächst zeigen, dass es zu einem  -Mino     ein  -Mino   und ein Quadrat   gibt, so dass   ist. Dadurch kann von der Kenntnis der Klassen der  -Minos ausgegangen werden. Durch Anfügen eines Quadrates entsteht je ein Repräsentant der Klassen der  -Minos. Auf diese Weise kann auch die Anzahl   der Klassen bestimmt werden. Wir verfahren wie folgt.

Wir nummerieren die Klassen der  -Minos durch und beginnen mit einem Repräsentanten   der ersten Klasse und betrachten systematisch alle Lagen eines Quadrates  , die überhaupt zu einem  -Mino   führen können. Diese Lagen werden mit   oder   markiert, je nachdem, ob das entsprechende  -Mino zu den bisherigen kongruent ist oder nicht. Nach gleicher Weise wird bei den nächsten Klassen der  -Minos verfahren. Natürlich kann dabei ein  -Mino entstehen, welches zu einem aus vorangegangenen Schritten kongruent ist. Solche werden mit einem Lagekästchen   bezeichnet  .

Nach endlich vielen Schritten bricht das Verfahren ab und es liefert einen Repräsentanten für jede Klasse der  -Minos.

Beispiel

Bearbeiten

Der rekursive Algorithmus soll bei der Ermittlung der Pentominos aus Tetrominos eingesetzt werden.

Computergestützt

Bearbeiten

Auf der Grundlage dieses Verfahrens lassen sich die   mit Computern bestimmen. Dabei lassen sich Polyominos durch eine Matrix mit 0 und 1 wie in folgendem Beispiel beschreiben.

  wird zu  

Hexominos

Bearbeiten

Eine Untergruppe von 11 der 35 Hexominos stellen geometrisch gesehen das Netz eines Würfels dar, da er durch 6 quadratische Flächen begrenzt wird.

Zusammengesetzte ähnliche Polyominos (Reptiles)

Bearbeiten
 
Figur 1
 
Figur 2
 
Figur 3

Allgemeine Reptiles-Definitionen

Bearbeiten
  • Ähnliche Figuren, die sich lückenlos zu einer größeren Figur, die zu den kleineren Figuren ähnlich ist, zusammensetzen lassen, werden im Englischen als Reptiles (Abkürzung für replicating tiles) bezeichnet.
  • Ist   die Anzahl der ähnlichen Teilfiguren, so wird die zusammengesetzte Figur rep- -Figur genannt.

Anwendungsbeispiele zu Polyominos

Bearbeiten

Im Folgenden sei  . Unter den verschiedenen Arten von Polyominos gibt es rep- -Figuren und rep- -Figuren (Figuren 1, 2 und 3).[5][6]

Verwendung

Bearbeiten

Packungen

Bearbeiten

Welche notwendigen und hinreichenden Bedingungen bestehen für die positiv ganzzahligen Seitenlängen eines Rechteckes, damit dieses mit bestimmten Sorten von Polyominos gepackt werden kann.

Spieleindustrie

Bearbeiten

Die Spiele Domino und Pentomino (Begriff stammt vom amerikanischen Mathematiker Solomon W. Golomb) sind weit verbreitet. Tetrominos kommen unter anderen in dem vom russischen Programmierer Alexei Paschitnow 1985 entwickelten Computerspiel Tetris zum Einsatz, wobei komplexere Versionen dieses Spiels auch auf andere Polyominos – ggf. Polywürfel, z. B. BlockOut – zurückgreifen. Ein Brettspiel, das dem Computerspiel Tetris nahe kommt, ist FITS (2009) von Reiner Knizia. Es nahm sich das Computerspiel ausdrücklich zum Vorbild. Weitere neuere Brettspiele sind das 2000 erschienene Blokus sowie Ubongo (2005), wo jeweils die verschiedenen großen  -Minos für   als Spielmaterial verwendet werden. Auch die Spiele Patchwork (2014) und Cottage Garden (2016) von Uwe Rosenberg sowie Die Baumeister von Arkadia (2006) von Rüdiger Dorn, NMBR 9 (2017) von Peter Wichmann und Bärenpark (2017) von Phil Walker-Harding nutzen diese Formen als Legeteile. Bei Ein Fest für Odin (2016) von Uwe Rosenberg sind die Plättchen rechteckig angeordnet. Auch dieses Spiel wird als Polyomino-Spiel eingestuft.[7] 2001 erschien das Spiel Rumis, welches dreidimensionale Steine (Polywürfel) verwendet.[8]

Pädagogik

Bearbeiten

Die Bausteine finden in der Grundschule Verwendung und dienen der Verbesserung der räumlichen Vorstellung. Ziel ist es, zu einer vorgegebenen Menge von Bausteinen Figuren zu finden oder für vorgegebene Figuren eine Zerlegung in die entsprechenden Bausteine.

Es ist nicht möglich, aus allen 5 möglichen Tetronimos ein 5×4 Rechteck zu erstellen. Es ist auch nicht möglich, ohne Mehrfachverwendung eines Winkelstücks, ein 4×4 Quadrat aus Tetrominos zu erstellen. Die verwendeten Figuren werden, wenn für sie Tetrominos verwendet werden, die den Buchstaben L, T und Z ähnlich sind, auch LTZ-Parkette genannt.

Verwandte Themen

Bearbeiten
  • Polywürfel (auch Polykuben) – das dreidimensionale Pendant mit Würfeln

Literatur

Bearbeiten
Bearbeiten
Commons: Polyomino – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

Bearbeiten
  1. Folge A000105 in OEIS
  2. Folge A000988 in OEIS
  3. Folge A001168 in OEIS
  4. Beispielsweise Folge A000104 in OEIS
  5. Claudi Alsina, Roger B. Nelsen: Perlen der Mathematik - 20 geometrische Figuren als Ausgangspunkte für mathematische Erkundungsreisen, Springer Spektrum, Springer-Verlag GmbH Berlin Heidelberg 2015, ISBN 978-3-662-45460-2, Seiten 51 bis 54
  6. George E. Martin: Polyominoes: A Guide to Puzzles and Problems in Tiling, AMS/MAA, Washington 1991
  7. Übersicht Polyomino-Spiele bei Boardgamegeek
  8. Rezension von Rumis bei hall9000.de