Einleitung

Kakuro (oder auch Cross Sums) ist ein altes Logikrätsel aus Japan. In vielen Zeitschriften, in denen Sudokus oder Kreuzworträtsel veröffentlicht werden sind auch Kakuro Rätsel zu finden. In der heutigen Zeit kann man außerdem auch ganz entspannt online auf Platformen wie zum Beispiel auf Janko an Kakuros, in verschiedenen Größen und Schwierigkeitsstufen, knobeln.

Regeln

Kakuro ist sehr einfach gehalten, es gibt nur drei Regeln:

1. Die weißen Felder müssen mit Zahlen zwischen 1 und 9 gefüllt werden.
2. Die schwarzen Felder geben die Summen an, die die Werte der weißen Felder in den Reihen links, bzw. den Spalten unter den jeweiligen schwarzen Feldern aufsummiert ergeben müssen.
3. In den Summen darf jede Zahl nur ein einziges mal vorkommen.

Ein Kakuro Puzzel ist dabei immer eindeutig lösbar.

^[1]

Komplexität

Das Problem der Kakuro Puzzel wurde in The Computational Complexity of the Kakuro Puzzle, Revisited ^[2] als NP-Komplett bewiesen. Damit werden die Kakuro Rätsel für Informatiker umso spannender. Wir wollen uns im Weiteren damit beschäftigen, wie wir trotz der Komplexität einen effizienten Lösungsweg entwickeln können.

Constraint Satisfaction Problem

Der simple Aufbau und den einzigen drei Regeln machen die Kakuro Puzzel sehr geeignet, um sie als Constraint Satisfaction Problem zu modellieren und mit Constraint Programming effizient eine Lösung zu suchen. Die Grundlagen des Constraint Programming werden auf der Wiki-Seite für Constraint Programming erklärt.

Zuerst wollen wir ein Kakuro Puzzel als ein Paar von zwei Mengen definieren <G,H>. Die Menge:

G=\{x_1,...,x_i\}

stellt die Menge der weißen, zu befüllenden, Felder dar. Die Menge:

H=\{<v_1,I_1>,...,<v_j,I_j>\}

definiert die durch die schwarzen Felder vorgegebenen Summen. Dabei gibt v den Wert der Summe und I \subset G den Block über den die Summe geht vor.

Kakuro, mit einem nxn Spielfeld als Constraint Satisfaction Problem, wie im angegben Wiki als Tripel <X,D,C>, zu modellieren definieren wir die Mengen der:

1. Variablen X=G, die die weißen Felder darstellen, die gefüllt werden müssen.
2. Domänen D=\{[1,9],...,[1,9]\}, jede Variable, bzw. jedes weiße Feld kann mit Zahlen zwischen 1 und 9 belegt werden.
3. Constraints C, die die drei Grundregeln modellieren.

Die Regel, dass alle weißen Felder mit Zahlen zwischen 1 und 9 belegt werden können haben wir schon durch die Domänen defieniert. Die weiten zwei Regeln wollen wir durch folgenden zwei Constraints definieren:

1. Vorgegebenen Summen müssen eingehalten werden:

\forall_{<I,v> \in H}:\sum_{i \in I}x_i=v

2. Die Werte in den Summen sollen alle einzigartig sein:

\forall_{<I,v> \in H}: alldifferent(\{x_i|i \in I\})

alldifferent ist dabei ein globaler Constraint, welches die meisten Constraint Solver von besitzen und wie der name schon beschreibt modelliert, dass alle Werte der gegeben Menge eindeutig seien müssen:

alldifferent(x_1,...,x_n) := \{(d_1,...,d_n) | d_i \neq d_j \  for \  i \neq j\}

Mit dieser Definition haben wir ein Constraint Satisfaction Problem modelliert und können nun mit dem Suchalgorithmus eines Constraint Solver auf effizienter Weise eine Lösungsmenge suchen.

^[3]

Auswertung

In Kakuro as a constraint problem^[3:1] wird ein Kakuro Puzzel wie oben beschrieben in der Constraint Logic Programming Plattform ECLiPSe^[4] als Constraint Satisfaction Problem modelliert und gegen verschieden Mengen an Kakuro Puzzeln getestet.

Schema:
Set: Getestetes Set an Puzzel
X, Y: Größe der Puzzel
K: Größe des Set
Setup: Prozent der nach dem Setup gelösten Puzzel
Shave: Prozent der nach dem Shaving gelösten Puzzel
Total: Prozent der gelösten Puzzel - begrenzt auf 500.000 Knoten in der Suche
Avg Time: Durchnittliche gebrauchte Zeit
Max Time: Maximal gebrauchte Zeit
Avg Back: Durchschnittlich gebrauchte Backtracking-Schritte
Max Back: Maximal gebrauchte Backtracking-Schritte
n/a: Es gab kein erfolgreichen Durchlauf

Im ersten Durchlauf wurde ein reiner Backtracking-Algorithmus ohne jegliche Optimierung genutzt. Es wird deutlich, dass dieser Ansatz nicht effizient ist und für viele größeren Puzzel gar keine Löung innerhalb der Grenze gefunden wird.

Im zweiten Durchlauf wird die Suche durch die Domänreduktion des Forward Checking genutzt, wodurch der Suchbaum stark reduziert wird und eine deutliche Steigerung in der Effizienz erreicht wird. Bis auf das größte Kakuro wird nun für alle Puzzeln eine Lösung gefunden.

Im dritten Durchlauf wird das globale alldifferent Constraint genutzt, um wie es im MAC Algorithmus beschrieben wird die Domänen weiter zu reduzieren. Damit können nun alle Puzzel gelöst werden und - bis auf das gößte - auch extrem effizient.

Referenzen

Abbildungen

• Abbildung 1: Aus den Beispielen von Janko ^[1:1]
• Abbildung 2: Aus den Beispielen von Janko ^[1:2]
• Abbildung 3,4,5: Aus Kakuro as a constraint problem ^[3:2]