cheesy
25.02.2010, 09:33

Hilfe für Rubics Cube Solver Algorithmus gesucht

Hi,
nachdem ich seit Montag stolzer Besitzer eines Mindstorms Sets bin, wollte ich langsam daran arbeiten, einen Rubics Solver zu bauen. Das Technische werde ich wohl irgendwie hinkriegen (auch wenn ich noch nicht genau weiss, wie), das Scannen der Farben mit dem Farbsensor wird wohl auch nicht so schwierig werden.
Was mir aber gehörig Kopfschmerzen bereitet, ist der Algorithmus zum Lösen des Würfels. Die Programmierung wollte ich eigentlich mit NXC erledigen (habe mir ein auf den ersten Blick sehr gutes Buch gekauft, das die Funktionsweise des NXT recht gut erklärt). Die Berechnung soll dann der NXT machen, also ohne Computer.
Ich bräuchte ein Programm, das ich mit den Farben der einzelnen Seiten füttere und das mir dann die benötigten Bewegungen liefert. Diese könnte ich dann Bewegungen des Mindstorms umsetzen.

Hat jemand einen Tip für mich?

Gruß, Peter


ThomaS
25.02.2010, 12:55

Re: Hilfe für Rubics Cube Solver Algorithmus gesucht

Hallo Peter,

» Ich bräuchte ein Programm, das ich mit den Farben der einzelnen Seiten
» füttere und das mir dann die benötigten Bewegungen liefert.

Hier gibt es ein Online-Programm, welches basierend auf vordefinierte Farbinfos einen Lösungsweg berechnet. Quellcode inclusive.

Viel Erfolg & Spaß
ThomaS


mike
25.02.2010, 13:42

Re: Hilfe für Rubics Cube Solver Algorithmus gesucht

Hi


» nachdem ich seit Montag stolzer Besitzer eines Mindstorms Sets bin,
Yeah! Einer mehr!


» wollte ich langsam daran arbeiten, einen Rubics Solver zu bauen. Das Technische
» werde ich wohl irgendwie hinkriegen (auch wenn ich noch nicht genau weiss,
» wie), das Scannen der Farben mit dem Farbsensor wird wohl auch nicht so
» schwierig werden.
» Was mir aber gehörig Kopfschmerzen bereitet, ist der Algorithmus zum Lösen
» des Würfels. Die Programmierung wollte ich eigentlich mit NXC erledigen
» (habe mir ein auf den ersten Blick sehr gutes Buch gekauft, das die
» Funktionsweise des NXT recht gut erklärt). Die Berechnung soll dann der
» NXT machen, also ohne Computer.
Hans Andersen hat den Tilted Twister gebaut, der löst den Rubik's Cube mit den Einzelteilen des NXT1.0 Baukastens, dort würde ich mal zu suchen anfangen ... tiltedtwister.com


» Ich bräuchte ein Programm, das ich mit den Farben der einzelnen Seiten
» füttere und das mir dann die benötigten Bewegungen liefert. Diese könnte
» ich dann Bewegungen des Mindstorms umsetzen.
Warum willst Du die Farben einfüttern? Dafür hast Du doch Deinen Roboter!


lg
Mike


MTM
25.02.2010, 14:06

Re: Hilfe für Rubics Cube Solver Algorithmus gesucht

braucht man da so groß Farben einzufüttern?

ich hab irgendwo zu Hause eine Anleitung, wie man den Rubic Cube - manuell und analog - also normal mit seinen beiden Händen - löst.

Da für muss man eigentlich immer nur die rechte untere Ecke und zu Beginn die mittlere mittlere und die untere mittlere Fläche betrachten.
Und dann gibt es dafür bestimmte Zugregeln, die gemacht werden müssen. Theoretisch ist das so doch einfacher, als zu Beginn alle Farben einzulesen und dann eine Gesamtlösung zu berechnen.

Ich guck mal, ob ich die Lösung finde, bzw. ob sie sich noch abscannen lässt, meines Erachtens war sie auf häßlich glattem Faxpapier gedruckt und vergilbt von Jahr zu Jahr mehr.

Oder versteh ich das grundsätzlich falsch? Meine beiden Semester Informatik liegen auch schon zu viele Jahre zurück.

Micha


mike
25.02.2010, 15:36

Re: Hilfe für Rubics Cube Solver Algorithmus gesucht

Hi


» braucht man da so groß Farben einzufüttern?
Wohl!


