RIESIGE ZAUBERWÜRFEL: EINE KONSTANTE VON 10⁴⁰ AUF 30,5 GESENKT
Der Zauberwürfel, der gerade 50 Jahre alt geworden ist, ist vielleicht das bekannteste Geduldsspiel der Welt, und eine seiner zentralen Fragen ist einfach zu formulieren: Wie viele Züge braucht man im schlimmsten Fall, um ihn zu lösen? Für den klassischen 3×3×3-Würfel ist die Antwort genau bekannt: 20 Züge, ein Ergebnis, das 2014 ein Team veröffentlichte, zu dem Tomas Rokicki gehörte; Rokicki zählt auch zum Autorenteam dieser neuen Arbeit.
Für größere Würfel mit n Schichten entlang jeder Kante ist die genaue Antwort außer Reichweite – einen gegebenen n×n×n-Würfel optimal zu lösen, ist sogar NP-vollständig. Doch 2011 zeigten Erik Demaine und Kollegen, wie der schlimmste Fall wächst: proportional zu n² / lg n, wobei lg der Logarithmus zur Basis 2 ist. Das ist um einen logarithmischen Faktor besser als Standardmethoden, die die Teile im Wesentlichen eines nach dem anderen lösen.
Ein Beweis mit einer absurden Konstante
Es gab einen Haken. Das Ergebnis von 2011 garantierte die Wachstumsrate, nicht die Zahl davor. Beim Durcharbeiten dieses Algorithmus stellen die Autoren fest, dass seine Konstante etwa 1,01 × 10⁴⁰ beträgt. Schuld ist eine Computerprüfung, die bewies, dass bestimmte Züge jede Anordnung einer Gruppe von 24 Teilen erreichen können, ohne zu sagen, wie schnell. Die einzige sichere Schranke für diese Länge war die Größe dieser Gruppe von Anordnungen, etwa 3,1 × 10²³ Schritte, und die Formel verwendet am Ende an zwei Stellen die riesige Zahl 24! (1 × 2 × … × 24, etwa 6,2 × 10²³). Die untere Schranke dagegen – die Zahl der Züge, die fast jeder verdrehte Würfel braucht – hat eine bescheidene Konstante von etwa 12,88. Viele in der Community glaubten deshalb, ein solcher Algorithmus könne für vernünftige Größen nie praktikabel sein.
Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf und Erik Demaine vom MIT, von der TU München und aus Palo Alto haben diese Konstante nun explizit und klein gemacht.
Sortiernetzwerke für Würfelteile
Auf einem großen Würfel dominieren die Mittelteile: Ihre Zahl wächst wie n², während Ecken und Kanten nur Terme proportional zu n beisteuern. Die Mittelteile zerfallen in Familien von 24, die nur untereinander die Plätze tauschen können. Das Grundwerkzeug ist der Kommutator, eine Zugfolge der Form A B A′ B′, die fast alles an Ort und Stelle lässt und nur drei Teile einer Familie vertauscht. Das Team fand Zugfolgen für alle 4.000 nutzbaren Dreiervertauschungen, jede höchstens 12 Züge lang.
Zwei Ideen lassen die Zahl sinken. Erstens kann derselbe Kommutator auf viele Familien gleichzeitig angewandt werden, über ganze Gruppen von Reihen und Spalten hinweg. Zweitens wird nicht jede Familie für sich gelöst: Alle Familien folgen einer einzigen festen universellen Folge von Vertauschungen und überspringen einfach diejenigen, die sie nicht brauchen. Ein Lemma verbindet alles: Eine universelle Folge aus L Stufen ergibt eine führende Konstante von L/2.
Um diese Folge zu verkürzen, borgt das Team Werkzeuge der Informatik: Sortiernetzwerke, feste Muster von Vergleichen, die jede Eingabe sortieren. Ein optimales Sortiernetzwerk für sechs Eingaben liefert 96 Stufen, also eine Konstante von 48. Netzwerke, die die 24 Positionen in Gruppen von 12, dann 4 aufteilen und per Computersuche gefunden wurden, bringen sie auf 72 Stufen (36). Erlaubt man schließlich Züge, die mehr als drei Teile auf einmal durchmischen, und teilt die Positionen anders auf, kommt man auf 61 Stufen.
Dreißig Komma fünf
Das Theorem: Jeder n×n×n-Würfel lässt sich in höchstens 30,5 n²/lg n Zügen lösen, plus Terme, die für großes n vernachlässigbar werden. Die Konstante verbessert sich um einen Faktor von mehr als 3,30 × 10³⁸ und liegt höchstens um den Faktor 2,37 über der unteren Schranke (30,5 / 12,88). Für die flache n×n×1-Version, die zum Aufwärmen dient, sinkt die Konstante von 12 oder 18 auf 1,5.

Acht gleichmäßig verteilte Bilder aus der Lösung eines Würfels mit 256 Schichten pro Seite: Die verdrehten Seiten werden zu einfarbigen Flächen. — Abbildung 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.
Der Algorithmus läuft in einer Zeit proportional zur Zahl der Teile, und die Autoren stellen einen Open-Source-Löser bereit, mit Skripten, die jedes Netzwerk, auf das er sich stützt, erschöpfend prüfen. Ihr eigener Vergleich sieht ihn ab etwa n = 840 vor bestehenden Lösern; sie haben Lösungen von Würfeln mit 256 und 65.536 Schichten pro Seite gerendert.
Die 2,37 ist eine asymptotische Aussage: Die kleineren Terme der Formel sind nicht genau bestimmt, also liefert sie keine exakte Zugzahl für einen bestimmten Würfel. Künftige Fortschritte, so die Autoren, könnten aus anderen Arten entstehen, Teile in Sortiernetzwerken zu gruppieren, und aus besseren Dreiervertauschungen – und dieselbe Maschinerie könnte andere riesige Geduldsspiele angehen, oder vier- und fünfdimensionale Hyperwürfel.
