Neuer Algorithmus löst beliebig große Zauberwürfel

Erik Demaine, ein Informatiker am renommierten Forschungsinstitut MIT in Boston, ist es gelungen, einen Algorithmus zu entwickeln, mit dem Zauberwürfel einer beliebigen Größe mit einer vorhersagbaren Zahl an Zügen gelöst werden können. Das berichtete das Wissenschaftsmagazin 'New Scientist'. Das Problem liegt darin, in dem Computer-Programm eine Strategie umzusetzen, die nicht auf dem Zufallsprinzip beruht. Einen herkömmlichen Zauberwürfel mit 3 x 3 x 3 Feldern kann man durchaus noch lösen, in dem man alle denkbaren Züge durchprobiert. Schon dies erfordert eine größere Rechenleistung. Allerdings geht dies nicht bei größeren Würfeln.

Bei der Suche nach einem effizienteren Weg konzentrierte sich der Forscher erst auf die Wege, die einzelne Felder nehmen. Dies erwies sich jedoch als nicht zielführend. Statt dessen ging man dazu über, die Wege der einzelnen Felder bei der Drehung des Würfels zu parallelisieren und so Gruppen von Feldern mit ähnlichen Wegen gleichzeitig betrachten zu können.

Letztlich fand Demaine so eine Formel, mit der sich die Zahl der maximal benötigten Züge zur Lösung eines beliebig gemischten Zauberwürfels etwa auf die Formel n^2/log n reduzieren lässt. Allerdings ist damit für Demaine die Arbeit noch nicht erledigt, sondern er hat sich schon das nächste Ziel gesetzt.

Diesmal geht es um Zauberwürfel, die geordnet waren und nur mit einer kleinen Zahl von Zügen geringfügig gemischt wurden. "Angenommen jemand nimmt einen Zauberwürfel mit 20 x 20 x 20 Feldern und macht fünf Züge - können sie herausfinden, welche das waren?", so Demaine. Ziel ist es also einen Algorithmus zu finden, der möglichst effizient genau diese fünf Züge nachvollziehbar macht.

Den letzten großen Durchbruch in der "Zauberwürfel-Forschung" machte im vergangenen Jahr der US-Informatiker Tomas Rokicki. Mit dem in der Szene "Gottes-Algorithmus" genannten Beweis konnte er belegen, dass sich ein herkömmlicher Zauberwürfel aus jeder Variation heraus mit maximal 20 Zügen lösen lässt, es aber Anordnungen gibt, von denen aus man auf keinen Fall mit weniger Zügen zum Ziel kommt. Farben, Zauberwürfel, Rubik's Cube Steve Rhodes / Flickr