Aufgabe: Algorithmus eines Zauberwürfels

[p0ke]

Also eigentlich wäre eine derartige Aufgabe besonders für die Studierten unter den DP Members gedacht, die sich schon mit dem Damenproblem (mathematisch :) ), dem Traveling Salesman Problem und diesem ganzen Kram auskennen.
Es geht also darum ein Programm zu schreiben, welches einem irgendwie einen Zauberwürfel berechnen kann (dieses nette Spielzeug, bei dem man versuchen muss auf jeder Seite des Würfels hinterher jeweils nur noch 9 Facetten einer Farbe zu haben). Ich weiß nich ob das überall Zauberwürfel genannt wird.
Vielleicht gibt es ja sogar schon ein fertiges Programm diesbezüglich. Ansonsten würde mir es aber auch einfach nur Spass machen euch zu diesem Thema diskutieren und überlegen zu sehen.
(Hinweis: Falls es sich so anhören sollte: Ich habe keine Lösung dafür, so das ich euch abfragen könnte diesbezüglich :) )

Ich hoffe mal das kam verständlich rüber. Ansonsten liefere ich gerne noch Infos nach.
(und fragt nich wozu ich das brauche, wirklich brauchen tu ich das nämlich nich... is mehr ne Spassaufgabe)

Gruss

p0ke

[MrKnogge]

Fragt sich nur, wie willst du die aktuelle Position der Facetten eingeben ?

Ich hab grad keinen Zauberwürfel zur Hand, aber man kann doch
jede Reihe drehen, oder ?

Vielllleicht kennt ja jemand ne Seite, auf der der Aufbau eines solchen Würfels beschrieben ist, das könnte sicherlich Weiterhelfen.

Aber das sich dies mit einem Algorithmus lösen lässt, wag ich zu bezweifeln !?

[sakura]

Zitat:

Zitat von MrKnogge

Aber das sich dies mit einem Algorithmus lösen lässt, wag ich zu bezweifeln !?

Es gibt Leute die können jede Situation in weniger als 30(!) Sekunden(!!) lösen. Da muss es also einen Algorithmus geben ;-)

...:cat:...

P.S.: Lang ist es her, aber ich kannte die Algos auch mal.

[Seniman]

Hallo p0ke,

man kann ohne Probleme im Internet Anleitungen finden, wie man einen Zauberwürfel (auch Rubikwürfel genannt) wieder in die Ausgangsposition zurückbringen kann. Bei dieser Lösung handelt es sich allerdings nicht um die schnellste Lösung, sondern um eine einigermaßen geordnete, so dass ein Mensch sie nachvollziehen kann.
Man könnte nun einen Rubikwürfel-programm schreiben, dass einen solchen Algorithmus durchführt. Wie gesagt wäre das aber nicht die schnellste Lösung. Sprich: Man dreht an dem Würfel dreimal--> Das Programm findet eine Lösung, bei der man 53mal drehen muss.
Vielleicht kann man rekursiv alle möglichkeiten durchgehen und so die schnellste finden. Das verbraucht nur ziemlich viel Speicher, weil man von jeder Position aus 18 Drehungen machen kann.

Edit: Falls jemand wissen will, wie so ein Rubikwürfel von innen aussieht: Man kann diese Teile ganz einfach auseinanderbauen (und hinterher wieder zusammen). Einfach eine Ebene um etwa 30° drehen und dann eine andere dagegendrehen. Man muss ein wenig Kraft anwenden, aber das klappt. Das ist dann auch gleichzeitig, die Methode für Verzweifelte: Würfelauseinandernehmen und geordnet wieder zusammensetzen. Klappt zwar nicht in 30 sek, aber bestimmt in 5 Minuten :-D .

Grüße
Seniman

[Stanlay Hanks]

Zitat:

Zitat von sakura

...
Es gibt Leute die können jede Situation in weniger als 30(!) Sekunden(!!) lösen. Da muss es also einen Algorithmus geben ;-)...

:gruebel: Ich überleg grade...meinst du nicht, dass da eventuell auch etwas Glück und Zufall dabei ist, oder is das öfters getestet worden (bei besagten Menschen)?

Zum Problem: Ich hab so ein Teil schon lange nicht mehr gesehen...Lieg ich richtig, wenn ich annehmen, dass, wenn man eine Seite komplett hat, man alle anderen auch hat? :gruebel:

Man liest sich, Stanlay :hi:

