¶ Shakashaka
¶ Allgemein
Shakashaka ist ein Logik-Puzzle, das vom japanischen Nikoli Verlag entwickelt wurde. Das Spielfeld ist ein rechteckiges Gitter, in welchem manche Felder schwarz gefärbt sind. Die schwarzen Felder können eine Zahl zwischen 0 und 4 enthalten.
Zum lösen des Puzzles müssen Teile der weißen Felder mit Dreiecken eingefärbt werden, sodass:
- Alle zusammenhängenden weißen Teile des Spielfelds rechteckig sind.
- Schwarze Felder mit Zahlen genau so viele direkte vertikale und horizontale Nachbarn wie angegeben haben.
Die Entscheidung ob eine Shakashaka-Instanz lösbar ist, ist NP-Vollständig. [1]
¶ Lösung mit Binary-Integer-Programming [1:1]
¶ Modell
Jedem Feld werden fünf Variablen zugewiesen. Eine für das Freilassen des Feldes und vier für alle möglichen Drehungen eines Dreiecks. Jede Variable kann den Wert 0 oder 1 annehmen. Eine Belegung mit 1 gibt an, dass das Feld entsprechend der Variable gefüllt wird.
Die Regeln des Puzzles werden mit den folgenden Regeln Modelliert.
¶ 1) Eine Belegung pro Feld
Für jedes weiße Feld gibt es die Bedingung, dass genau eine Variable mit 1 belegt werden muss.
Die Variablen werden für schwarze Felder auf 0 fixiert.
¶ 2) Schwarze Felder
An jedes schwarze Feld darf nur eine gefärbte Kante eines Dreiecks oder ein leeres Feld angrenzen.
Daraus ergibt sich diese Formel für das Feld direkt über einem Schwarzen. (das schwarze Feld befindet sich an Position (i, j))
Die Bedingung gilt analog für die drei anderen Richtungen.
Für schwarze Felder mit Zahl k muss die Anzahl der benachbarten Dreiecke genau k sein.
¶ 3) Kanten von weißen Rechtecken (45°)
Jede diagonale Kante eines weißen Rechtecks muss entweder gerade oder rechtwinklig fortgeführt werden.
Daraus ergeben sich die folgende Formeln:
Das größer-gleich Zeichen kann in der folgenden Bedingung als Implikation und das Plus als Disjunktion gelesen werden.
Damit eine Kante nur entweder gerade oder als Ecke fortgeführt wird, gibt es noch folgende Bedingung. In diesem Fall steht das Plus für eine Konjunktion.
Die Bedingungen gelten wieder analog für die anderen Richtungen.
¶ 4) Kanten von weißen Rechtecken (0°)
Mit den aktuellen Bedingungen kann es immernoch zu dem Fall kommen, dass die weißen Flächen, die von vertikalen und horizontalen Kanten abgeschlossen sind, konkav sind. Um das zu verhindern, müssen L-Formen aus leeren Feldern immer entweder mit einem weiteren leeren Feld oder der passenden Diagonale zu quadraten ergänzt werden.
Daraus ergibt sich die Bedingung:
Die Bedingung gilt auch wieder analog für die anderen Richtungen.
¶ 5) Schwarze Kästchen in weißen Rechtecken (45°)
In dem Paper von Erik D. Demaine ist außerdem noch eine Bedingung zu finden die den folgenden Fall ausschließen soll. Diese ist meiner Analyse nach aber überflüssig, da Bedingung 3) für das mittlere schwarze Quadrat verletzt wird.
Es gibt jedoch noch eine ähnlichen Fall der mit allen Bedingungen des Papers immernoch möglich ist:
Ob dieser in lösbaren Shakashaka-Instanzen auftreten kann ist mir aber nicht bekannt.