Nurikabe ist ein deterministisches Puzzle, das 1991 erstmals von Nikoli, einem japanischen Herausgeber von Puzzlespielen - besonders bekannt für Sudoku -, publiziert wurde.
¶ Namensgebung
Der Name des Puzzles ist auf einen japanischen Geist - oder genauer Yōkai - der japanischen Folklore zurückzuführen. Dieser manifestiert sich nachts als unsichtbare, unüberwindbare Wand und versperrt Leuten den Weg. Dieses Sinnbild der unüberwindbaren Wand wird im Puzzle aufgegriffen.
Ein Gemälde eines Nurikabe-Yōkai[1]
¶ Regeln
- Die Startfelder der Inseln dürfen nicht eingefärbt werden.
- Je Insel gibt es genau ein Startfeld, insbesondere berühren sich keine zwei Inseln horizontal oder vertikal.
- Es gibt nur eine Wand, die durchgehend horizontal oder vertikal verbunden ist.
- Es gibt keine 2x2-Blöcke aus schwarzen Wandfeldern.
Die Lösung eines Nurikabe ist eindeutig.
¶ Inseln im Strom
Die Erläuterung der Spielregeln, die die schwarzen Felder als Wand bezeichnet, ist naheliegend in Bezug auf den namensgebenden Yōkai. Andere Erklärungsversuche bezeichnen die eingefärbten Felder als (Fluss-)Strom, daher ist das Spiel teilweise auch als Inseln im Strom (Islands in the Stream) bekannt. Die Veranschaulichung der vierten Regel ist bei Inseln im Strom intuitiver: 2x2-Blöcke aus eingefärbten Feldern werden hier als Teich bezeichnet.[2]
¶ Lösungsansätze
Es gibt eine Reihe von mehr oder weniger involvierten Lösungsansätzen. Im Folgenden wird exemplarisch ein relativ einfaches Nurikabe-Puzzle schrittweise gelöst. Die Darstellungen des Koordinaten-Puzzlefelds sind übernommen von Holzer et al[3].
- Zunächst wird das Puzzle für Erklärungszwecke mit Koordinaten versehen:
- Da sich Inseln nicht berühren dürfen, werden Felder eingefärbt, die zwischen zwei Inseln liegen. Die Insel der Größe 1 auf
e3hat bereits ihre Endgröße erreicht, daher werden alle vier berührenden Felder eingefärbt:
- Die Inseln auf den Positionen
a1undc6sollen zwei Felder groß sein. Sie können jeweils nur noch ein Feld in eine einzige Richtung wachsen, daher sind diese Inseln fertig gelöst und die angrenzenden Felder (a3,b2undb5,c4,d5) werden eingefärbt:
- Die Insel auf
b7hat lediglich eine Möglichkeit, sich auf fünf Felder auszubreiten. Sie reicht daher bisa4und ist fertig gelöst. Es wirdb4eingefärbt, da das Feld an die Insel grenzt.d4ist eingeschlossen von Wandfeldern, wird also auch eingefärbt:
- Nun fällt auf, dass
c3nicht eingefärbt werden darf, da sonst ein 2x2-großer Wandbereich entstehen würde. Dementsprechend muss die Insel aufc1überc2bisc3reichen, es werden also die angrenzenden Felderb3,d1undd2eingefärbt:
- Es fallen erneut zwei 2x2-Wandbereich-Kandidaten auf:
e5muss zu einer Insel gehören, wobei nur die Insel aufe6in Frage kommt, da sich die Felder berühren. Wir können alsoe7,f5undf6einfärben. Dad7von Wandfeldern eingeschlossen wäre, wird es auch eingefärbt.
Ebenso musse1zu einer Insel gehören, hierfür kommt nur die Insel aufg2in Frage. Die Insel muss über das Feldg1wachsen, dag1sonst ein Wandfeld wäre, das nicht mehr mit dem Rest der Wand verbunden ist. Daher werdenf2undg3eingefärbt:
- Lediglich die Insel auf
f4ist noch nicht komplettiert. Sie kann nur in eine Richtung wachsen. Es wirdf7undg7eingefärbt und das Puzzle ist gelöst:
¶ Komplexität
Nurikabe ist NP-vollständig. Holzer et al haben nachgewiesen, dass Nurikabe selbst mit Inselgrößen von maximal zwei Feldern NP-vollständig ist. Darüber hinaus haben sie bewiesen, dass NP-Vollständigkeit weiterhin gegeben ist, wenn man eine oder beide der Regeln 3 und 4 streicht, also
- die Wand muss nicht durchgehend verbunden sein,
und/oder
- 2x2 Blöcke aus schwarzen Wandfeldern dürfen vorhanden sein,
erlaubt[3:1]. Anzumerken ist, dass die Lösung eines Nurikabe-Puzzles in diesen Fällen nicht mehr eindeutig ist - veranschaulicht wird dies durch folgende Grafik von Holzer et al, die verschiedene mögliche Lösungen, je nach Relaxationsgrad der Regeln, präsentiert:
Hierbei entspricht (b) den gängigen Regeln, in (c) ist die Wand nicht mehr durchgehend verbunden, in (d) gibt es einen 2x2-Wandbereich, in (e) ist sowohl die Wand nicht mehr durchgehend verbunden als auch ein 2x2-Wandbereich vorhanden.
¶ Lösungsansatz per Ant Colony Optimization
Basierend auf einem von Lloyd und Amos entwickelten Ant Colony Optimization-Algorithmus zum Lösen von Sudoku[4], haben Amos et al einen adaptierten Algorithmus für das Lösen von Nurikabe entworfen[5].
¶ Pseudocode
read in puzzle grid ;
initialize global pheromone matrix ;
while puzzle is not solved do
for each ant do
give ant local copy of grid ;
assign ant to random starting island ;
colour black all non-numbered cells in local grid ;
end
while all ants not finished do
for each ant do
if all islands not filled to target size
then
create list, N, of all cells surrounding current island ;
remove from N any cut cells ;
remove from N any cells adjacent to another island ;
if possible, select a cell from N, and add to current island (and update local pheromone) ;
if current island is target size or N is empty then
move to next island ;
end
end
else
mark ant as finished ;
end
end
end
find best ant ;
do global pheromone update ;
do best value evaporation ;
end
Pseudocode übernommen aus [5:1].
¶ Parameter
Folgende feste Parameter werden für den Algorithmus auf einem großen Nurikabe-Feld benötigt. Die genaue Bedeutung erschließt sich aus der darauf folgenden detaillierten Beschreibung des Algorithmus.:
, die Anzahl der Ameisen, die pro Iteration einen Lösungskandidaten erstellen.
, der Initialwert der globalen Pheromonmatrix.
, der Parameter des lokalen Pheromonupdates.
, der Parameter des globalen Pheromonupdates.
, der Gier-Paramter.
, der Best Value Evaporation-Parameter.
Zwei weitere dynamische Werte des bis zur aktuellen Iteration jeweils besten Lösungskandidatens werden gespeichert:
, der Pheromonbonus des aktuell besten Lösungskandidatens, sowie
dessen Inselfeldbelegung.
¶ Initialisierung
Vor Beginn der Iterationen wird die globale Pheromonmatrix initialisiert. Diese hat die identische Dimension des Puzzles und weist dem korrespondierenden Puzzlefeld einen Pheromonwert zu. Der Initialwert ist . Die Einträge der Matrix werden im Folgenden durchnummeriert adressiert, d.h. entspricht dem ersten Eintrag (1,1) der Matrix, mit dem letzten Eintrag (m,n).
In jeder Iteration starten die Ameisen mit lokalen Kopien des Puzzles. Diese Kopie besteht aus dem Puzzlefeld, wobei jedes Feld außer den Inselstartfeldern schwarz eingefärbt ist. Die Ameisen versuchen nun, die Inseln auf ihre eigentliche Größe wachsen zu lassen, indem sie Wandfelder durch Inselfelder ersetzen. Die Lösung wird also rückwärts erschlossen, konträr zu den gängigen Lösungsansätzen für Menschen.
¶ Äußere Schleife, Teil 1
Jede Ameise wird auf eine zufällige Insel ihres Puzzlefelds gesetzt.
¶ Innere Schleife
¶ Erstellung der Kandidatenliste
Falls die Insel noch nicht die Zielgröße erreicht hat, erstellt die Ameise eine Liste aller an die Insel angrenzenden Felder. Die Liste der möglichen Felder wird nun durch Pruning so gefiltert, dass zwei mögliche Regelverstöße nicht auftreten können:
- Entferne alle Felder, die eine andere Insel berühren würden.
- Entferne alle Felder, die die Wand in zwei Bereiche trennen würden.
Folgendes Beispiel zeigt die Kandidatenliste, grün gefärbt, für die Insel oben rechts vor dem Pruning. Beim Pruning würden zunächst die an die benachbarte Insel grenzenden mit a und b markierten Felder entfernt werden. Daraufhin würde das mit c markierte Feld ebenso entfernt werden, da es die Wand zerteilen würde - das mit b markierte Feld wäre ein isoliertes Wandfeld.
¶ Wahl des Feldes
Falls die finale Liste leer ist, es also kein mögliches Feld gibt, ist die Insel abgearbeitet, auch wenn sie noch nicht die eigentliche Zielgröße erreicht hat. Andernfalls wird aus der Liste nun ein Feld gewählt. Falls es mehr als ein mögliches Feld gibt, gibt es zwei Ansätze:
- Gieriger Ansatz
Es wird der Pheromonwert der Felder in der globalen Pheromonmatrix verglichen und das Feld mit dem höchsten Wert gewählt. Für die Liste möglicher Felder gilt also:
- Gewichteter Ansatz
Damit nicht stehts die gierige Wahl getroffen wird, wurde vor dem Start des Algorithmus der Gier-Parameter festgelegt. Für jede Feldwahl wird eine zufällige Zahl generiert. Falls , wird die gierige Wahl getroffen, der höhere Pheromonwert entscheidet also. Andernfalls entscheidet der Zufall. Hierfür wird der Pheromonwert der Zellen aufsummiert. Der relative Anteil jedes Feldes bestimmt die Chance, dass das Feld gewählt wird. Die Chance, dass Feld i innerhalb der Liste möglicher Felder gewählt wird, lautet also:
¶ Lokales Pheromonupdate
Nach der Wahl eines Feldes wird ein lokales Pheromonupdate angestoßen. Hierfür wurde der Parameter festgelegt (der Standardwert von Ant Colony System-Algorithmen ist 0.1). Der neue Pheromonwert lautet
dieser überschreibt den alten Wert in der global Pheromonmatrix. Andere Ameisen, die ab jetzt vor einer ähnlichen Feldwahl stehen, sind weniger dazu geneigt, dieselbe Wahl zu treffen.
Falls die Insel weiterhin nicht die geforderte Größe erreicht hat, startet die innere Schleife erneut bei der Erstellung der Kandidatenliste angrenzender Felder. Andernfalls ist die Insel abgearbeitet und die Ameise fährt fort mit der nächsten Insel.
¶ Auswahl der nächsten Insel
Die Auswahl der nächsten Insel hat Auswirkungen auf die Effektivität des Algorithmus. Analysiert wurden sechs verschiedene Auswahlverfahren, siehe Abschnitt Resultate:
- Die Inseln wurden basierend auf einem Raster-Scan sortiert, d.h. zeilenweise von oben links nach unten rechts.
- Die Inseln wurden zufällig sortiert.
- Die Inseln wurden der Größe nach absteigend sortiert.
- Die Inseln wurden der Größe nach aufsteigend sortiert.
- Bei jedem Wechsel zu einer neuen Insel wurde die nach Manhattan-Distanz am weiten entfernteste gewählt
- Oder zuletzt, ebenso basierend auf der Manhattan-Distanz, die jeweils nahste Insel.
¶ Äußere Schleife, Teil 2
¶ Auswertung der Lösungskandidaten
Nach Abschluss der inneren Schleifen, d.h. wenn alle Ameisen jeweils alle Inseln abgearbeitet haben, wird die Qualität der Lösungskandidaten bewertet. Hierfür wird eine Kostenfunktion angewandt, die die Anzahl an Regelverstößen - also die Anzahl an 2x2-Wandfeldern sowie die Differenz aus den Inselfeldern des Lösungskandidaten und der eigentlich geforderten Anzahl an Inselfeldern - zählt. Ist die Kostenfunktion eines Kandidatens 0, wurde die Lösung gefunden und der Algorithmus ist beendet.
Aus dem Kehrwert der Kostenfunktion wird der Pheromonbonus jedes Lösungskandidatens bestimmt. Je weniger Regelverstöße, desto höher ist also der Pheromonbonus. Das Maximum der aktuellen Iteration wird mit dem bisherigen besten Wert vergleichen. Falls er höher ist und sich die Inselfeldbelegung des Lösungskandidatens von unterscheidet, werden beide Werte aktualisiert.
Der Kostenfunktionswert des folgenden Beispiels beträgt 4, da bei dieesem Lösungskandidat ein 2x2-Wandfeld vorhanden ist und statt 5+5+3+2+2 = 17 lediglich 5+2+3+2+2 = 14 Inselfelder vorhanden sind, also insgesamt 1+(17-14)=4 Regelverstöße.
¶ Globales Pheromonupdate
Nun wird das globale Pheromonupdate durchgeführt. Hierfür wird jedes Feld der Inselbelegung des aktuell besten Lösungskandidatens - d.h. aus dieser oder einer vorherigen Iteration - mit extra Pheromon belohnt. Der festgelegte Parameter entscheidet, wie stark der Pheromonbonus ausfällt:
¶ Best Value Evaporation
Bevor die nächste Iteration starten kann, kommt es noch zu einer Besonderheit, die bereits von Lloyd und Amos für das Lösen von Sudoku[4:1] verwendet wurde. Hierbei wird der Parameter um den Faktor abgeschwächt um frühe Konvergenz zu vermeiden, siehe nächster Abschnitt:
¶ Verfrühte Konvergenz
Verfrühte Konvergenz auf suboptimale lokale Minima erster Lösungskandidaten sind ein gängiges Problem bei ACO-basierten Algorithmen.[6]
Um dieses Problem abzuschwächen, kommen wie erwähnt drei Methoden zum Einsatz.
-
Der gewichtete Ansatz bei der Wahl zwischen mehreren möglichen Feldern. Dadurch, dass nicht stets die gierige Wahl getroffen wird, kommt es zu diverseren Lösungskandidaten.
-
Die lokalen Pheromonupdates nach jeder Wahl eines Feldes. Dies unterstützt zusätzlich die Diversität der Lösungskandidaten innerhalb einer Iteration, da für nachfolgende Entscheidungen die anderen Felder durch einen nun relativ höheren Pheromonanteil an Attraktivität gewinnen - insbesondere bei der gewichteten Wahl.
-
Die Best Value Evaporation nach jeder Iteration. Diese ermöglicht, dass nach mehreren stagnierenden Iterationen ohne einen neuen, besseren Lösungskandidaten ein eigentlich schlechterer Lösungskandidat als beste bisherige Lösung gewählt werden kann. Somit werden möglicherweise neue Lösungspfade erschlossen.
¶ Resultate
Der ACO-Algorithmus wurde verglichen mit einem constraint-basierten Copris-Solver[7].
Der Algorithmus wurde auf einem einzelnen Kern eines Xeon E5-2640 v4 2.40 GHz Prozessors auf Ubuntu ausgeführt. Sowhol der ACO-Algorithmus als auch der Copris-Solver laufen auf einer Java Virtual Machine, wobei der Copris-Solver auf einen in C kompilierten SAT-Solver für die Constraints zurückgreift.
¶ Instanzen
908[8] eindeutig lösbare Puzzleinstanzen mit einer Größe von 9 bis 2500 Feldern wurden analysiert.
¶ Parameter
Jede Instanz wurde 100x pro Inselauswahlsverfahren mit einem Zeitlimit von jeweils 60 Sekunden durchlaufen.
Folgende Parameterwerte wurden genutzt:
, , , und .
¶ Vergleich der Selektionsschemata
Tabelle übernommen aus [5:2].
Schemata:
0: Rasterscan,
1: Zufall,
2: der Größe nach absteigend,
3: der Größe nach aufsteigend,
4: weiteste Manhattan-Distanz,
5: kürzeste Manhattan-Distanz.
Instance size entspricht der Anzahl der Felder.
ist die Anzahl der Instanzen.
ist die Anzahl der Instanzen, die mindestens einmal während der 100 Durchläufe gelöst wurde.
ist der gesamte Anteil der erfolgreichen Durchläufe.
Da Nurikabe ein komplexes Puzzle ist, liegt es Nahe, dass man im Voraus keine optimale, generalisierte Reihenfolge der Inselauswahl treffen kann. Dies wird sehr deutlich durch die klare Überlegenheit der zufälligen Auswahl (70% Erfolgsrate) im Vergleich zu vorsortierten Selektionen (unter 61%). Des Weiteren fällt auf, dass die Erfolgschance in großen Instanzen rapide abfällt.
¶ Vergleich mit dem Copris-Solver
Tabelle übernommen aus [5:3].
zählt die Anzahl an Instanzen, in denen sowohl ACS als auch SAT eine Lösung gefunden haben.
bzw zählt die gelösten Instanzen, in denen der jeweils andere Solver keine Lösung gefunden hat.
zählt die Anzahl an Instanzen, in denen der SAT-Solver schneller zum Ergebnis gekommen ist als der ACS-Algorithmus.
Es wird deutlich, dass der ACS-Algorithmus in kleinen Instanzen bis zu 99 Feldern in knapp 75% der Fälle schneller die Lösung findet. In mittleren Instanzen bis zu 199 Feldern dreht sich das Blatt, hier findet der SAT-Solver häufiger (56%) eine schnellere Lösung. In noch größeren Instanzen kommen die Schwächen des ACS-Algorithmus zu Tage - hier findet der SAT-Solver sowohl deutlich mehr Lösungen und in den Instanzen, in denen beide eine Lösung finden, ist der SAT-Solver fast immer schneller.
Die Autoren heben zudem hervor, dass der ACS-Algorithmus nahezu keine heuristische Informationen und nur die Puzzleregeln benötigt um eine Lösung zu finden.
¶ Referenzen
(ぬりかべ) from Bakemono no e (化物之繪, c. 1700), Harry F. Bruning Collection of Japanese Books and Manuscripts, L. Tom Perry Special Collections, Harold B. Lee Library, Brigham Young University. ↩︎
https://web.archive.org/web/20230202100250/https://de.wikipedia.org/wiki/Nurikabe ↩︎
Holzer, Markus, Andreas Klein, and Martin Kutrib. On the NP-completeness of the Nurikabe pencil puzzle and variants thereof. Proceedings of the 3rd International Conference on FUN with Algorithms. 2004. ↩︎ ↩︎
Lloyd, Huw, and Martyn Amos. Solving Sudoku with ant colony optimization. IEEE Transactions on Games 12(3) 2019: 302-311. pdf ↩︎ ↩︎
Amos, Martyn, Matthew Crossley, and Huw LLoyd (2019). Solving nurikabe with ant colony optimization (extended version). Extended version of a short paper presented at the Genetic and Evolutionary Computation Conference (GECCO), July 13-17 2019, Prague. pdf | original, unextended pdf ↩︎ ↩︎ ↩︎ ↩︎
Dorigo, M. and Stützle, T. (2004) Ant Colony Optimization. The MIT Press, Cambridge, ISBN 9780262256032; p. 117 ↩︎
Naoyuki Tamura. Copris-basierter Nurikabe-Solver https://cspsat.gitlab.io/copris-puzzles/nurikabe/ ↩︎
Angela Janko and Otto Janko. Nurikabe Instanzen, verfügbar auf https://www.janko.at/Raetsel/Nurikabe/. ↩︎