N-Minos

N-Minos

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

Inhaltsverzeichnis

Definition

Ein Polyomino oder n-Mino ist eine Figur P, die aus n \geq 1 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 Q1 und Q * aus P gibt es eine Folge Q_1 Q_2 \ldots Q_{k-1} Q^* von benachbarten Quadraten aus P
  3. P bildet eine einfach zusammenhängende Punktmenge.

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

1. gilt nicht
1. gilt nicht
2. gilt nicht
2. gilt nicht
3. gilt nicht

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.

Konstruktion

5 mögliche Tetrominos
35 mögliche Hexominos

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

nicht-orientierungserhaltende Bewegung
nicht-orientierungserhaltende Bewegung

A(n) bezeichne die Anzahl der kongrunenten Polyominos, die sich aus n Quadraten bilden lassen, A'(n) die Anzahl unter Beachtung der Orientierung. A''(n) bezeichnet letztlich alle möglichen Lagen, dabei werden sogar zwei zueinander um 90° gedrehte aber sonst gleiche Polyominos als verschieden angesehen. Insbesondere A(n) ist von großem Interesse.

n A(n) A'(n) A''(n)
1 1 1 1
2 1 1 2
3 2 2 6
4 5 7 \ldots
5 12 \ldots
6 35
7 108
8 369
9 1285
10 4655
11 17073
12 63600
13 238591
14 901971
15 3426576

rekursive Fortsetzung

Algorithmus

Man kann leicht ein rekursives Verfahren beschreiben, das es gestattet, aus der Kenntnis aller n − 1-Minos (n \geq 2) alle n-Minos zu gewinnen. Es lässt sich zunächst zeigen, dass es zu deinem n-Mino P2 (n \geq 2) ein n − 1-Mino P1 und ein Quadrat Q gibt, so dass P_2 = P_1 \cup Q ist. Dadurch kann von der Kenntnis der Klassen der n − 1-Minos ausgegangen werden. Durch Anfügen eines Quadrates entsteht je ein Repräsentant der Klassen der n-Minos. Auf diese Weise kann auch die Anzahl A(n) der Klassen bestimmt werden. Wir verfahren wie folgt.

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

Nach endlich vielen Schritten bricht das Verfahren ab und es liefert einen Repräsentanten für jede Klasse der 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 A(n) mit Computern bestimmen. Dabei lassen sich Polyominos durch Matrizen mit 0 und 1 wie in folgendem Beispiel beschreiben.

Bild:heptomino_transform.svg wird zu \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}

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

Im Deutschen sind das Spiel Domino und im Russischen das Pentomino (Begriff stammt vom amerikanischen Mathematiker Solomon W. Golomb) 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. dreidimensionale - zurückgreifen. Neuere Brettspiele sind das 2000 erschienene Blokus sowie das 2003 in Schweden und 2005 in Deutschland erschienene Ubongo, wo jeweils die verschieden großen n-Minos für n = 1..5 als Spielmaterial verwendet werden. 2001 erschien das Spiel Rumis, welches dreidimensionale Steine verwendet.[1]

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 vorgegeben 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 Figuren werden 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

Einzelnachweise

  1. Rezension von Rumis bei hall9000.de

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Minos EMI — S.A. Type Subsidiary Industry Music Founded 1931 Headquarters …   Wikipedia

  • Minos — Minos, von Schlangen umschlungen und gebissen (Detail eines Freskos des Jüngsten Gerichts in der Sixtinischen Kapelle – Michelangelo, 1536 41) Minos (griechisch Μίνως) ist in der griechischen Mythologie Sohn des Zeus und der Europa und der… …   Deutsch Wikipedia

  • Minos (Saint Seiya) — Minos Personnage de fiction apparaissant dans Saint Seiya Logo de Saint Seiya …   Wikipédia en Français

  • Minos II — MINOS II, (⇒ Tab. XX.) des Lykastes Sohn, Diod. Sic. l. IV. c. 62. p. 183. und also des Minos I Enkel, wiewohl ihn auch einige selbst für Jupiters Sohn angeben. Hygin. Fab. 41. Apollod. l. III. c. 1. §. 3. & ad eum Gale l. c. §. 4. Sie verwirren… …   Gründliches mythologisches Lexikon

  • Minos Kyriakou — Minos X. Kyriakou (alternate spelling: Minos Kiriakou) (born May 31, 1942 in Poros, Greece; in Greek: Μίνως (Μηνάς)Κυριακού) is a Greek billionaire[1] shipping magnate and businessman. He is the Chairman of Euroholdings Capital Investment… …   Wikipedia

  • Minos (disambiguation) — Minos was a mythical king of Crete. Minos may also refer to: Minos (dialogue), one of the dialogues of Plato Palace of Minos, a Bronze Age archaeological site on Crete USS Minos (ARL 14), a tank landing ship Troides minos, the southern birdwing… …   Wikipedia

  • MINOS — Roi légendaire de Crète, fils de Zeus et d’Europe. Il monta sur le trône de Crète grâce à l’assistance de Poséidon et assura l’hégémonie de Cnossos sur les îles de la mer Égée, en colonisant nombre d’entre elles et en débarrassant la mer des… …   Encyclopédie Universelle

  • Minos (personnage) — Minos est un personnage du manga et dessin animé Goldorak. Sommaire 1 Rôle, dénomination et doublage 2 Signification du nom 3 Caractère et biographie du personnage …   Wikipédia en Français

  • MINOS — Detektor MINOS steht für Main Injector Neutrino Oscillation Search und bezeichnet einen Neutrinodetektor für Myon Neutrinos des Soudan Underground Laboratory. Der MINOS Detektor in der ehemaligen Soudan Eisenmine (Minnesota/USA) soll Mischwinkel… …   Deutsch Wikipedia

  • Minos Beach Art Hotel — (Агиос Николаос,Греция) Категория отеля: 5 звездочный отель Адрес: Akti Ilia S …   Каталог отелей

  • Minos — {{Minos}} Sohn des Zeus* und der Europa*, König und erster Gesetzgeber der Kreter, von Pasiphae* Vater des Androgeos*, der Phaidra*, der Ariadne* und weiterer drei Söhne, Stiefvater des Minotauros*, für den ihm Daidalos* das Labyrinth baute. Als… …   Who's who in der antiken Mythologie

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”