» ich hab irgendwo zu Hause eine Anleitung, wie man den Rubic Cube - manuell
» und analog - also normal mit seinen beiden Händen - löst.
»
» Da für muss man eigentlich immer nur die rechte untere Ecke und zu Beginn
» die mittlere mittlere und die untere mittlere Fläche betrachten.
» Und dann gibt es dafür bestimmte Zugregeln, die gemacht werden müssen.
» Theoretisch ist das so doch einfacher, als zu Beginn alle Farben
» einzulesen und dann eine Gesamtlösung zu berechnen.
Das mag schon stimmen, ich kenne diese Lösungen.
Aber da guckst Du schon immer vor jedem Zug wo die Ecken denn hinsoll, wo sie farblich dazupasst!
Wenn Du das also so auf einen Roboter umlegst, dann mußt Du wohl oder übel nach jeder Zugkombination wieder ein paar Farben einscannen - das dauert in Summe dann aber länger, als wenn Du am Anfang alle Seiten des Würfels einmal betrachtest!


lg
Mike


RobbyRay
25.02.2010, 15:59

Noch ein Problem!

Hi Peter
Du hast noch ein Porblem:
1. Als erstes braucht der Roboter einen fertig gelösten Cube um sich alles zu merken. Falls du einen ungelösten Cube hast, probiere es mit dem Programm Cube.

2. Zum wenden brauchst du ein Stück Pappe (7*7cm mit Ecken 8*15mm).

Ließ dir einfach hier alles durch.

Zum Algorithmus kann ich dir auch nicht weiter helfen.


Lego'ische Grüße
Henrik


fgee
25.02.2010, 17:50

Re: Noch ein Problem!

Es begab sich, dass ich letzte Woche bisschen im Web rumgesucht habe zum Thema.

Das Lösen des Rubiks Cube besteht eigentlich aus mehreren Unterthemen, die jedes für sich bereits ziemlich anspruchsvoll sind:

1) Einlesen des Istzustands.
Ansätze:
- Eingeben von Hand und übermitteln dan den NXT
- Scannen mit dem Farbsensor (wie bei Tilted Twister)
- Verwenden einer Handycam oder Webcam und übermitteln an den NXT (geht am effektivsten)

2) Berechnen der Lösung.
Ansätze:
- Programm aus dem Link von Antwort 1 (ist jedoch sehr langsam)
- oder Verwenden der Algorithmen und Programme von Herbert Kociemba (schneller geht nicht)

3) Konstruktion einer Mechanik, die den Würfel kippen und drehen kann.
Ansätze:
- Tilted Twister (kommt mit lediglich 2 Motoren aus. Genial einfach!
- Kippen mit einem Motor, Festhalten beim Drehen mit einem anderen, Drehen mit dem Dritten. Das eröffnet Möglichkeiten für eine schnellere Mechanik. Dann steht der dritte Motor aber nicht mehr für die Bildgewinnung zur Verfügung -> Kamera unausweichlich.
- Die effektivste Mechanik (und dabei einfach nachzubauen) ist diese hier. Allerdings 2 NXT erforderlich.

4) Programmieren der Bewegungen, die sich aus der Lösung ergeben. Dabei ist exzessive Koordinatentransformation erforderlich, weil der Würfel (anders als beim Lösen von Hand) ständig seine Lage im Raum ändert.


Ich würde auch mit dem Tilted Twister beginnen.

Felix


cheesy
25.02.2010, 19:43

Re: Noch ein Problem!

Hi,

mein Plan war schon, ähnlich wie der Tilted Twister vorzugehen. Ziel ist es, komplett alles mit einem NXT zu lösen. Das Einlesen mit dem Farbsensor sollte machbar sein, wenn ich die Farben meines Cubes einmal kalibriert habe. Weitaus schwieriger stelle ich mir die Konstruktion der Dreh- und Kippmechanik vor. Ich habe nunmal nur drei Motoren zur Verfügung und einer davon müsste schon den Farbsensor bewegen. Ich bin momentan am grübeln, ob ich es igendwie bewerkstelligen kann, dass der Farbsensor mit einem "Arm" kombiniert werden kann, der den Würfel auch bewegen kann.

Den Sorcecode vom Tilted Twister schaue ich mir mal an, damit könnte ich ja evtl. weiterkommen.

Danke auf jeden Fall schonmal für die Tipps.

Gruß, Peter


Gesamter Thread: