[Lord]

interessantes thema..
mich würde mal interessieren, ob es algorithmen gibt, die den würfel nach x-facher wiederholung lösen, egal wie er vorher gemischt war.. dafür wäre natürlich die voraussetzung, dass der algo jede kante und jede ecke vertauscht.

[Logen]

mhh ja aber man müsste für jede veschidene Mischung (oder farbkombination) einen eigenen Alg geben.
Und wenn es nur einen alg gibt dann dauert es ja bis man gerade die 43 Trilliardste Kombination hat

[NicoS]

@Mezzo: Jetzt hast du mich verwirrt Ich habe keinen Algo, ich hätte gern einen.
@Lord: Geben tut's den bestimmt, der hat nur mindestens 43 Trillionen Züge
Was mich eher interssieren würde, ob dieser Alg denn wirklich genau die Anzahl an Züge, die der Cube Stellungen hat, oder ob manche Stellungen wiederholt werden müssen

[Jannik]

Wenn du den Algo findest der 43 Trillionen Wiederholungen braucht hast du die EINFACHSTE methode für den 3x3. Algo X bis der cube gelöst ist^^. Braucht man nur nen computer für um den zu finden.

Ein solcher Algo nennt sich "zyklisch" . Und die 43 Trillionen Stellungen sind eine "Gruppe".
Ein zyklisches Element ist eine Permutation oder sonstwas. Oder die eins. Wenn man nämlich immer 1 mit 1 addiert, bekommt man jedes Element, also unendlich viele Elemente der Gruppe der natürlichen Zahlen.
Bei Permutationen gibt es allerdings den Fall, dass es wie beim H-Perm ist, dass man nicht alle möglichen Permutationen erhält.
Da geht 1 auf 2, 2 auf 1, 3 auf 4, und 4 auf 3. Also wenn man eine Gruppe mit 2-Edge-Swaps hat, ist die Gruppe nicht zyklisch.
Aber 43 Trillionen Stellungen... Die Gruppe ist bestimmt zyklisch. Man muss jetzt alle God-Algos nehmen und die so oft ausführen, bis der Cube gelöst ist...
Und wenn man 43 Trillionen Male braucht, ist das eben der Algo.

[Jannik]

Die Theorie versteh ich auch, aber warum funktioniert beim algorithmus R U nicht?

6er-Kanten-Cycle.
8erEcken-Cycle.
KgV fon 6 und 8 ist 24. Theorie stimmt nicht.
Aber mal was von Orientation gehört ... ... ... ... ... ... ...

[NicoS]

Also erstens ist das kgV von 6 und 8 niemals 12 (8*x=12 {x € N}; geht nicht auf...), ich würde auf 24 tippen.
Zweitens, wie kommst du auf einen 8 Ecken cycle? Es werden nur 5 Ecken bewegt und eine wird gedreht (dadurch auch eine andere, bzw. einige andere, das ist aber im Moment egal), was zu einen 5 Ecken cycle und einen 3 Ecken cycle führt.
Das kgV von 3 und 5 sind 15 und dann sind es auch nicht 6 sondern 7 Kanten und das kgV von 15 und 7 ist 105.
Drittens hättest du den thread gelesen, wüsstest du die Antwort bereits, da Mezzo das schon alles gepostet hat...

[NicoS]

Mezzo, ich bezweifel, dass es möglich ist einen Alg zu finden mit einem kgV von 43 Trillionen:
Fall 1: Der Alg hat >1 Zug: Wiederholt man den Alg n mal, hatte man mehr als n Stellungen (logisch, da jeder Zug eine eigene Stellung erzeugt und man hat >n Züge)
Fall 2: Der Alg hat exakt einen Zug + xy oder andere Rotations: Hier wäre es möglich, aber ich glaube nicht, dass man alle Stellungen durch macht, wenn man immer die gleichen Rotations hat.
Fall 3: Man hat einen einzelnen gigantisch großen Alg, der alle Stellungen durch geht und schlussendlich wieder zur Ausgangsposition kommt: Mind. 43 Trillionen Züge (für jeder Stellung einen) und evtl. mehr, wenn es unmöglich ist einen solchen idealen Alg zu finden ohne Stellungen zu wiederholen


Zu meinem vorherigen Problem: Das hat sich erledigt, ich bin schlussendlich auf eine Lösung gekommen

[Stefan Pochmann]

Weil man ja quasi einen algorithmus ausführt der die steine permutiert wie bei blind auhc mal so das er nicht mehr orientiert ist aber wenn man einen Pll oder scramble ausführt und das mehrere male dann permutiert man solange bis man an die stelle kommt wo der algo der god's algo ist. (auch wenn scrambles länger sind)

Falsch, ist fast nie goettlich (die meisten Algorithmen sind nicht optimal).

Und es waer nett, wenn du dir mehr Muehe beim Schreiben geben wuerdest, dein Beitrag ist ja grauenhaft zu lesen. Lieber erst der zweite Antworter sein und dafuer nicht wie ein respektloser Volldepp erscheinen.

Jeder Alg tauscht x Kanten (ein x-Cycle) und y Ecken (y-Cycle).

Das kann ja jeder behaupten. Beweis? Wobei es ja eh falsch ist, da es oft mehrere oder gar keine echten Zyklen gibt. Aber auch die korrekte Variante, mit mehreren Zyklen, will erst mal bewiesen werden.

