2x2x2 Rubiks Cube lösen
-
Hallo zusammen,
ich überlege mir gerade, wie man einen 2x2x2 Rubiks cube mit einem möglichst einfachen algorithmus in nicht allzulanger Zeit (höchstens ein paar Minuten) in Möglichst wenig Schritten lösen kann.
Bei Wikipedia steht, dass jede Anordnung in maximal 11 Zügen gelöst werden kann.
In jeder Stellung gibt es 12 verschiedene mögliche Züge.Ich habe mir als erstes überlegt es einfach mit backtracking zu lösen:
Man fängt am anfang an, ruft nacheinander rekursiv für jeden der 12 Züge sich selbst auf und sobald rekursionsschritt 11 zuende ist hat man entweder etwas gefunden und bricht ab, oder lässt die rekursion weiterlaufen (nicht mehr weiter in die tiefe, sondern beim nächsten "strang" weiter).Allerdings gibt es da ein Problem:
12^11 = 743 008 370 688
Selbst wenn man als optimierung reinmacht, dass niemals der gerade gemacht Zug im folgezug rückgängig gemacht wird wären es immer noch
11^11 = 285 311 670 611 Funktionsaufrufe.
Bei einer Taktrate von 2-3 Gigaherz muss das lange dauern.Meine zweite Idee war den Würfel als 8 Teile zu betrachten und eine Datenstruktur zu basteln, die jede Mögliche Anordnung der 8 Teile fasst.
Das ergibt dann 11.022.480 Anordnungen (oder 3.674.160, wenn man nur die mechanisch möglichen beachtet). Dann könnte man nach dem Dijkstra algorithmus suchen. Ich bezweifle aber das das viel schneller sein wird als die erste Möglichkeit, bei einer Datenstruktur mit 11 Millionen elementen).Habt ihr sonst noch Ideen?
Ich weiß das es im internet einige algorithmen gibt, aber ich suche etwas möglichst einfaches und wollte am liebsten selbst auf eine Lösung kommen. Ein paar Denkanstöße würden evtl. schon reichen.
-
Ich verstehe nicht, wie du auf 11^11 kommst. Ich habe bei jedem Zug 3 Drehrichtungen und 2 moegliche Richtungen, also fuer 11 Zuege ergeben sich 6^11 Moeglichkeiten. Das zuruecknehmen des Zuges entfaellt, also 5^11.
-
Du hast 8 Klötze:
Drehen kannst du dann:
-Die vorderen 4 Klötze um 90 grad, -90 grad, 180 grad seitwärts
-Die hinteren 4 Klötze um 90 grad, -90 grad, 180 grad seitwärts
-die linken 4 klötze um 90 grad, -90 grad, 180 grad "in die tiefe"
-die rechten 4 klötze um 90 grad, -90 grad, 180 grad "in die tiefe"Macht 12 Züge
-
'180 grad seitwärts' sehe ich nicht als Zug an, da er aus 2 Drehungen zusammengesetzt ist.
-
Bei wikipedia stand das 180 grad auch als zug zählt, wird unter profis dann wohl so gehandhabt
-
Dann nimm 14 'quarter turns' ... Der Suchraum ist fuer heutige Massstaebe verschwindend gering.
-
Kannst du das mit quarter-turns bitte noch ein bischen ausführen? Google und Wiki haben mir auf anhieb nix gutes geliefert.
Edit: Weiß immer noch nicht was du meintest, aber mir ist noch ne andere idee gekommen:
Es gibt ja die 4 Achsen an denen man jeweils 3 änderungen pro rekursionsschritt macht. In dem darauffolgenden schritt braucht diese achsen icht mehr beachtet zu werden, weil diese Möglichkeiten sowieso schon abgedeckt werden.
Aus 12^11 sollte das dann 12 * 9^10 = 41 841 412 812 machen, also immer noch jede menge.
-
-
Du sollst nur Bruteforschen, wenn Du Gods Algorithm brechen willst.
Sonst nimm http://www.youtube.com/watch?v=q4p7ZelNGkg
Haha, verarscht.
Hier wirds kool.
http://rubikscube.info/ortega.phpDie Jungs vor mir haben recht, mit einem I7 und klassischen Optimierungen kannste wohl auch den 2x2x2 schnell lösen, ohne vorher nachzuschauen.
-
Ah ok jetzt weiß ich was du meinst.
Wären das dann nicht trotzdem 8^14 Schritte nach dem backtracking-verfahren (was mehr sind als 12^11)?
-
Q schrieb:
Du hast 8 Klötze:
Drehen kannst du dann:
-Die vorderen 4 Klötze um 90 grad, -90 grad, 180 grad seitwärts
-Die hinteren 4 Klötze um 90 grad, -90 grad, 180 grad seitwärts
-die linken 4 klötze um 90 grad, -90 grad, 180 grad "in die tiefe"
-die rechten 4 klötze um 90 grad, -90 grad, 180 grad "in die tiefe"Macht 12 Züge
Wenn ich die rechten 4 Kloetze um 90 Grad dreche, ist es das gleiche, wie wenn ich die linken 4 Kloetze um -90 Grad drehe. Darueber unaus hast du oben und untern vergessen. Es sind drei Achsen!
-
Ich glaube, du hast was anderes als ich unter "in die tiefe" verstanden.
Stimmst du denn zu, dass es 12 Züge gibt?
-
Stimmst du zu, dass ich genau 3 Achsen habe , um die ich drehen kann?
-
Ich gehe davon aus, daß es jetzt langsam um Sachen geht, die man gleichermaßen in Cobol oder Nextrun oder C++ lösen würde. Bis auf kleine Syntaxunterschiede. Darum verschiebe ich in ein Forum, wo mehr Programmierer sind als nur im C++-Forum...
-
Dieser Thread wurde von Moderator/in volkard aus dem Forum C++ (auch C++0x, bzw. C++11) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Ich sehe im moment nur 2 achsen, vielleicht kannst du mir auf die sprünge helfen?
Das mit den links 90 grad ist das gleiche wie rechts -90 grad ist schonmal eine hilfreiche sache, war mir bisher noch nicht aufgefallen.
-
Du kannst beispielsweise links festhalten und die rechten 4 Kloetze drehen. Du kannst die oberen festhalten und die unteren drehen, du kannst die hinten festhalten und vorne drehen.
-
Ok überzeugt
Hab eine Achse irgendwie übesehen gehabt.
Also sinds dann 9 und nicht 12 Züge, oder wenn man nur diese quarter züge macht dann sogar nur 6?
-
Genau, und wenn man den Zug nicht zuruecknehmen moechte sind es nur noch 5 Moeglichkeiten. Beim ersten Zug kann noch nichts zurueckgenommen werden, also 6 (fuer den ersten) * 5^13 Zuege. Die durchzuprobieren ist nicht weiter schwer. Du brauchst eine Datenstruktur, die den Wuerfel repraesentiert, eine Repreasentation einer Vierteldrehung und eine Funktion, die den gegebenen Wuerfel vor der Drehung in den gegebenen Wuerfel nach der Drehung ueberfuehrt. Bei jedem Schritt muss noch getestet werden, ob der Wuerfel bereits geloest ist.
-
Ich würde zwar lieber die 180 grad auch zulassen, aber so sind es ein paar rechnungen weniger. Ich werde das dann mal so implementieren, wenn keiner mehr verbesserungsvorschläge hat und schauen, wie lang es dauert. Ein paar Minuten werden es vermutlich sein. 1 milliarde züge und 2 milliarden takte pro sekunde, aber ein zug wird ja schon ein paar takte dauern
Vielen Dank für die Hilfe!
-
Ich wuerde 180 Grad nicht zulassen. Du kannst auch nachtraeglich 2 gleiche 90 Grad Drehungen zu einer von 180 Grad zusammenfassen.