Aufgabe: Algorithmus eines Zauberwürfels

[Lefko]

Wikipedia:

Man kann den Zauberwürfel auch mit verbundenen Augen lösen. Zu diesem Zweck bekommt man zuerst Zeit, sich den verdrehten Würfel einzuprägen. Der amerikanische Student Leyan Lo stellte in dieser Disziplin im Jahre 2006 mit 1 min 28,82 sec einen neuen Weltrekord auf

[alzaimar]

Zauberwürfel: Es gibt ca. 8 Operationen, um bestimmte Teilaufgaben zu lösen. Dazu gehören:
1. Alle 8 Ecken in die richtige Position bringen
2. Obere und untere Fläche fertigstellen
3. Die Mitte fertigstellen
Meist sind jetzt 2 Steine vertauscht. Die bekommt man mit 8*3 Drehungen umgedreht-
4.Fertig.

Das o.g. ist nur eine von vielen Möglichkeiten. Ich hab das früher in so ca. 40 Sekunden geschafft. Wie gesagt, keine Kunst, wenn man die Operationen geübt hat.

Mit ein wenig Übung schafft das Jeder ohne Gichtproblemen in den Händen. Als Algorithmus eine nette Aufgabe, mehr aber auch nicht.

[gordon freeman]

Hier wird beschrieben, wie ein Lösungsweg funktioniert. Ich habe mich auf einer Mathematik-Informatik-Akademie mal mit einem aktiven Spped-Cuber unterhalten und der sagt, es gibt für alles Algorithmen. Alle diese Algorithmen basieren letztendlich auf dem Tausch von 2 Farbflächen. Wenn du dafür einen Algorithmus hast musst du ihn nur entsprechend oft anwenden, um den Würfel zu sortieren. Ich frag ihn mal, ob er mir dazu einschlägige Seiten sagen kann ....

[Corpsman]

Ho ich habe das gemacht, ist im Prinzip total easy

Link zum Programm

[Cöster]

@ Corpsman: cooles Teil, aber berechnet das auch die schnellst mögliche Lösung?
Die einzige Möglichkeit, die Lösung mit den wenigsten Drehungen zu finden, ist wohl die Brute-Force-Methode. Einfach alle Möglichkeiten durchspielen.
Es gibt, wie hier schon gesagt wurde, zu jedem Zug 18 mögliche Drehungen. Ich behaupte mal, dass selbst die schlechteste Positionierung mit weniger als 50 Drehungen gelöst werden kann. Das heißt es gibt 18^50 verschiedene Wege.
Der erste Weg wäre, 50 mal die gleiche Drehung zu machen, der zweite wäre 49 mal die gleiche Drehung wie beim ersten zu machen und als 50ten Zug dann einen anderen Weg zu gehen. Diese 18^50 verschiedene Wege müssten alle nacheinander durchgespielt würden.
Stimmt, braucht Monate bis da ne Lösung gefunden würde.

Aber das alles könnte man ja ein bisschen vereinfachen und an vielen Ecken und Kanten einschränken, sodass man die Anzahl der Wege verringert.

• Man darf nie nach einem Zug den entgegengesetzten ausführen, womit wir schonmal bei 17^50 wären.
• Es darf nie über 2mal hintereinander die gleiche Drehung durchgeführt werden (denn wenn man dreimal in Richtung x dreht gelangt man zum gleichen Ergebnis wie wenn man einmal in die entgegengesetzte Richtung dreht). Dadurch fallen unglaublich viele Züge weg.
• Nur für die Drehungen 1-9 ist erlaubt, zweimal hintereinander durchgeführt zu werden. Wenn man Drehung 10 nämlich 2mal hintereinander ausführt, erhält man das gleiche Ergebnis wie wenn man Drehung 1 zweimal durchführt (wenn 10 die Gegendrehung zu 1 ist).
• Wenn eine Lösung mit weniger als 50 Drehungen gefunden wurde, kann für die nächsten Berechnungen die Rechentiefe vermindert werden.

Ich kann nicht genau abschätzen, wie viele mögliche Zug-Folgen dann noch übrig blieben, die berechnet werden müssen.
Vielleicht ist mein Lösungsansatz Bullshit, weil er zwar nicht Monate, dafür aber Tage braucht. War nur so meine spontane Idee.
Es wird aber nicht übermäßig viel Speicher belegt. Was gespeichert werden muss:

• Ausgangslage
• aktuelle Lage (nur die aktuelle, die vorherigen können vergessen werden. Es muss anhand der Lösungsnummer möglich sein, genau diesen Zug nachstellen zu können)
• Lösungsnummer des Zuges, der von den bisher berechneten das schnellste Ergebnis liefert und die Anzahl der dafür benötigten Züge

[dino]

wie redet ihr hier über den Zauberwürfel???
ich hatte früher(ok sehr viel früher) so einen und hab stunden versucht ihn wieder zurückzukriegen aber nie wieder geschafft

bei *Simpsons* hat er in der Folge, wo *Flanders* durchdreht auch mal kurz für verwirrung unter den *Simpsons* gesorgt

[Cöster]

@ Dino:
Ging mir nicht anders, bis ich irgendwann mal auf diese Seite gestoßen bin

[dino]

den zauberwürfel hab ich damals verflucht und zerstört, sonst würde ich jetzt dazu verführt sein die seite auszuprobieren

[Corpsman]

@Cöster :

Du hast nicht ganz unrecht, es gibt soviel ich weis sogar einen Beweis das man nicht sehr viele Drehungen braucht , ich meine es waren sogar unter 30.

Die Brute Force habe ich auch mal getestet. Selbst wenn man das mit einer Heuristischen Variante Koppelt geht es nicht.

Das heist es geht schon. Aber mein Algo hat es nur geschafft wenn weniger oder 6 drehungen notwendig waren, d.h 18^6 Möglichkeiten ( unoptimiert ).

Sobald ich den Würfel mehr Verdreht habe ist die Rechenzeit derartig explodiert das nichts mehr ging. Zusätzlich mus man ja noch speichern wie man auf die Lösung kommt. Das hat mein 1 GB RAM Speicher dannn auch noch zerlegt.

[Phoenix]

Zitat von Seniman:

Edit: Falls jemand wissen will, wie so ein Rubikwürfel von innen aussieht: Man kann diese Teile ganz einfach auseinanderbauen (und hinterher wieder zusammen). Einfach eine Ebene um etwa 30° drehen und dann eine andere dagegendrehen. Man muss ein wenig Kraft anwenden, aber das klappt. Das ist dann auch gleichzeitig, die Methode für Verzweifelte: Würfelauseinandernehmen und geordnet wieder zusammensetzen. Klappt zwar nicht in 30 sek, aber bestimmt in 5 Minuten.

Hey, verrat doch nicht wie ich die damals immer meine Würfel gelöst hab. Ich hab immer jemanden gesagt er soll die verdrehen, hab mich dann damit 5 Minuten aufs Klo verdrückt ('Da kann ich besser Denken...') und WUPPDI - war er gelöst

Es gibt inzwischen u.a. schon einen Lego-Roboter, der die Lösen kann. Der Link dazu war irgendwann mal bei Userfriendly.org als Link of the Day promoted. Da hat einer so eine Halterung für den Würfel gebaut und einen Roboterarm der den ganzen würfel bzw. die einzelnen Seiten drehen und per Webcam fotografieren konnt. Der hat halt ne Weile gebraucht, ging aber komplett vollautomatisch.