Wegfindung ohne Weg - z.B. Algorithmus zum Lösen von Unblock Me Puzzles
Guten Abend!
Geht es euch auch so, dass ihr manchmal ein Denkspiel spielt und dabei unweigerlich darüber nachdenken müsst, wie man das wohl programmatisch lösen könnte?
So erging es mir letztens beim Spiel Unblock Me auf dem iPhone.
siehe Bild im Anhang bzw. Video (in schlechter Qualität) hier
Habt ihr eine Idee, wie man dieses Problem mit Hilfe eines Algorithmus angehen könnte? Ich könnte mir gut vorstellen, dass sich hierfür Dijkstra oder A* eignen. Mir fallen allerdings keine geeigneten Heuristiken ein, um die Kosten zu schätzen, die zum Ziel führen. Was sagt ihr dazu?
Ich würde mich über ein paar Anregungen von euch freuen. Leider kann ich nicht versprechen, zeitnah zu antworten, da ich gerade beruflich viel um die Ohren habe und bald im Urlaub bin.
VG, Florian
Hallo deerhunter,
unter dem "Originalnamen" Rush Hour findest du mehr als genug Lösungsmöglichkeiten -algorithmen.
Im Prinzip ist es eine Graphen-Suche wo die Kanten die möglichen Züge und die Knoten der Zustand vom "Spielbrett" ist. Wie das auf zB A* angewandt werden kann entnimm obigen Link oder allen anderen Alogrithmen zur Puzzle-Lösung.
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Hallo gfoidl!
Vielen Dank für diese Information. Das ist glaube ich genau das, was ich gesucht habe.
Gute Nacht!
Geht es euch auch so, dass ihr manchmal ein Denkspiel spielt und dabei unweigerlich darüber nachdenken müsst, wie man das wohl programmatisch lösen könnte?
Eindeutig -> nein
Auch wenn danach gefragt wurde: bitte nicht beantworten. Versteht es als rhetorische Frage. Danke.
Eine Möglichkeit wäre, mit logischer Programmierung (z.B. Prolog zu arbeiten).
Dort beschreibst Du die Fakten und Regeln und durch Backtracking wird dann der Lösungsraum durchsucht. Ich habe mal ein Beispiel gesehen, wie das Spiel die Türme von Hanoi damit gelöst wurde.
Grüße solick
Hallo solick,
Ich habe mal ein Beispiel gesehen, wie das Spiel die Türme von Hanoi damit gelöst wurde.
Das ist aber kein gutes Plädoyer für logische Programmiersprachen. Die Türme von Hanoi wurden wohl schon mit jeder Programmiersprache gelöst. 😃
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Hallo gfoidl,
Die Türme von Hanoi wurden wohl schon mit jeder Programmiersprache gelöst. 😃
klar, der Unterschied bei Prolog ist aber, dass man nur die Regeln des Spiels (und die Ausgangslage) beschreibt. Das "Programm" ist also rein deklarativ. Man muss nicht implementieren, wie man Türme von Hanoi löst. Man ruft dann das Programm mit der gewünschten Endstellung als Parameter auf und Prolog sucht dann selber den Lösungsweg. Mit anderen Worten: Das Backtracking steht nicht im Programm, sondern ist wesentlicher Teil des Prolog-Interpreters. Deshalb ist Prolog keine schlechte Wahl, wenn es um Probleme geht, die Backtracking erfordern. Das Backtracking muss man dann nicht ausprogrammieren, sondern bekommt es quasi vom Interpreter geschenkt.
Ob sich allerdings der Aufwand lohnt, wenn C# schon kann, aber Prolog erst lernen müsste und wenn man nur ein bestimmtes (Backtracking-)Problem lösen will, steht auf einen anderen Blatt.
herbivore