Zauberwürfel: Informatiker beweist Lösung jeder Ausgangsposition innerhalb von 20 Zügen

"Gottes-Algorithmus" für Zauberwürfel20 Züge reichen zum Lösen
Mit maximal 20 Zügen kann der Zauberwürfel aus jeder beliebigen Position in seine Ausgangslage gebracht werden. Das kann Tomas Rokicki nun beweisen. Der US-Informatiker greift bei den Berechnungen auf Datenzentren von Google zurück.

Der so genannte "Gottes Algorithmus" zur Lösung eines Zauberwürfels ist gefunden. Er konnte durch den US-Informatiker Tomas Rokicki mit Unterstützung des Suchmaschinenkonzerns Google bewiesen werden.

Der Informatiker Rokicki befasst sich schon länger mit der Mathematik des Zauberwürfels. Im August 2008 konnte er bereits beweisen, dass sich die farbigen Felder aus jeder beliebigen Position mit maximal 25 Zügen wieder ordnen lassen. Kürzlich wurde der Algorithmus von ihm auf maximal 22 Züge verbessert.

Jetzt gelang Rokicki in Zusammenarbeit mit seinen Unterstützern Morley Davidson, John Dethridge und Herbert Kociemba der Nachweis, dass aus jeder beliebigen Position maximal 20 Züge benötigt werden, es aber auch bestimmte Anordnungen gibt, die keinesfalls schneller zu lösen sind.

Freie Rechenzeiten von Google

Um den entsprechenden Beweis erbringen zu können, benötigte Rokicki eine gewaltige Rechenleistung. Nach Angaben der Projektgruppe hätte ein moderner PC mit einem vierkernigen Intel Nehalem-Prozessor mit 2,8 Gigahertz rund 35 Jahre benötigt, um die notwendigen Berechnungen durchzuführen.

Unterstützung erhielt die Gruppe daher von Google. Der Konzern stellte freie Rechenzeit in seinen Datenzentren zur Verfügung. Dadurch wurden letztlich nur wenige Wochen benötigt, hieß es.