[MrKnogge]

nicht unbedingt, besser gesagt: "Das ist ja das schwierige :mrgreen: "

[p0ke]

Das sind doch schonmal interessante Ansätze :)
Öhm, also Stanlay, es kann sein das du nur eine Seite hast und der Rest nicht passt, es kann auch passieren das du 3 Seiten fertig hast aber die anderen 3 nich. Dann kommt das Problem, jetzt musst du die 3 fertigen Seiten wieder "kaputt" machen um auch noch die anderen 3 fertig zu bekommen :)
@Seniman: Wir bleiben mal bei dem Programm. Also da die Elemente auseinander ziehen und geordnet wieder zusammenstecken (mogeln) is nich :mrgreen:

[Seniman]

Hallo

@Stanlay: Nein, das hat absolut nichts mit Glück zu tun. Ich war mal absolut begeistert von diesen Teilen und hab es eine ganze Weile geübt. Ich konnte dann einen komplett chaotischen Rubikwürfel in ca 2 Minuten wieder "heile" machen. Inzwischen hab die Übung nicht mehr so ganz drin und brauche länger.

Grüße
Seniman

[MrKnogge]

ich hab meiner Schwester mal ne Email geschrieben, die hatt sich früher auch Stundenlang mit den Dingern beschäftigt, zudem hat ist sie Mathe-Lehrerin, vielleicht hat sie ja eine Lösung :roll:

[p0ke]

Hab mal n bisschen rumgesucht und was gefunden. Habs mir noch nich angesehen, aber ich denke es is für alle interessant.
Cube Explorer

Delphi 6 Source gibts da ebenfalls.

[Lefko]

Wikipedia:

Man kann den Zauberwürfel auch mit verbundenen Augen lösen. Zu diesem Zweck bekommt man zuerst Zeit, sich den verdrehten Würfel einzuprägen. Der amerikanische Student Leyan Lo stellte in dieser Disziplin im Jahre 2006 mit 1 min 28,82 sec einen neuen Weltrekord auf

:shock: :shock: :shock: :shock: :shock: :shock: :shock: :shock: :shock: :shock:

[alzaimar]

Zauberwürfel: Es gibt ca. 8 Operationen, um bestimmte Teilaufgaben zu lösen. Dazu gehören:
1. Alle 8 Ecken in die richtige Position bringen
2. Obere und untere Fläche fertigstellen
3. Die Mitte fertigstellen
Meist sind jetzt 2 Steine vertauscht. Die bekommt man mit 8*3 Drehungen umgedreht-
4.Fertig.

Das o.g. ist nur eine von vielen Möglichkeiten. Ich hab das früher in so ca. 40 Sekunden geschafft. Wie gesagt, keine Kunst, wenn man die Operationen geübt hat.

Mit ein wenig Übung schafft das Jeder ohne Gichtproblemen in den Händen. Als Algorithmus eine nette Aufgabe, mehr aber auch nicht.

[gordon freeman]

Hier wird beschrieben, wie ein Lösungsweg funktioniert. Ich habe mich auf einer Mathematik-Informatik-Akademie mal mit einem aktiven Spped-Cuber unterhalten und der sagt, es gibt für alles Algorithmen. Alle diese Algorithmen basieren letztendlich auf dem Tausch von 2 Farbflächen. Wenn du dafür einen Algorithmus hast musst du ihn nur entsprechend oft anwenden, um den Würfel zu sortieren. Ich frag ihn mal, ob er mir dazu einschlägige Seiten sagen kann ....

[Corpsman]

Ho ich habe das gemacht, ist im Prinzip total easy ;)

Link zum Programm

[Cöster]

@ 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

[dino]

wie redet ihr hier über den Zauberwürfel???
ich hatte früher(ok sehr viel früher) so einen und hab stunden versucht ihn wieder zurückzukriegen aber nie wieder geschafft

bei *Simpsons* hat er in der Folge, wo *Flanders* durchdreht auch mal kurz für verwirrung unter den *Simpsons* gesorgt

[Cöster]

@ Dino:
Ging mir nicht anders, bis ich irgendwann mal auf diese Seite gestoßen bin :wink:

[dino]

den zauberwürfel hab ich damals verflucht und zerstört, sonst würde ich jetzt dazu verführt sein die seite auszuprobieren

[Corpsman]

@Cöster :

