Polyomino

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

Für kleine $n$ sind auch die Bezeichnungen Monomino ( $n=1$ ), Domino ( $n=2$ ), Tromino ( $n=3$ ), Tetromino ( $n=4$ ), Pentomino ( $n=5$ ), Hexomino ( $n=6$ ), Heptomino ( $n=7$ ), Oktomino ( $n=8$ ), Nonomino oder Enneomino ( $n=9$ ), Dekomino ( $n=10$ ), Undekomino ( $n=11$ ), Dodekomino ( $n=12$ ) usw. üblich.

Definition

Ein Polyomino oder $n$ -Mino ist eine Figur $P$ , die aus $n\geq 1$ kongruenten Quadraten besteht, für die gilt

je zwei Quadrate haben entweder keinen Punkt oder eine Ecke oder eine Kante gemeinsam,
zu je zwei verschiedenen Quadraten $Q_{1}$ und $Q^{*}$ aus $P$ gibt es eine Folge $Q_{1}Q_{2}\ldots Q_{k-1}Q^{*}$ von benachbarten Quadraten aus $P$ .

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

Polyo1.svg

1. ungültig
Polyo2.svg

2. ungültig
Polyo3.svg

3. ungültig
Polyo4.svg

4. ungültig

Für besondere Anwendungen wird zusätzlich gefordert:

$P$ bildet eine einfach zusammenhängende Punktmenge.

Datei:Polyo5.svg

Polyomino mit Loch

Darstellung über Zusammenhangsgraphen

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

Tetromino zusammenhangsgraph i.svg
Tetromino zusammenhangsgraph l.svg
Tetromino zusammenhangsgraph t.svg
Tetromino zusammenhangsgraph z.svg
Tetromino zusammenhangsgraph o.svg

Konstruktion

Datei:Tetrominos.svg

die 5 Tetrominos

Bestimmung der Anzahlen

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

die 12 Pentominos

die 35 Hexominos

$A(n)$ bezeichnet die Anzahl Polyominos, die sich bis auf Kongruenz aus $n$ Quadraten bilden lassen. $A'(n)$ ist die Anzahl unter Beachtung der Orientierung, d. h. zueinander spiegelbildliche (wie oben illustriert) werden als verschieden betrachtet. $A''(n)$ 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 $A(n)$ ist von Interesse.

$n$	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A(n)} ^[1]	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A'(n)} ^[2]	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A''(n)} ^[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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=7} an abweichende Zahlen.^[4]

Rekursive Fortsetzung

Algorithmus

Man kann leicht ein rekursives Verfahren beschreiben, das es gestattet, aus der Kenntnis aller Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} -Minos Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n \geq 2)} alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Minos zu gewinnen. Es lässt sich zunächst zeigen, dass es zu einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Mino Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_2} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n \geq 2)} ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} -Mino Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_1} und ein Quadrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q} gibt, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_2 = P_1 \cup Q} ist. Dadurch kann von der Kenntnis der Klassen der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} -Minos ausgegangen werden. Durch Anfügen eines Quadrates entsteht je ein Repräsentant der Klassen der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Minos. Auf diese Weise kann auch die Anzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A(n)} der Klassen bestimmt werden. Wir verfahren wie folgt.

Wir nummerieren die Klassen der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} -Minos durch und beginnen mit einem Repräsentanten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} der ersten Klasse, und betrachten systematisch alle Lagen eines Quadrates Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q} , die überhaupt zu einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Mino Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P \cup Q} führen können. Diese Lagen werden mit Datei:Rechteck strich.svg oder Datei:Rechteck punkt.svg markiert, je nachdem, ob das entsprechende Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Mino zu den bisherigen kongruent ist oder nicht. Nach gleicher Weise wird bei den nächsten Klassen der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} -Minos verfahren. Natürlich kann dabei ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Mino entstehen, welches zu einem aus vorangegangenen Schritten kongruent ist. Solche werden mit einem Lagekästchen Datei:Rechteck lage.svg bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (i=1,2,\ldots)} .

Nach endlich vielen Schritten bricht das Verfahren ab und es liefert einen Repräsentanten für jede Klasse der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Minos.

Beispiel

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

Computergestützt

Auf der Grundlage dieses Verfahrens lassen sich die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A(n)} mit Computern bestimmen. Dabei lassen sich Polyominos durch eine Matrix mit 0 und 1 wie in folgendem Beispiel beschreiben.

Datei:Heptomino transform.svg wird zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}}

Hexominos

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.

Verwendung

Packungen

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

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Minos für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=1..5} 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.^[5] 2001 erschien das Spiel Rumis, welches dreidimensionale Steine (Polywürfel) verwendet.^[6]

Pädagogik

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.

Literatur

Solomon W. Golomb: Polyominoes. Puzzles, Patterns, Problems, and Packings. 2. erweiterte Auflage. Princeton University Press, Princeton 1994, ISBN 0-691-08573-0

Weblinks

Commons: Polyomino – Sammlung von Bildern, Videos und Audiodateien

Polyominos bei Wolfram Mathworld
Gerard's Universal Polyomino Solver
Puzzlespiel mit Polyominos 3D
Spiel zur Füllung mit Polyominos 2D (Memento vom 20. April 2008 im Internet Archive)
Ebene Figuren – Vielecke (Anwendung für Kinder) (Memento vom 28. September 2007 im Internet Archive)

Einzelnachweise

↑ Folge A000105 in OEIS
↑ Folge A000988 in OEIS
↑ Folge A001168 in OEIS
↑ Beispielsweise Folge A000104 in OEIS
↑ Übersicht Polyomino-Spiele bei Boardgamegeek
↑ Rezension von Rumis bei hall9000.de

[1] Folge A000105 in OEIS

[2] Folge A000988 in OEIS

[3] Folge A001168 in OEIS

[4] Beispielsweise Folge A000104 in OEIS

[5] Übersicht Polyomino-Spiele bei Boardgamegeek

[6] Rezension von Rumis bei hall9000.de

[1]

[2]

[3]

[4]

[5]

[6]

Anonym

Suche

Polyomino

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis