@ 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