Der "Rubiks Cube", in Deutschland auch "Zauberwürfel" genannt, ist wohl das bekannteste Spielzeug aus den 80er Jahren! Jeder hatte damals einen. Es handelt sich um einen kleinen Würfel mit Aufklebern in sechs verschiedenen Farben auf allen Seiten, an dem sich jede Seite drehen lässt. Ziel ist es, den Würfel in die Ausgangssituation zurückzudrehen, d.h. so, dass jede Seite einheitlich gefärbt ist.
In diesem Artikel möchte ich eine Einführung zu diesem Spielzeug geben und kurz (!) anschneiden, wie man ihn mathematisch beschreiben kann. Es stellt sich nämlich heraus, dass der Rubiks Cube ein schönes Beispiel für eine Permutationsgruppe ist, nämlich eine Untergruppe der symmetrischen Gruppe auf 48 bzw. 54 Elementen. Meiner Ansicht nach das perfekte Hobby (nicht unbedingt nur für Mathe-Fans).Um diesem Artikel folgen zu können sollte der Leser am besten selbst einen Rubiks Cube zur Hand haben! Wer keinen Würfel hat und durch diesen Artikel Lust darauf bekommt: Bei Amazon.de oder bei cubikon.de gibt es welche zu kaufen. Wie man einen Cube nun genau löst werde ich hier nicht erklären, dazu gibt es genug Seiten im Internet, z.B. diese: Speedcubing Unter Speedcubing versteht man, wie der Name bereits suggeriert, das Lösen von Rubiks Cubes und anderen ähnlichen Puzzlen auf Zeit. Es gibt dafür eine relativ große Community (mehrere Tausend Leute weltweit) und es ist tatsächlich nicht so schwer zu lernen. Nach weniger als ein paar Wochen Übung kann jeder auf Zeiten von unter einer Minute kommen, nach ein paar Monaten durchaus auch deutlich darunter. Der aktuelle Rekord liegt bei unter 10 Sekunden. Neben dem 3x3x3 Cube gibt es noch viele weitere Varianten, z.B. 2x2x2, 4x4x4, 5x5x5, Megaminx, Pyraminx oder andere Disziplinen, z.B. das Lösen mit möglichst wenig Zügen, das Blindlösen, Lösen mit einer Hand, etc.
Wer daran interessiert ist oder mal sehen möchte wie sowas aussieht: Einfach mal auf speedcubing.com vorbei schauen oder bei youtube nach ein paar Videos suchen. Auch wenn man sich nicht für die Mathematik dahinter interessiert (die auch überhaupt nicht notwendig ist um das zu lernen) macht es sehr viel Spaß! Aber Vorsicht, jeder sei hiermit gewarnt, dieses Spielzeug hat enormes Suchtpotential! Ich habe schon mehrere Leute nach sehr kurzer Zeit in die Abhängigkeit getrieben!
Ein paar Begriffe - Ecken, Kanten und Centers sind die drei Typen von Steinen, aus denen der Rubiks Cube besteht. Ein Center hat genau einen Aufkleber (6 Stück), eine Kante hat genau zwei Aufkleber (12 Stück) und eine Ecke hat genau drei Aufkleber (8 Stück). Der Typ der Steine kann offensichtlich durch die Drehungen nicht geändert werden, d.h. es ist z.B. nicht möglich einen Kantenstein mit einem Eckenstein zu tauschen, etc.. Ausserdem sind die Centers fest, d.h. wenn Weiß gegenüber von Gelb ist wird das immer so sein, usw.
- U,D,B,F,R,L: Die sechs Basisdrehungen des Würfels (Up, Down, Back, Front, Right, Left), jeweils um 90° im Uhrzeigersinn (bei Draufsicht auf die jeweilige Seite) (siehe auch hier)
- U',D',B',F',R',L': Die jeweils entgegengesetzten Drehungen
- Ein Algorithmus ist eine Zugfolge, also eine Komposition der Basisdrehungen, z.B. R U R' F' B F
- Orientierung und Permutation: Jeder Stein eines Rubiks Cubes in jeder möglichen Konfiguration hat genau zwei Parameter. Seine Permutation, d.h. seine Position auf dem Würfel, und seine Orientierung. Ecken haben drei mögliche Orientierungen (z.B. gelber Aufkleber oben/vorne/rechts), Kanten haben zwei mögliche Orientierungen
Gesetzmäßigkeiten Offensichtlich ist nicht jede Permutation der Aufkleber möglich. Aber auch andere Konfigurationen, die auf den ersten Blick erreichbar erscheinen, sind auf einem korrekt zusammen gebauten Würfel nicht zu erzeugen. Wenn ein Rubiks Cube auseinandergenommen und zufällig wieder zusammengebaut wird, ist dieser nur mit einer Wahrscheinlichkeit von 1:12 tatsächlich lösbar. Es gelten die folgenden Cube Gesetze: - Nur die Hälfte der Permutationen ist möglich: Die Anzahl der Vertauschungen von Steinen ist immer gerade
- Nur die Hälfte der Kanten Orientierungen ist möglich: Die Anzahl der Kanten, die von einem Zug umorientiert ("gekippt") werden ist immer gerade, d.h. wenn eine Kante gekippt wird, dann immer noch eine weitere
- Nur ein Drittel der Ecken Orientierungen ist möglich
Die Cube Gruppe Der Rubiks Cube besteht aus 6 Seiten mit jeweils 9 Aufklebern, also insgesamt 54 Aufkleber. Die Aufkleber in den Mittelstücken sind fix (d.h. es gibt keine Drehungen des Würfels, so dass diese Aufkleber untereinander permutiert werden können), daher wollen wir diese ignorieren. Alle übrigen Aufkleber werden wir durchnummerieren, z.B. nach folgendem Schema: | | 1 | 2 | 3 | | | | | 4 | U | 5 | | | | | 6 | 7 | 8 | | | | | 9 | 10 | 11 | | 17 | 18 | 19 | | 25 | 26 | 27 | | 33 | 34 | 35 | | 12 | L | 13 | | 20 | F | 21 | | 28 | R | 29 | | 36 | B | 37 | | 14 | 15 | 16 | | 22 | 23 | 24 | | 30 | 31 | 32 | | 38 | 39 | 40 | | | 41 | 42 | 43 | | | 44 | D | 45 | | | 46 | 47 | 48 | | Wir erhalten auf diese Weise also eine Bijektion zwischen Aufkleber und den natürlichen Zahlen von 1 bis 48. Die sechs Drehungen des Würfels können jetzt (z.B. in disjunkter Zykelschreibweise) als Permutation der Aufkleber beschrieben werden: \ F = (17,19,24,22)(18,21,23,20)(06,25,43,16)(07,28,42,13)(08,30,41,11) B = (33,35,40,38)(34,37,39,36)(03,09,46,32)(02,12,47,29)(01,14,48,27) L = (09,11,16,14)(10,13,15,12)(01,17,41,40)(04,20,44,37)(06,22,46,35) R = (25,27,32,30)(26,29,31,28)(03,38,43,19)(05,36,45,21)(08,33,48,24) U = (01,03,08,06)(02,05,07,04)(09,33,25,17)(10,34,26,18)(11,35,27,19) D = (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40) Bemerkung: Offensichtlich hat jede der sechs Permutationen eine Ordnung von 4, d.h. jede der sechs Drehungen führt nach viermaligen ausführen wieder zur "Startposition".
Wir haben nun bereits eine "einfache" Möglichkeit um die Ordnung eines beliebigen Rubiks Cube Zuges zu bestimmen, da die Ordnung einer Permutation in disjunkter Zykelschreibweise genau das kgV der Zykellängen ist.
Ein paar Beispiele:
Folgende Beispiele kann man z.B. gut mit einem Computeralgebrasystem wie GAP berechnen:
\
Order(U) = 4
Order(UD) = Order(DU) = 4
Order(RU) = Order( (1,3,38,43,11,35,27,32,30,17,9,33,48,24,6)
(2,5,36,45,21,7,4)
(8,25,19)
(10,34,26,29,31,28,18))
\ = kgV(15,7,3,7)
\ = 105
Order(R2 U' R' U' R U R U R U' R) = Order((2,4,5)(10,26,34)) = 3
D.h. man muss z.B. den Zug "R U" 105 mal wiederholen um wieder zum gelösten Würfel zurück zu kehren. Bei dem letztgenannten Zug handelt es sich um einen sogenannten "Edge 3 Cycle", ein Algorithmus, der drei der vier Kanten der oberen Ebene zyklisch vertauscht, ohne die Orientierung zu ändern.
(Für weitere interessante Dinge, die man mit GAP machen kann, siehe Analyzing Rubik's Cube with GAP von Martin Schoenert, Lehrstuhl D für Mathematik, RWTH Aachen)
\
\big\Definition:\normal
Sei M := { 1, 2, ..., 48 } die Menge der Aufkleber des Rubik's Cubes und R,L,U,D,F,B \el\ S_M seien die sechs Basisdrehungen. Dann heisst die Permutationsgruppe, die von den sechs Basisdrehungen erzeugt wird, G := die \stress\ Rubik's Cube Group \normal\ und es gilt G \subset\ S_M = S_(48). Wie die meisten Permutationsgruppen ist G nicht abelsch (G hat sogar fast triviales Zentrum, siehe unten).
\
\big\Bemerkung:\normal
Die Zuordnung zwischen Stellungen des Würfels und Algorithmen ist nicht eindeutig! D.h. es gibt für jede Stellung mehrere Züge, die diese Stellung auf einem gelösten Würfel erzeugen!
\
\big\Satz:\normal
Die Ordnung der Cube Group entspricht der Anzahl der möglichen Stellungen:
\|G\| = (8! * 3^8 * 12! * 2^12) / (2 * 2 * 3) = 2^27 * 3^14 * 5^3 * 7^2 * 11^1 = 43.252.003.274.489.856.000
Diese Zahl ist übrigens um 1 größer als eine Primzahl, d.h. die Anzahl
der ungelösten Stellungen (G ohne Identität) ist prim.
(8! Permutationen der Ecken, 3^8 mögliche Eckenorientierungen, 12! mögliche
Permutationen der Kanten, 2^12 mögliche Kantenorientierungen, der Nenner ergibt sich
aus den oben genannten Cube Gesetzen)
\
\big\Folgerung:\normal
Nach dem Satz von Lagrange teilt die Ordnung jedes Elementes die Gruppenordnung. Daher existiert z.B. kein Zug mit Ordnung 13. Nach Cauchy gilt sogar, dass für jede Primzahl p mit p teilt \|G\| ein Zug existiert, der Ordnung p hat. D.h. es existiert z.B. ein Zug mit der Ordnung 11.
Da die Gruppe endlich ist hat auch jedes Element endliche Ordnung. Tatsächlich ist die maximale Ordnung eines Elementes aber deutlich kleiner als die Gruppenordnung.
\
\big\Satz:\normal
Der Zug R * U^2 * D^(-1) * B * D^(-1) hat Ordnung 1260. Es existiert kein Zug mit größerer Ordnung.
\
\big\Definition:\normal
Das Zentrum Z(G) einer Gruppe G ist die Untergruppe von G, die genau die Elemente von G enthält, die mit allen anderen kommutieren, d.h.:
Z(G) = \{ z \el\ G \| zg = gz \forall\ g \el\ G \}
\
\big\Satz:\normal
Sei G die Cube Group, dann gilt: Z(G) = {id, superflip} mit
superflip = R^(-1) * U^2 * B * L^(-1) * F * U^(-1) * B * D * F * U *
\ D^(-1) * L * D^2 * F^(-1) * R * B^(-1) * D * F^(-1) * U^(-1) *
\ B^(-1) * U * D^(-1)
Dieser Zug kippt alle Kanten (ohne sie zu permutieren) und behält alle Eckenkonfigurationen bei. Dieser Zug ist also, neben der Identität, der
einzige, der mit allen anderen Zügen kommutiert.
Isomorphieklassen von Untergruppen
Viele kleine (!) Untergruppen der Cube Group lassen sich relativ einfach durch allgemein bekannte Gruppen ausdrücken. z.B. ist jede Untergruppe, die von einer 180° Drehung einer beliebigen Seite, z.B. R2, erzeugt wird, isomorph zu C_2 und die von R2F2R2F2 und R2 erzeugte Untergruppe ist isomorph zur symmetrischen Gruppe auf 3 Elementen. Eine ausführliche Liste (mit interessanteren Untergruppen) findet sich auf Jaaps Puzzle Page
Konjugation und Kommutatoren
Die zwei wichtigsten Gruppentheoretischen Konzepte, die dazu dienen neue Zugfolgen zu finden oder bereits bekannte Zugfolgen sinnvoll anwenden zu können sind die Konjugation und die Bildung von Kommutatoren.
\
\big\Definition:\normal
Seien g,h \el\ G, dann heisst h * g * h^(-1) die Konjugation von g mit h.
Die Konjugation mit einem Element ist ein Automorphismus der Gruppe, also ein bijektiver Gruppenhomomorphismus der Gruppe in sich selbst.
Angewendet auf Algorithmen bedeutet dieses Konzept: Wir führen zuerst g aus, dann h, dann machen wir g rückgängig. Der Effekt des neuen Algorithmus wird der gleiche sein wie der des alten, nur wird er sich auf andere Steine auswirken.
\
\big\Bemerkungen:\normal
Zueinander konjugierte Elemente haben die gleiche Ordnung
Wozu braucht man das nun? Ganz einfach. Kennen wir bereits ein paar Züge, dann können wir durch Konjugation viele weitere sinnvolle Züge erzeugen. In der Cube Szene bezeichnet man das Konzept der Konjugation übrigens meistens mit "Setup Moves". Angenommen wir kennen einen Zug der drei Steine der oberen Ebene zyklisch vertauscht (einen sogenannten 3-Cycle, siehe oben). Mit Hilfe dieses einen einzelnen Zuges ist es uns nun bereits möglich drei beliebige Steine zu tauschen. Wir müssen die drei Steine, die wir tauschen wollen, lediglich noch per "Setup Move" in die Position bringen, von der aus wir bereits wissen, wie man die Steine tauscht. Den Algorithmus ausführen und den Setup rückgängig machen.
\
\big\Definition:\normal
Sei x,y \el\ G, dann nennt man [x,y] = x^(-1) * y^(-1) * x * y den Kommutator von x und y.
Kommutatoren sind in gewisser Weise ein Maß dafür, wie sehr zwei Elemente das Kommutativgesetz verletzen. Wenn x und y kommutieren ist der Kommutator das neutrale Element. Für den Cube sind solche Züge oft sehr nützlich, wählt man z.B. zwei "fast kommutierende" Elemente x und y dann ist [x,y] sehr oft ein Zug, der "wenig ändert" und "nützliche Auswirkungen" hat.
\
\big\Beispiel:\normal
Seien x und y zwei beliebige Basiszüge an benachbarten Seiten, dann ist:
[x,y]^2 ein Zug, der drei Kanten permutiert und keine Ecken
[x,y]^3 ein Zug, der genau zwei Paare von Ecken permutiert und keine Kanten
Die beiden Konzepte lassen sich natürlich auch kombinieren.
\
\big\Beobachtung:\normal
Kommutatoren sind verträglich mit Gruppenhomomorphismen, also insbesondere mit Konjugation. Sei g,x,y \el\ G, dann gilt:
g^(-1) * [x,y] * g = [g^(-1)*x*g, g^(-1)*y*g]
Ein paar offene Probleme Es gibt ein paar interessante Probleme für den Rubiks Cube, die bis heute ungelöst sind. - Wieviele Züge benötigt man maximal um eine beliebige Rubiks Cube Stellung zu lösen? Es existiert ein Zug (der sogenannte superflip4spot) für den es bewiesen ist, dass man (gemessen in der Quarter Turn Metrik, d.h. jede Vierteldrehung zählt einen Zug) ihn in nicht weniger als 26 Quarterturns lösen kann, d.h. 26 ist aufjedenfall eine untere Grenze, aber ist es auch die größte untere Schranke? Gibt es eventuell eine "längere" Stellung?
- Anders ausgedrückt: Wie hoch ist die Anzahl der Züge für die bestmögliche Lösung für die schlechtest mögliche Stellung? Dieses Problem ist für die meisten Puzzle ungelöst
- Finde God's Algorithm, d.h. ein Verfahren um zu jeder gegebenen Stellung effizient (!) die bestmögliche Lösung zu finden
- Enthält der Cayley Graph der Cube Gruppe einen Hamiltonkreis? Oder anders ausgedrückt: Existiert eine Zugfolge, so dass bei ihrer schrittweisen Ausführung jede mögliche Stellung exakt einmal eingenommen wird?
Ergänzung: Im Jahre 2010 wurde der Beweis erbracht, dass jede beliebige Stellung mit maximal 20 Schritten lösbar ist. Jedoch ist nicht bekannt, wieviele Stellungen exakt 20 Schritte benötigen.
Weiter Information dazu unter cube20.org
Weitere Informationen Ich hoffe, ich habe mit diesem Artikel ein kleines bisschen Interesse wecken können. Wer weitere Informationen erhalten will:
|
