God's Number: Wie viele Züge braucht es maximal, um jeden Zauberwürfel zu lösen?
Wir tauchen in die Welt der Zauberwürfel ein und erzählen, wie die Mathematiker es letztlich geschafft haben, das Problem zu lösen.
Ein verdrehter Zauberwürfel sieht auf den ersten Blick wie eine unlösbare Aufgabe aus. Jede Bewegung einer Ebene orientiert die Teile eines Würfels neu und verschiebt dafür andere. Schon nach wenigen Verdrehungen verliert man den Überblick. Die schiere Anzahl an möglichen Kombinationen motivierte Mathematiker, den Rubik's Cube zu erforschen und sich folgende Frage auszudenken: Angenommen, Gott ist in der Lage, jeden Zustand eines Würfels immer perfekt zu lösen. Wie viele Bewegungen der Ebenen bräuchte er maximal, um jeden beliebigen Zustand des Zauberwürfels lösen zu können? Die Zahl tauften die Mathematiker "God's Number".
Während Speedcuber den Würfel in der kürzesten Zeit lösen wollten, interessierte Mathematiker die theoretische Version der Frage. Wie viele Drehungen reichen, wenn Gott keine Fehler macht? Was sie damals noch nicht wussten: Die Suche nach God's Number entpuppte sich als überhaupt nicht trivial und beschäftigte Mathematiker rund um die Welt 30 Jahre lang. Erst 2010 fanden Tomas Rokicki, Herbert Kociemba und Morley Davidson endlich die Lösung.
Der Begriff God's Number oder auch Gottes Algorithmus wurde zwar für den Zauberwürfel geprägt, tritt aber auch in anderen Spielen und Puzzles auf, wenn eine kleinstmögliche optimale Lösung vorhanden ist. Beim Schach zum Beispiel gibt es die sogenannten Tablebases: Alle möglichen Positionen mit sieben Figuren oder weniger sind gelöst. Es gibt also für alle diese Fälle eine optimale Lösung, die entweder zum Sieg, zum Unentschieden oder zur unweigerlichen Niederlage führt. Wer jetzt glaubt, seine Freunde im Endspiel in Grund und Boden spielen zu können, sollte Platz auf seinem Rechner schaffen, denn die Tablebases umfassen mehr als 16 TByte an Festplattenspeicher. Doch das ist gar nichts im Unterschied zu der möglichen Anzahl an Zuständen, die ein Zauberwürfel annehmen kann.
Das war die Leseprobe unseres heise-Plus-Artikels "God's Number: Wie viele Züge braucht es maximal, um jeden Zauberwürfel zu lösen?". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.Immer mehr Wissen. Das digitale Abo für IT und Technik.
Bequemer zum Ziel: Tipps zum Umgang mit Windows-Pfadangaben
Outdoor-Kamera mit Raspberry Pi und wasserfestem Gehäuse im Eigenbau
Test VW ID.3 GTX Performance: Endlich gereift
Sensible Daten durch Passworttresore besser schützen
Starlink v3 im Test: Das leistet das Satelliten-Netzwerk