Von Heinrich Hemme
07. Mai 2008 Schneller als ein Grippevirus hat sich Anfang der achtziger Jahre des vergangenen Jahrhunderts eine besondere Spielsucht um die ganze Welt verbreitet, ein Knobelspiel, das sich um den sogenannten Zauberwürfel drehte. Diesen Zauberwürfel hatte der ungarische Bauingenieur Ernö Rubik im Jahr 1974 erfunden. Er besteht aus drei mal drei mal drei zusammenhängenden bunten Würfeln, die sich schichtweise in jeder Ebene gegeneinander verdrehen lassen. Dadurch werden die einzelnen Würfel des Spiels umgeordnet.
Es ist nun die Aufgabe, die ursprüngliche Anordnung wiederherzustellen, ein Problem, das verblüffend schwer zu lösen ist. Vielleicht gerade deshalb trat Rubiks Würfel damals seinen Siegeszug an. Wo man auch war, in Klassenzimmern oder Hörsälen, in Büros oder Werkstätten, in Wohnzimmern, Kneipen oder Eisenbahnen, überall saßen Menschen und drehten konzentriert den Zauberwürfel in ihren Händen. Mitte der achtziger Jahre, als bereits über 100 Millionen Exemplare des Zauberwürfels verkauft worden waren, klang die Epidemie genauso schnell wieder ab, wie sie entstanden war.
Mehr als ein Spielzeug
Für die Mathematiker ist der Zauberwürfel nicht nur ein Spielzeug, sondern auch eine Quelle schwieriger gruppentheoretischer Probleme, die zum Teil noch immer ungelöst sind. Sie interessieren sich dafür, wie groß, mathematisch gesprochen, „Gottes Zahl“ ist – die Anzahl der Züge, die man bei richtiger Strategie maximal dazu benötigt, Rubiks Zauberwürfel aus jeder beliebigen Stellung in seine Ausgangslage zurückzudrehen. Im April ist Tomas Rokicki aus Palo Alto (Kalifornien) der Beweis gelungen, dass sie höchstens 23 sein kann.
Die siebenundzwanzig Würfel des Zauberwürfels können auf über 43 Trillionen unterschiedliche Weisen angeordnet werden. Zählt man alle Stellungen, die man durch eine räumliche Drehung oder Spiegelung des Zauberwürfels ineinander überführen kann, als gleich, so reduziert sich diese gigantische neunzehnstellige Zahl auf 901 Billiarden Anordnungen. Will man für eine beliebige Stellung des Zauberwürfels durch systematische Berechnung die kürzeste Zugfolge finden, mit der sich dieser in seine Ausgangsstellung zurückdrehen lässt, muss man einen der heutigen Computer im Schnitt etwa eine Viertelstunde lang arbeiten lassen. Das bedeutet, für die Berechnung der jeweils kürzesten Zugfolge aller 901 Billiarden Anordnungen müssten fünf Millionen Computer über fünf Millionen Jahre lang rechnen, was natürlich ein Ding der Unmöglichkeit ist. Also mussten die Mathematiker nach anderen Wegen suchen, Gottes Zahl zu finden.
Erste Eingrenzung
Die Wissenschaftler näherten sich der Lösung des Problems von zwei Seiten. Um 1980 konnte bereits durch kombinatorische Überlegungen bewiesen werden, dass es Würfelstellungen geben muss, für die man mindestens achtzehn Züge zum Zurückdrehen benötigt. 1982 haben Alexander H. Frey von IBM in Washington und David Singmaster von der South Bank University in London gezeigt, dass man jede beliebige Würfelstellung mit höchstens 52 Zügen lösen kann. Damit war Gottes Zahl auf den Bereich von 18 bis 52 eingegrenzt.
Dreizehn Jahre später ist es Michael Reid von der University of Central Florida in Orlando gelungen, diesen Zahlenbereich auf 20 bis 29 einzuengen. Silviu Radu von der Johannes-Kepler-Universität in Linz hat die Obergrenze 2005 auf 27 gesenkt, und Daniel Kunkle und Gene Cooperman von der Northeastern University in Boston konnten sie 2007 sogar auf 26 drücken.
Idee aus Darmstadt
Für seine eigenen Arbeiten hat Rokicki ein Verfahren verfeinert, das der Darmstädter Mathematiklehrer Herbert Kociemba bereits 1992 entwickelt hat. Dabei begnügt man sich im ersten Schritt, den Würfel in eine von etwa 20 Milliarden speziellen Zwischenstellungen zu drehen, die eine Untergruppe der Würfelgruppe bilden. Dazu sind nicht mehr als zwölf Züge notwendig. Im zweiten Schritt wird dann der Würfel mit höchstens 18 Drehungen aus diesen Zwischenstellungen in den Ausgangszustand gebracht. Für beide Schritte zusammen beträgt die Obergrenze also, wie seit längerem bekannt ist, 30 Züge.
Den zweiten Schritt des Verfahrens – hin zum Ausgangspunkt – hat Rokicki nun gleichzeitig auf etwa 20 Milliarden Würfelstellungen angewendet, aber nicht in Kociembas Untergruppe, sondern in eine Nebenklasse davon. Mit seinem Computer dauerte es nur ungefähr 18 Minuten, für einen solchen Satz von Stellungen zu zeigen, dass sie alle in zwanzig Zügen – statt in 18 wie bei Kociembas Untergruppe – zu lösen sind. Von solchen Nebenklassen gibt es wiederum ungefähr 140 Millionen verschiedene.
Fast acht Jahre Rechenzeit
Rokicki benutzte nun eine intelligente Auswahl von nur 200.000 Nebenklassen mit der Eigenschaft, dass man von jeder beliebigen Würfelstellung in höchstens drei Zügen eine dieser Nebenklassen erreichen kann. Er benötigte dafür 7,8 Jahre Rechenzeit am Computer. Da er für alle Würfelstellungen dieser Nebenklassen zeigen konnte, dass sie maximal zwanzig Züge benötigen, hatte er somit bewiesen, dass 23 Züge für jede beliebige Würfelstellung ausreichen.
Man kennt heute über eine Million Würfelstellungen, für die man zwanzig Züge zur Lösung benötigt, und keine einzige, für die mehr als zwanzig Züge notwendig sind. Die meisten Fachleute vermuten, dass 20 tatsächlich Gottes Zahl ist, aber ein Beweis steht noch aus.
Text: F.A.Z.
Bildmaterial: ASSOCIATED PRESS
