mal ein grober Algo-Entwurf ohne Optimierung:

1. die Zellen des Spielfelds und des Außenrandes als 2D-Array darstellen.

2. Jede Zelle kann 7 verschiende Zustände einnehmen, 2 gerade, 4 gebogene oder gar kein Streckenstück.

3. Jede Zelle kann diverse Neben-Bedingungen haben, die erlaubte Zustände einschränken:
a) Weißer Punkt =>muss ein gerades Streckenstück beinhalten, mind. ein verbundener Nachbar gebogen
b) Scharzer Punkt => muss gebogenes Streckenstück beinhalten, kein verbundener Nachbar gebogen
c) kein Punkt
d) liegt außerhalb

4. Die erlaubten Zustände einer Zelle werden zusätzlich (nur) von den Bedingungen und Zuständen der vier Nachbarzellen beeinflusst.

5. Baumsuche:
a. Einen Punkt als Start auswählen.
b. in aktueller Zelle erlaubten Zustand ausprobieren.(evt. Backtrack auf frühere Zelle)
c. auf Widerspruchsfreiheit mit Nachbarn überprüfen
c1. Widerspruchsfrei => Nachbarn als aktuelle Zelle auswählen, Teilstrecke erweitern.
c2. Widerspruch => Zustand streichen, weiter mit =>b
d. Falls Nachbar gleich Startpunkt, überprüfen ob alle Schwarzen und Weißen Punkte durchlaufen wurden.
d1. Nein => b
d2 Ja => Fertig.


Dieser Brute-Force Ansatz dürfte für einfache Beispiele reichen ...

Optimierungsmöglichkeiten:
1. Die möglichen Teilgraphen für zusammenhängende Gebiete mit mehreren S/W-Punkten oder Außenpunkten vorkalkulieren.
2. Bei der Auswahl des nächsten Nachbarn immer priorisiert am Rand langlaufen.
3. Teilstrecken die bestimmte s/w-Punkte isolieren frühzeitig erkennen und zum Backtracken nutzen.
4. Aufwendige Tests durch Tabellenzugriffe realisieren (Rechenkomplexität mit Speicherkomplexität ersetzen). Z.B lassen sich alle erlaubten Zustände und Bedingungen einer Zelle als Bits realisieren, die Implikation auf Nachbarzellen ließen sich wiederum als Bitmaske aus einer Tabelle ablesen, statt aufwendige if/then konstrukte zu durchlaufen.


Helfen die Überlegungen? :)