Google begeht den 40. Geburtstag des Zauberwürfels heute mit einer Animation des Würfels, die man mit dem Mauszeiger “bearbeiten” kann.

Aus Mathematiker-Sicht bilden die aus Hintereinanderausführungen von Drehungen zusammengesetzten Bewegungen des Zauberwürfels eine Gruppe, die transitiv auf der Menge der möglichen Stellungen wirkt.

Die Gruppe wird per Definition von den Drehungen erzeugt.
Jede Stellung entspricht einem eindeutigen Element der Gruppe (die Wirkung ist “einfach transitiv”). Das Problem, den Rubik-Würfel in seine Ausgangslage zurückzudrehen, läßt sich also mathematisch beschreiben als die Frage, ein Gruppenelement in ein Produkt von Erzeugern zu zerlegen.

Damit hat man erstmal noch nichts für die praktische Lösung gewonnen 🙂 , es gibt aber natürlich Algorithmen, die das Problem lösen. Übrigens erst 2010 wurde von Tomas Rokicki, Herbert Kociemba, Morley Davidson und John Dethridge (mit von Google bereitgestellten Computern) bewiesen, dass man jedes Element der Gruppe in höchstens 20 Erzeuger zerlegen, also jede Stellung mit höchstens 20 Zügen lösen kann. (Das bestmögliche Ergebnis.) Einen Überblick dazu findet man auf https://www.cube20.org.

Kommentare (5)

  1. #1 rolak
    19. Mai 2014

    Ach das alte Foltergerät – es war damals das letzte Mal, daß ich einen Algorithmus auswendig gelernt habe, von dem ich nicht wußte, warum er überhaupt funktioniert…

  2. #2 schlappohr
    19. Mai 2014

    Wenn ich die cube20-Seite richtig verstehe, dann haben Rokicki et. al. mit einer Brute-Force-Methode versucht, aus jeder Stellung eine Lösung mit maximal 20 Drehungen zu finden – und haben sie gefunden. Wobei die Abschätzung 20 schon vorher existiert hat.
    Für ein endliches Problem ist das natürlich ein legitimer Weg (probier einfach alles aus), aber ich habe immer ein bisschen Bauchscherzen, so etwas einen Beweis zu nennen. Es ist eine Lösung für ein spezifisches Problem. Für einen 4^3- oder einen 3^n-Cube hlift uns das aber vermutlich nicht weiter.
    Das bedeutet nicht, dass ich die Arbeit abwerten will. Es ist ein himmelweiter Unterschied, zu beweisen, dass eine Lösung für ein Problem existiert, und ein Verfahren zu entwickeln, das diese Lösung findet.

  3. #3 miniwolf
    19. Mai 2014
  4. #4 Thilo
    20. Mai 2014

    Ich dachte erst, das wäre das neue Doodle für heute.

  5. #5 Swanhild Bernstein
    21. Mai 2014

    Einfach “brute force” ist falsch, schliesslich musste die riesige Zahl der Möglichkeiten auf eine handbabbare Zahl heruntergebrochen werden und dazu wurden Gruppeneigenschaften ausgenutzt. Ansonsten ist es bei graphentheoretischen oder kombinatorischen Problemen oftmals so, dass schon kleine endliche Zahlen zu vielen einzelnen Lösungen führen, die alle einzeln abgearbeitet werden müssen. Eine schöne “Weltenformel” gibt es da selten.