2x2x2 Rubiks Cube lösen
-
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.
-
Dann ist die mittlere anzahl an schritten die ich als lösung finde aber vermutlich höher, als wenn ich direkt mit 180 grad erlaubt suche. Warum würdest du es nicht zulassen, einfach weils aufwändiger auszurechnen ist, oder weil dir die regel nicht natürlich erscheint oder soetwas?
Edit:
Mir fällt gerade folgendes auf:
Wir haben je 3 möglichkeiten pro Achse, falls 180 grad erlaubt ist. Geht man dann eine rekursionsstufe tiefer, macht es keinen sinn die selbe achse zu drehen, also braucht man dann nur noch 6 möglichkeiten zu beachten, also sollte sich das bei 180 grad auf 9 * 6^10 = 544 195 584 Funktionsaufrufe beschränken, was durchaus machbar ist. Oder übersehe ich wieder irgendwas?
-
Oder übersehe ich wieder irgendwas?
Bestimmt.
Ich wuerde 180 Grad nicht einbauen, da sie aus eben zwei 90 Grad Drehungen zusammengesetzt ist. Das ist der einzige Grund. Aber es sollte nicht schwierig sein die Moeglichkeit nachtraeglich hinzuzufuegen oder eben wegzulassen. Wenn du sie mitbetrachten moechtest, nur zu.