Du hast nicht ganz unrecht, es gibt soviel ich weis sogar einen Beweis das man nicht sehr viele Drehungen braucht , ich meine es waren sogar unter 30.

Die Brute Force habe ich auch mal getestet. Selbst wenn man das mit einer Heuristischen Variante Koppelt geht es nicht.

Das heist es geht schon. Aber mein Algo hat es nur geschafft wenn weniger oder 6 drehungen notwendig waren, d.h 18^6 Möglichkeiten ( unoptimiert ).

Sobald ich den Würfel mehr Verdreht habe ist die Rechenzeit derartig explodiert das nichts mehr ging. Zusätzlich mus man ja noch speichern wie man auf die Lösung kommt. Das hat mein 1 GB RAM Speicher dannn auch noch zerlegt.

[Phoenix]

Zitat:

Zitat von Seniman

Edit: Falls jemand wissen will, wie so ein Rubikwürfel von innen aussieht: Man kann diese Teile ganz einfach auseinanderbauen (und hinterher wieder zusammen). Einfach eine Ebene um etwa 30° drehen und dann eine andere dagegendrehen. Man muss ein wenig Kraft anwenden, aber das klappt. Das ist dann auch gleichzeitig, die Methode für Verzweifelte: Würfelauseinandernehmen und geordnet wieder zusammensetzen. Klappt zwar nicht in 30 sek, aber bestimmt in 5 Minuten.

Hey, verrat doch nicht wie ich die damals immer meine Würfel gelöst hab. Ich hab immer jemanden gesagt er soll die verdrehen, hab mich dann damit 5 Minuten aufs Klo verdrückt ('Da kann ich besser Denken...') und WUPPDI - war er gelöst ;-)

Es gibt inzwischen u.a. schon einen Lego-Roboter, der die Lösen kann. Der Link dazu war irgendwann mal bei Userfriendly.org als Link of the Day promoted. Da hat einer so eine Halterung für den Würfel gebaut und einen Roboterarm der den ganzen würfel bzw. die einzelnen Seiten drehen und per Webcam fotografieren konnt. Der hat halt ne Weile gebraucht, ging aber komplett vollautomatisch.

[gordon freeman]

Zitat:

Zitat von Corpsman

Die Brute Force habe ich auch mal getestet. Selbst wenn man das mit einer Heuristischen Variante Koppelt geht es nicht.

Ich würde da auch eher zu Backtracking tendieren. Und dann den Backtracking-Algorythmus so anpassen, dass er nach der besten Lösung sucht. Sollte doch hinkommen, wenn man noch die kombinatorischen Elemente einbaut, wie sie oben schon aufgezählt sind.

[OT] Aber zum Thema Backtracking stelle ich jetzt auch mal ein kleines Tutorial in Aussicht mit allgemeiner Klasse, hab alles hier, muss es nur noch vernünftig dokumentieren und abtippen.

[Cöster]

Zitat:

Zitat von Corpsman

Sobald ich den Würfel mehr Verdreht habe ist die Rechenzeit derartig explodiert das nichts mehr ging. Zusätzlich mus man ja noch speichern wie man auf die Lösung kommt. Das hat mein 1 GB RAM Speicher dannn auch noch zerlegt.

Ließe sich das Problem nicht lösen? Ideal wäre es, wenn die Drehungsfolge an der Wegnummer ablesbar wäre.

Wenn das nicht ginge/zu kompliziert wäre:

Delphi-Quellcode:

private
  FBestWay: array of Byte;  // Speicherung des bisher besten Weges
  FCurrentWay: array of Byte; // Speicherung des aktuell berechneten Weges
  function AllTried(const Way: array of Byte): Boolean; // prüft, ob alles probiert wurde
  procedure CalcWay(var Way: array of Byte); // Berechnet nächsten Weg
  function Solved(var Way: array of Byte): Boolean; // geht Drehungen durch,
                                                    // bei Lösung: verkürzt Way und gibt True zurück
{...}

implementation

procedure TForm1.btnLoesen1Click(Sender: TObject);
var
  i: Byte;
begin
  SetLength(FCurrentWay, 30);
  for i := 1 to 29 do
    FCurrentWay[i] := 1;
  FCurrentWay[30] := 0;
  repeat
    CalcWay(FCurrentWay);
    if Solved(FCurrentWay) then
    begin
      SetLength(FBestWay, Length(FCurrentWay);
      FBestWay := FCurrentWay;
    end;
  until AllTried(FCurrentWay);
end;

{...}