------------------------------------------------

Immer wieder schoen, wenn diese Frage gestellt wird. Ich versuch mich auch nochmal an einer Erklaerung:

Warum gelangt man durch wiederholte Ausfuehrung eines Algorithmus zwangslaeufig irgendwann zur Anfangsstellung zurueck?

Es gibt nur endlich viele Stellungen, daher koennen wir ihn nicht unendlich oft ausfuehren und immer nur neue Stellungen antreffen. Irgendwann gelangen wir zu einer Stellung, bei der wir schon mal waren. Und dann laufen wir natuerlich wieder dieselben Stellungen ab wie nach dem ersten Mal, also immer im Kreis. Jetzt koennte man noch denken, dass die Anfangsstellung nicht im Kreis liegt und dass der Kreis erst "betreten" wird, also dass wir zB die Stellungen 1, 2, ..., 40, 41, 42, 43, 41, 42, 43, 41, 42, 43 und so weiter durchlaufen (also Kreis 41, 42, 43). Dann haette aber Stellung 41 zwei unterschiedliche Vorgaengerstellungen, naemlich 40 und 43. Das kann aber nicht sein, denn wenn man den Algorithmus auf Stellung 41 rueckwaerts anwendet, koennen ja nicht zwei unterschiedliche Resultate rauskommen. Somit ist ein "Betreten" des Kreises unmoeglich und wir befinden uns von Anfang an im Kreis, und die Anfangsstellung ist die erste, die wiederholt wird.

------------------------------------------------

Wenn's darum geht, alle Stellungen mit einem einzigen Algorithmus zu besuchen, dann heisst das uebrigens nicht Gottesalgorithmus, sondern Teufelsalgorithmus. Wie oft ein Algorithmus ausgefuehrt werden muss, um zur Anfangsstellung zurueckzukehren (zb 105 fuer R U), wird die "Ordnung" des Algorithmus genannt. Die groesste Ordnung beim 3x3x3 ist 1260 (bzw 2520, wenn man die Mittelsteine auch betrachtet). Ein Teufelsalgorithmus ohne Wiederholung muss offensichtlich mindestens 43 Trillionen Zuege haben (eine neue Stellung bei jedem Zug besuchen), und ein Teufelsalgorithmus mit Wiederholung noch mindestens einige Billiarden Zuege. Beide Varianten sind noch nicht geloest (also man weiss noch nicht, wie kurz die Teufelsalgorithmen sein koennen), sogar fuer kleinere Puzzles wie 2x2x2 (so weit ich weiss).

[Stefan Pochmann]

Was sollte daran falsch sein?

Weil zB UD nicht 1+1 Zyklen, sondern 2+2 erzeugt (oder gar 6+2, wenn man 1-Zyklen mitzaehlt).

Im Prinzip hast du nur das wiederholt was ich zuvor gepostet hab

Das wird daran liegen, dass deins zu verwirrend/unvollstaendig/falsch war, als dass ich es haette verstehen koennen.

Wenn es diesen Teufelsalgorithmus gibt (Warum heißt der eig so?)

Weiss ich leider nicht sicher, aber ich vermute, weil er eben das Gegenteil vom Gottesalgorithmus ist: maximal doof und lang statt maximal intelligent und kurz.

dann muss der auf keinen Fall 43 Trillionen Züge haben

Ohohoho... also erstmal geh zurueck und lies nochmal, was ich geschrieben habe. Hab ich nicht ganz deutlich zwei Varianten genannt, eine mit und eine ohne Wiederholen? Und auch mit Wiederholen beweist du mir bitte mal, dass es in unter 43 Trillionen Zuegen geht.

Gesucht ist ein Algorithmus der 43 Trillionen mal Wiederholt werden muss, um der cube wieder in Ausgangsstellung zu bringen.

Ich hab doch grad gesagt, dass die maximale Ordnung 1260 (bzw 2520) ist. Wieso willst du dieselben Stellungen trillionenfach immer und immer wieder durchlaufen? Was soll das bringen?

btw, bei Google lässt sich nichts wirksames zu Teufelsalgorithmus finden, also bin ich da bei der Benennung nicht ganz einig .

Dann guckste einfach mal nach Devil's Algorithm.

[Stefan Pochmann]

Um's nochmal klarer zu sagen: Den Teufelsalgorithmus, wie du ihn meinst, gibt es offensichtlich nicht (weil 1260 < 43 Trillionen), daher ergibt es keinen Sinn, ihn so zu definieren. Die sinnvolle Definition ist die, wo auch die Zwischenzustaende waehrend der Ausfuehrung des Algorithmus betrachtet werden, nicht nur die Zustaende am Ende jeder Ausfuehrung.

Und auch aus einem anderen Grund macht das mehr Sinn: Die Idee ist ja, dass man einen Algorithmus hat, den man einfach nur hirntot ausfuehren muss (evtl mehrfach), bis man den Wuerfel irgendwann geloest hat. Und man kann doch auch in der Mitte des Algorithmus aufhoeren, wenn der Wuerfel da bereits geloest ist. Waer doch ziemlich doof, das zu ignorieren und weiter zu drehen, oder?