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

Farben, Zauberwürfel, Rubik's Cube Bildquelle: Steve Rhodes / Flickr
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 Farben, Zauberwürfel, Rubik's Cube Steve Rhodes / Flickr
Diese Nachricht empfehlen
Kommentieren66
Jetzt einen Kommentar schreiben


Alle Kommentare zu dieser News anzeigen
Kommentar abgeben Netiquette beachten!

Jetzt als Amazon Blitzangebot

Ab 18:30 Uhr Sony 5.1-Kanal Soundbar mit 600W Ausgangsleistung, NFC
Sony 5.1-Kanal Soundbar mit 600W Ausgangsleistung, NFC
Original Amazon-Preis
205,25
Im Preisvergleich ab
205,24
Blitzangebot-Preis
179,00
Ersparnis zu Amazon 13% oder 26,25

Video-Empfehlungen

WinFuture Mobil

WinFuture.mbo QR-Code Auch Unterwegs bestens informiert!
Nachrichten und Kommentare auf
dem Smartphone lesen.

Folgt uns auf Twitter

WinFuture bei Twitter

Interessante Artikel & Testberichte

WinFuture wird gehostet von Artfiles

Tipp einsenden