¶ Allgemeines
Kakuro (auch bekannt als "Cross Sums") ist ein beliebtes japanisches Logikrätsel, das mathematisch zur Klasse der NP-vollständigen Probleme gehört. Kakuro wird dabei häufig in Zeitungen abgedruckt und analog gespielt, ähnlich wie das in Deutschland weitaus bekanntere Sudoku.
Im vorliegenden Paper[1] von Tristan Cazenave wird untersucht, wie Monte-Carlo-Methoden die traditionellen Suchverfahren verbessern können. Kakuro wird hierbei als Constraint Satisfaction Problem modelliert.
¶ Regeln
Abb. 1 - menschliche Lösung eines 7x7 Kakuro, selbst erstellt
Kakuro-Puzzle bestehen aus einer Mischung aus leeren Feldern, die es zu befüllen gilt und Hinweisfeldern die dem Spieler beim Finden der Lösung helfen. Ziel des Puzzles ist es, in jedem leeren Feld eine eindeutige Ziffer einzutragen. Dabei müssen folgende Constraints erfüllt werden:
- Ziffernbereich: Jedes leere Feld muss mit einer Ganzzahl zwischen 1 und 9 (oder zwischen 1 und N v.a. bei theoretischen Puzzles[2]) befüllt werden.
- Einzigartigkeit: Alle Ziffern innerhalb einer zusammenhängenden Zeile oder Spalte müssen unterschiedlich sein.
- Summen-Constraint: Die Summe in der jeweiligen Zeile bzw. Spalte muss exakt dem vorgegebenen Hinweiswert entsprechen.
¶ Komplexität
Mathematisch gesehen gehört Kakuro zur Klasse der NP-vollständigen Probleme[2:1]. Dies bedeutet, dass es nach aktuellem Kenntnisstand keinen Algorithmus gibt, der alle Kakuro-Rätsel in effizienter (polynomieller) Zeit lösen kann.
Die Komplexität eines spezifischen Kakuro-Rätsels wird primär durch zwei Faktoren bestimmt:
- Anteil der leeren Felder: Die Schwierigkeit nimmt mit der Anzahl der freien Variablen stetig zu. Während andere Rätsel oft bei einem mittleren Füllgrad am schwierigsten sind, stellen bei Kakuro vollständig leere Gitter (0 % vorgegebene Zahlen) die maximale Herausforderung für Suchalgorithmen dar.
- Anzahl der möglichen Werte: Die Komplexität verhält sich nicht linear zum Wertebereich. Experimente mit 8x8-Gittern zeigen, dass die Schwierigkeit zunächst mit der Anzahl der erlaubten Ziffern (z. B. von 1–9 auf 1–10) ansteigt. Ab einem gewissen Punkt nimmt die Schwierigkeit jedoch wieder ab, da bei sehr vielen möglichen Werten die Summen-Constraints leichter zu erfüllen sind.[1:1]
¶ Menschlicher Ansatz
Der menschliche Ansatz besteht im Wesentlichen darin, zuerst die Hinweiszahlen zu bearbeiten, die im Zusammenspiel mit den freien Feldern nur sehr wenige Kombinationen zulassen. Bei zwei freien Feldern gibt es beispielsweise die Summen 17, 16, 3 und 4, die jeweils aus einer eindeutigen Kombination aus Ziffern bestehen.
Durch die einfacheren Kombinationen erarbeitet man sich dann die Hinweise, um schwerere Zeilen/Spalten anzugehen.
¶ Algorithmische Ansätze
Abb. 3 - Lösung für 5x5 Kakuro, Abbildung aus dem Paper [1:2]
Abb. 2 - Ein quadratisches 5x5 Kakuro, Abbildung aus dem Paper [1:3]
Im Paper "Monte-Carlo Kakuro"[1:4] vergleicht der Autor Tristan Cazenave vier aufeinander aufbauende Ansätze, um als CSP modellierte Kakuro Puzzle zu lösen. Dabei werden ganz bewusst komplett leere, quadratische Kakuro Puzzle verwendet. Mit einem solchen Aufbau ist ein Kakuro für einen Menschen nahezu unlösbar, dafür werden dort die Unterschiede zwischen verschiedenen Algorithmen im Worst-Case-Szenario deutlich.
¶ Forward Checking
Dies ist eine Form der Tiefensuche (Depth First Search). Nach jeder Zuweisung einer Zahl wird der Wertebereich (Domain) der verbleibenden freien Variablen reduziert. Wenn eine Zuweisung dazu führt, dass ein Feld keine möglichen Werte mehr hat oder die Summe nicht mehr erreicht werden kann, wird der Pfad als inkonsistent verworfen.
¶ Iterative Sampling
Dieser Ansatz nutzt Forward Checking zur Aktualisierung der Wertebereiche, wählt dann aber wiederholt zufällige Zuweisungen (Samples) bis eine Lösung gefunden wurde oder keine Züge mehr möglich sind.
¶ Meta Monte-Carlo Search
Hierbei werden für alle möglichen Zuweisungen einer Variablen Testspiele (Samples) durchgeführt. Der Algorithmus wählt den Spielzug, der im anschließenden Sample den besten Score erzielt hat, und speichert die erfolgreichsten Sequenzen.
¶ Nested Monte-Carlo Search (Level 2)
Der Kern des Papers ist die Anwendung von Nested Monte Carlo Search. Dieser Algorithmus treibt den Meta-Ansatz weiter, indem er mehrere rekursive Ebenen (Level) benutzt. Dabei entspricht Level 1 im Wesentlichen der Meta Monte-Carlo Search. Im Gegensatz zu klassischen Algorithmen benötigt NMCS kein spezifisches Domänenwissen und ist somit breit anwendbar. Der Nested Monte Carlo Search Algorithmus benutzt rekursive Simulationen, um mögliche Züge zu bewerten. Dabei wird die Rekursionstiefe als "Level" bezeichnet.
Niedrigere Level simulieren ein ganzes Spiel um eine Bewertung abzugeben, höhere Level nutzen diese Bewertungen um eine Vorstellung zu bekommen, wie gut ein Spielzug ist.
Pseudocode[1:5]
int nested (level)
best score = number of free variables
while true
choose a free variable var
for all values in the domain of var
assign value to var
update the domains of the free variables
if a domain is empty or inconsistent then
score = 1 + number of free variables
else if level is 1
score = sample ()
else
score = nested (level - 1)
if score < best score then
best score = score
best sequence = {{var,value},level-1 sequence}
var = pop variable of the best sequence
value = pop value of the best sequence
assign value to var
update the domains of the free variables
if a domain is empty or inconsistent then
return 1 + number of free variables
if no free variable or best score equals 0 then
return 0
¶ Erläuterung des NMCS-Algorithmus
- Initialisierung: Der Algorithmus startet mit der Annahme, dass noch alle freien Felder gelöst werden müssen (best score = number of free variables). Ein Score von 0 bedeutet, dass eine vollständige Lösung gefunden wurde.
- Variablenauswahl: Es wird ein freies Feld (var) ausgewählt. Um die Effizienz zu steigern, nutzt Cazenave hier die Heuristik, das Feld mit dem kleinsten verbleibenden Wertebereich (Smallest Domain) zuerst zu wählen.
- Wert-Evaluation (Die Schleife): Für jede mögliche Ziffer (1–9) in diesem Feld wird eine Simulation gestartet.
- Level 1 (Basis): Hier wird eine einfache Zufallssimulation (sample) durchgeführt, um zu sehen, wie weit man mit diesem Zug kommt.
- Höhere Level (n): Der Algorithmus ruft sich selbst rekursiv auf einem niedrigeren Level (n−1) auf. Dadurch "lernt" das höhere Level aus den optimierten Ergebnissen des niedrigeren Levels.
- Sequenz-Speicherung: Wenn eine Simulation einen besseren Score (weniger verbleibende leere Felder) liefert als bisher bekannt, wird dieser Pfad als die neue best sequence gespeichert.
- Zugausführung: Nachdem alle Werte für ein Feld evaluiert wurden, führt der Algorithmus den besten gefundenen Zug der Sequenz tatsächlich aus und aktualisiert das Spielfeld permanent.
- Terminierung: Der Prozess wiederholt sich, bis entweder keine freien Felder mehr übrig sind (Erfolg, Return 0) oder ein unlösbarer Zustand erreicht wird.
¶ Die Bedeutung der Sequenz-Speicherung
Ein kritischer Aspekt des NMCS ist das Speichern der besten Sequenz. Findet eine Simulation auf einem niedrigeren Level einen Pfad, der besser als der bisherige Bestwert ist, wird diese gesamte Abfolge von Zügen auf das höhere Level übernommen. Dies verhindert, dass gute Lösungen durch spätere Zufallsentscheidungen "verloren" gehen
¶ Heuristiken bei der Variablenwahl
Obwohl NMCS auf Zufall basiert, nutzt Cazenave eine bewährte CSP-Heuristik: Bei der Entscheidung, welches Feld als nächstes befüllt wird, wählt der Algorithmus immer das Feld mit der kleinsten verbleibenden Domain (den wenigsten möglichen Ziffern). Die Ziffer selbst wird dann auf Basis der Monte-Carlo-Simulationen gewählt.
¶ Visualisierte Beispielausführung
Abb. 4 -Visualisierte Beispielausführung auf einem 5x5 Grid, selbst erstellt
¶ Andere Ansätze
Neben den von Cazenave untersuchten Monte-Carlo-Methoden gibt es spezialisierte mathematische und informatische Ansätze zur Lösung von Kakuro:
SAT-Solver[2:2]: Durch die Kodierung der Kakuro-Regeln in die Aussagenlogik können hochoptimierte Solver wie MiniSat oder GlueMiniSat verwendet werden. Dabei wird jedes Feld durch binäre Variablen repräsentiert, die angeben, welche Ziffer (1–9) enthalten ist.
Constraint Programming[3]: Da sich Kakuro als klassisches Constraint Satisfaction Problem modellieren lässt, können auch moderne Constraint-Programming Solver benutzt werden. Diese Solver nutzen Sprachen wie Copris oder Z3, um die "All-Different"- und "Sum"-Constraints effizient zu verarbeiten.
Genetische Algorithmen[4]: Diese nutzen evolutionäre Prinzipien (Mutation, Selektion), um Lösungskandidaten zu verbessern. Neuere Ansätze verwenden dynamische Mutationsraten, um lokale Optima zu vermeiden.
¶ Ergebnisse und Performance
In den Experimenten von Cazenave zeigt sich eine drastische Überlegenheit der NMCS gegenüber klassischen CSP-Lösern bei leeren Gittern.[1:6]
| Algorithmus | Gelöste 8x8 Gitter | Gesamtzeit (Sek.) |
|---|---|---|
| Nested Level 2 | 100 / 100 | 17,85 s |
| Nested Level 1 | 100 / 100 | 78,30 s |
| Iterative Sampling | 10 / 100 | 94.605,16 s |
| Forward Checking | 8 / 100 | 92.131,18 s |
Die Daten verdeutlichen, dass Kakuro mit steigender Anzahl leerer Felder (Holes) exponentiell schwieriger für Forward Checking wird, während NMCS Level 2 selbst leere 8x8 Grids effizient löst.
¶ Ausblick
Nested Monte Carlo Search schneidet von den vier verglichenen Algorithmen mit Abstand am besten ab. Ein systematischer Vergleich mit den anderen Ansätzen SAT-Solver, Constraint Programming und Metaheuristiken steht noch aus. Des Weiteren erwähnt Cazenave im Paper eine vielversprechende Richtung zur Verbesserung des Algorithmus. Wenn man NMCS mit besseren Konsistenzprüfungen (Domain Specific Knowledge) kombiniert, könnte die Effizienz der Simulationen gesteigert werden, indem unmögliche Werte frühzeitig weggeschnitten werden. (Pruning)
¶ Referenzen
Cazenave, Tristan. "Monte-carlo kakuro." Advances in Computer Games. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 45-54. researchgate ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Ruepp, Oliver, and Markus Holzer. "The computational complexity of the Kakuro puzzle, revisited." International Conference on Fun with Algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. ↩︎ ↩︎ ↩︎
Simonis, Helmut. "Kakuro as a constraint problem." Proc. seventh Int. Works. on Constraint Modelling and Reformulation (2008). ↩︎
Sexton, Aaron, Erik Anderson, and James Hereford. "An improved evolutionary strategy with dynamic mutation rate applied to kakuro puzzles." 2019 SoutheastCon. IEEE, 2019. ↩︎