Hi ihr.

Ich suche schon seit Stunden nach einem Algorithmus bzw. einer Lösungsidee für folgendes Spiel:
http://puzzles.puzzled.com/lightson/
Ich dachte mir einfach, dass hier so viele gute Programmierer sind, dass vielleicht einer von euch eine Idee hätte, das Spiel sinnvoll zu lösen. Das Hauptproblem ist, dass ich die beste Lösung finden muss und bisher nicht mal weiss, wie ich irgend eine Lösung finde, ohne einfach zu probieren...
Falls irgend jemand eine Idee hat, wie man das lösen könnte, wäre ich natürlich extrem froh, wenn er das posten könnte (brauche nur einen kleinen Ansatz und auf jeden Fall keine Lösung)...

BTW: Das ganze ist eine Aufgabe der SOI und falls es hier junge schweizer Informatiker hat, wäre es natürlich schön, wenn sich noch der eine oder andere anmelden könnte...
[Edit]
URL-Tag richtig geschrieben (das kommt davon, wenn man im Moment hauptsächlich auf einem PhpBB unterwegs ist... Oo)
[/Edit]
[Edit2]
Und bevor die Frage auchtaucht: Es ist Sinn der Runde 1, dass man sich Ideen auch von anderen Personen holen darf...
[/Edit2]

Hi,
Du könntest das ganze als Suchproblem formulieren: Du betrachtest das Spielfeld als einen Zustand, z.B. als einen Vektor der Länge 25 mit 1 oder 0.
Jetzt kannst du für jedes Feld eine Übergangsfunktion definieren. Diese Übergangsfunktion beschreibt, was mit dem Vektor passiert wenn du das Feld anklickst.

Nun gilt es noch Folge von Übergangsfunktionen zu finden, welche zur Lösung kommt. Dazu verwendet man typischerweise Iterative Deepening Search, was den Lösungsraum (also jede mögliche Folge von Übergangsfunktionen) durchsucht.

www.d3opencoop.com - A Doom3 Cooperative Mod

Zitat:

Nun gilt es noch Folge von Übergangsfunktionen zu finden, welche zur Lösung kommt. Dazu verwendet man typischerweise Iterative Deepening Search, was den Lösungsraum (also jede mögliche Folge von Übergangsfunktionen) durchsucht.

Man muss also irgenteine Begrenzung finden.

Die eigentliche Lösungsidee von Nicemice halte ich aber für sehr sinnvoll. Ich würde wahrscheinlich eine Klasse daraus machen.

Entities: HL | HL²
Kompilierfehler
r_speeds | mehr über r_speeds

@Leviathan: Ein Suchalgorithmus sollte zurerst alle Möglichkeiten für einen, zwei, drei usw. Züge abgrassen.

Es kann zwar unendlich viele Sequenzen von Zügen geben, aber die Anzahl der Zustände ist endlich. Das heißt, nach einer gewissen Anzahl von Zügen bist du wieder in einem Zustand wo du schon warst.

(Beispiel: Wenn man zweimal das gleiche Feld anklickt, dann läuft man sozusagen im Kreis)

www.d3opencoop.com - A Doom3 Cooperative Mod

Zitat:

Nicemice postete
@Leviathan: Ein Suchalgorithmus sollte zurerst alle Möglichkeiten für einen, zwei, drei usw. Züge abgrassen.

Es kann zwar unendlich viele Sequenzen von Zügen geben, aber die Anzahl der Zustände ist endlich. Das heißt, nach einer gewissen Anzahl von Zügen bist du wieder in einem Zustand wo du schon warst.

(Beispiel: Wenn man zweimal das gleiche Feld anklickt, dann läuft man sozusagen im Kreis)

Stichwort: Spielbäume (gibt es 1000 Skripte [nein, nicht Scripts] zu).

georg-wicherski@pixel-house.net | http://www.pixel-house.net/ - Coding Resource| http://www.google.de/