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:
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Greetings: 06.11.2018 19:45.
|
