Rubiks Zauberwürfel, ein Solitärspiel aus den 80ern, ist ein beliebtes Studienobjekt für Forscher mit viel Tagesfreizeit. Ein US-Mathematiker weist nun nach: Man braucht höchstens 25 Züge, dann ist der Würfel komplett.
Sechs Seiten, sechs Farben
Für alle, die sich in den 80ern nicht für den Zauberwürfel interessiert haben - bzw. zu spät geboren wurden, um den Hype um das vom Ungarn Ernö Rubik entwickelte Spielzeug erlebt zu haben: Dabei handelt es sich um einen Würfel, dessen sechs Seitenflächen aus jeweils neun farbigen Quadraten bestehen. Ziel des Spiels ist es, die Quadrate so anzuordnen, sodass jede Seitenfläche des Würfels einfarbig ist.
Das ist für den Normalverbraucher schon eine recht anspruchsvolle Aufgabe, die ganze Nachmittage in Anspruch nehmen kann, sofern man nicht überhaupt scheitert. Echte Meister des "Speedcubing" schaffen das hingegen in zehn Sekunden und weniger (siehe Video).
Die Lösung von unten suchen
Abgesehen von den Tugenden Schnelligkeit und Geschicklichkeit kann man sich dem Thema auch von der abstrakten Seite nähern. Die große Frage der Zauberwürfelforschung lautet nämlich: Wie viele Züge braucht man im schlechtesten Fall, um den Zauberwürfel zu komplettieren? Die Antwort ist unbekannt. Doch obwohl es noch immer keinen entsprechenden Beweis gibt, kann man die Lösung mittlerweile ganz gut eingrenzen.
Zu diesem Zweck verfolgen Rubikologen in der Regel zwei Strategien. Die einen betrachten die Sache gewissermaßen vom Kellergeschoß aus, d.h. sie versuchen zu zeigen, wie viele Züge man mindestens benötigt. Etwa, indem man zunächst die Anzahl der möglichen Würfelpositionen ausrechnet (rund 4,32 mal 1019, also sehr viele) und sich dann ansieht, wie viele Positionen durch eine gegebene Zahl von Zügen erzeugt werden können.
Die Anzahl der Positionen bei 17 Zügen ist etwa deutlich kleiner als die Maximalzahl (4,32 mal ...), es gibt offenbar Positionen, die auch mit einem 17-Züge-Manöver nicht zu erreichen sind. Daraus folgt: Es sind mindestens 18 Züge nötig.
Mindestens 20 Züge bis zum Ziel
Superflip
Man kann auch bei einer besonders kniffeligen Position starten und dann nach einer möglichst ökonomischen Lösung suchen. Recht viel Arbeit macht beispielsweise die Superflip-Position (Bild rechts): Bei ihr stehen die vier Ecksteine alle an der richtigen Stelle, nur die vier Kantensteine sind verkehrt orientiert.
1992 fand der Niederländer Dik T. Winter eine Lösung mit 20 Zügen, drei Jahre später bewies Michael Reid aus den USA, dass das tatsächlich die minimale Lösung ist. Mit anderen Worten: Man braucht 20 Züge um den Zauberwürfel zu finalisieren - oder mehr.
Den Plafond auf 25 senken
Genau umgekehrt agieren jene Mathematiker, die plafondseitig arbeiten. Sie wollen nicht - wie eben - die Untergrenze anheben, sondern die Obergrenze nach unten drücken. Damit man sich nicht durch die unhandliche 20-stellige Zahl möglicher Positionen ackern muss, bietet sich das Number-Crunching per Computer mit einem klugen Algorithmus an. Letzterer zerlegt das Problem in Teilprobleme und sucht nach möglichen Abkürzungen im Lösungsraum.
Auf diese Weise hat man das Rubik-Maximum in den letzten Jahren scheibchenweise abgetragen. In den 90ern lag es zunächst bei 40 Zügen, 2006 fiel es auf 27, ein Jahr später betrug es nur mehr 26. Im März dieses Jahres meldete der US-Mathematiker Tomas Rokicki auf dem Preprintserver "arXiv" (0803.3435) einen neuen Rekord: 25 Züge, errechnet mit einem 1,6-GHz-Prozessor, der für diese Lösung satte 1.500 Stunden benötigte.
Mit Sonys Hilfe: Vermutlich 23
Die Rechenzeit für neue Rekorde hätte wohl Monate oder sogar Jahre in Anspruch genommen. In der Zwischenzeit ist allerdings die Firma Sony Pictures Imageworks an Rokicki herangetreten und hat ihm jene Superrechner zur Verfügung gestellt, auf denen etwa "Spiderman 3" entstanden ist.
Damit ging nun alles ganz schnell: Laut Auskunft von Rokicki wurden mittlerweile die Hürden 24 und 23 genommen, derzeit laufen die Prozessoren am Projekt 22 heiß. Offiziell sind die neuen Rekorde mangels entsprechender Publikationen noch nicht, aber wenn die 25er-Berechnung wasserdicht war, dann werden es die neuen auch sein, die Methode ist nämlich die gleiche. Und wann ist endgültig Schluss mit der Rekordrechnerei? Die pragmatische Antwort: spätestens bei 20. Die exakte Antwort will wie gesagt noch gefunden werden.
