[Conanfreak]

Hi Leute.
Ich cube seit fast einem halben Jahr bin aber eher schlecht.
In meiner freizeit bin Ich im Schülerrechenzentrum in Dresden in dem Informatik Grundkurs.
Dort müssen wir über das ganze Schuljahr ein Programm mit Java schreiben, das Thema dürfen oder eher durften wir selber aussuchen.
Ich habe mich dafür entschieden ein Programm zum lösen eines normalem 3x3 Zauberwürfel zu schreiben.
Allgemein habe Ich schon ein ziemlich gutes Konzept was ich auch schon zum teil programmiert habe und zwar indem ich den Zauberwürfel durch zufall löse.
Allgemein wird der Würfel nur in Stickern eingegeben also mit 48 variablen, was die wirtuelle Züge sehr einfach zu programmieren macht.
Allgemein brauche ich nurnoch einen effizienten breitensuchalgorithmus, der alle Züge systematisch abgeht ohne zu viel speicher zu verbrauchen und vorallem wenn er die lösung in einem naja mehr oder weniger großem Baumdiagramm findet sie zurückverfolgen kann.
Wer sich das ganze nicht ganz vorstellen kann muss sich ein Baumdiagramm vorstellen was pro punkt 12 weitere Punkte hat und 20 punkte tief ist.
Ich nehme jede Art von Hilfe gerne an und würde auch noch alles erklären brauche eben nurnoch eine elegante Variante obwohl sie noch nichteinmal elegant sein muss nur muss sie funktionieren auch wenn sie den Würfel nicht unbedingt löst sondern nur lösen könnte (wegen relativ hoher prozessorbeanspruching).
Auf jeden Fall schoneinmal fielen Dank
Conan

[Sébastien]

Hi. Das hier könnte dir helfen: http://kociemba.org/twophase.htm

[moritz]

Baumdiagramm [...] was pro punkt 12 weitere Punkte hat und 20 punkte tief ist.

die 12 für 6 seiten die man in zwei richtungen drehen kann? dann gibt es soweit ich weiß auch positionen die mehr als 20 züge zum lösen brauchen. die 20 gilt nur in HTM, d.h. es sind auch 180°-drehungen einer seite als "ein zug" erlaubt.

Aber genug von haarspaltereien. ich verstehe nicht so ganz was du mit "durch zufall lösen" meinst. willst du alles so lange durchprobieren bis der würfel gelöst ist? das ist glaub ich ziemlich ineffizient. die meisten lösungsprogramme verwenden eine X-TFS datenbank, wo alle positionen die X turns from solved sind drinstehen. und dann probierst du an deinem scramble paar züge durch bis du einen treffer in der TFS datenbank hast und danach kannst du die lösung zusammensetzen aus dem durchprobierten teil und dem aus der datenbank. also sozusagen ein "treffen in der mitte".

einige leute behaupten dass die darstellung als permutation von stickern auch wahnsinnig ineffizient ist. ich glaube die meisten leute bevorzugen eine darstellung als permutation des cubies zusammen mit der orientation.

also so viel zu dem was du schon geschrieben hast. mit was genau soll man dir den helfen? (das geht nicht ganz aus deinem text hervor)

ich habe mein weltwissen übrigens fast nur aus diesen beiden threads:
http://www.speedsolving.com/forum/showth...rce-Solver
http://www.speedsolving.com/forum/showth...20-Minimum

[Jakube]

Ich nehme mal an, dass du die optimale (kürzeste) Lösung zu einem Würfel suchst. Da kann ich jetzt schon sagen, dass dir das nicht gelingen wird. Nicht böse gemeint, aber der Verzweigungsfaktor ist einfach zu groß. Ich habe noch nie ein Programm gesehen, dass mir zu einem zufälligen Würfel die optimale Lösung sagen konnte. Zumindest wenn die optimale Lösung 19 oder 20 Züge lang ist.

Übrigens, der Faktor 12 ist falsch. Im einfachsten Fall hast du einen Faktor von 15. Wenn du dann doch Drehungen ignorierst, die sich kürzen (z.B. R L R = R2 L) oder die doppelt vorkommen (R L = L R), kommst du nur auf einen Faktor von 13.35 (Ganz genau gesagt 6 + 3 * Wurzel(6)). Für die Tiefe 10 hättest du dann schon 269.405.157.600 Knoten. Viel zu viel für einen Rechner. Zumindest 20 wird er nicht erreichen, denn dort gibt's schon 48.386.092.616.942.490.160.128 Knoten.

Trotzdem gibt es einige Techniken, wie man einigermaßen gute Ergebnisse bekommt. Ich habe mich selbst im letzten Monat wieder ein mal damit beschäftigt, und ich kann zum Teil 15 Züge-Lösungen in ca. 1 Minute optimal ermitteln. Wenn die Steine etwas unpassend liegen, dann komme ich allerdings höchstens bis 13 Züge.

Eine gute Seite, mit vielen dieser Techniken, ist http://www.jaapsch.net/puzzles/compcube.htm.

Eine Alternative ist, den Würfel nicht optimal zu lösen, sondern nur pseudo-optimal. Mit Kociemba's Algorithmus kann man jeden Würfel in ca. 21-23 Züge im Bruchteil einer Sekunde lösen. Diese Lösung ist im allgemeinen nicht die kürzeste, aber eine gute Näherung. Den Algorithmus findest du ebenfalls unter der oberen Seite oder unter Sébastien's Link.

[Conanfreak]

Vielen Dank erstmal wenn ich fragen habe melde ich mich auf jeden Fall noch einmal und nochmal danke für die schnellen Antworten ;D

Gesendet von meinem Nexus 5 mit Tapatalk