| Die letzten 2 Beiträge |
| Gast |
Allgemein: Es wird ein Algorithmus benötigt, der das Problem - unter minimalen Grundannahmen über den Lösungsweg - sicher löst.
Das bedeutet: Es findet eine Zerlegung des Problems in formale Teilprobleme statt. Über die Verknüpfung der formalisiertenTeilprobleme lässt sich überprüfen ob die Zielvorgabe erreicht wurde.
In Kürze: Je nachdem wie das Problem gelöst wurde, ist es sehr einfach das Ergebnis zu überprüfen oder sehr schwer. |
| Greetings |
Hashiwokakero
Hallo,
ich stehe vor einem Problem. Es geht um das Spiel "Hashiwokakero". Es soll eine automatische Lösungsstrategie erstellt werden.
Kurz: Es werden Inseln auf einem Spielfeld platziert und man darf höchstens n Brücken in jede Nachbarrichtung bauen, aber nur maximal zwei Brücken in jede Richtung. Die Brücken dürfen sich nicht kreuzen. Das Spiel ist gewonnen, wenn alle Inseln die richtige Anzahl Brücken haben und jede Insel indirekt verbunden ist. (siehe Anhang)
Meine ersten Schritte waren:
1.) Prüfen, ob nur eine Nachbarinsel möglich ist. Wenn ja: Dann verbinde.
2.) Prüfe ob z. B. eine 8 auf der Insel steht und 4 Nachbarn hat. Dann baue in jede Richtung zwei Brücken. Das gleiche passiert wenn eine 6 auf der Insel steht und man nur 3 Nachbarn hat. Oder man hat eine 4 und zwei Nachbarn.
3.) Prüfe, ob es sich um eine 7 mit 4 Nachbarn handelt. Dann baue in jede Richtung eine Brücke. Oder eine 5 mit 3 Nachbarn oder eine 3 mit 2 Nachbarn.
4.) Prüfe, ob es sich um eine 3-er, 5-er oder 7-er Insel handelt und sie eine 1-er Insel als Nachbarn hat und die Nachbarn (ohne eins) sich komplett verbinden lassen. Dann dürfen alle Nachbarn verbunden werden. Das Gleiche gilt für eine 4 und zwei 1-er Inseln, dann darf der dritte Nachbar mit zwei Brücken verbunden werden.
All das ist auf jeden Fall korrekt. Im Anhang mal ein Beispiel, an dem ich den Algorithmus durchlaufen lasse. Die Inseln, die orange gefärbt sind, haben schon die maximale Anzahl Inseln.
Nur jetzt frage ich mich: Wie geht es weiter?
Mein Vorschlag ist:
5.) Baue eine Brücke zufällig. Prüfe, ob es dann noch eine Lösung gibt.
Meine Frage ist jetzt:
Wie kann ich prüfen, ob es dann tatsächlich noch eine Lösung gibt, nachdem ich die Brücke gebaut habe?
Oder habt ihr noch andere Ideen? Danke!
Greetings hat dieses Bild (verkleinerte Version) angehängt:
|
|
|
