Kakuro und Sudoku - Lösungsstrategien

Ein Kurzüberblick über einige Ansätze

Faszination Logikspiele und Zahlenrätsel

Sudoku

Sudoku läßt sich auf vielerlei Arten lösen, hier nur einige:
Backtracking: Beginnend mit dem ersten freien Feld probiert man systematisch, mit der Eins beginnend, ob man zu einer Lösung kommt. Beim ersten Widerspruch geht man zurück (backtrack). Dieser Lösungsweg lässt sich sehr elegant rekursiv formulieren, und man ist sicher, dass alle Kombinationsmöglichkeiten abgesucht werden. Da es sich um tausende Wege handeln kann, ist dieser Algorithmus nur für Computerprogramme geeignet. Der Lösungsalgorithmus ist sicher nur suboptimal, da er keinerlei analytische Vorinformationen verwendet und nur durch Ausprobieren vorgeht.

AnalyseDie zwei Hauptanalyseverfahren sind die Eliminierung (oder Kandidatenbeseitigung) und die Hypothese (oder "was-wenn"). In der Eliminierung kommt man damit vorwärts, dass man mehrmals hintereinander Kandidatenzahlen von einer oder mehreren Zellen beseitigt, um gerade eine Wahl zu lassen. Nachdem jede Antwort erzielt wurde, wird zur Überprüfung noch ein üblicher Scan durchgeführt, um die Auswirkung der neuesten Zahl zu sehen. Es gibt eine Vielzahl von Eliminierungstaktiken, die alle auf den einfachen oben genannten Regeln basieren, welche wichtige und nützliche logische Schlussfolgerungen beinhalten.

Kakuro

Die einfachste mathematische Überlegung, die man sich beim Lösen von Kakuro zunutze macht, ist folgende: für eine gegebene Anzahl Stellen (Felder) sind bestimmte Summen eindeutig bestimmt, die Zahl 6 lässt sich z.B nur durch eine Kombination der Zahlen 1, 2, 3 in drei Stellen darstellen. Die möglichen Kombinationen kann man sich erdenken oder vorgefertigten Tabellen entnehmen.
Folgende Zahlen besitzen nur eine einzige Zerlegung in zwei zulässige Summanden: 3 (1+2), 4 (1+3), 16 (7+9) und 17 (8+9).
Da in den Feldern des Kakuro nur die Ziffern 1 bis 9 eingetragen werden dürfen, hat zu einer gegebenen Anzahl Stellen deren Summe einen Maximalwert. Beispiel: Eine Reihe von vier Feldern hat maximal den Wert 30 = 9+8+7+6. Ebenso hat dieselbe Reihe von Feldern minimal den Wert 10 = 1+2+3+4. Dies funktioniert aber nur, wenn eine kleinere Zahl auf weniger Felder aufgeteilt wird. Da sich die Ziffern in einer Reihe nicht wiederholen dürfen, hat eine Reihe maximal neun Stellen und maximal den Wert 45 = 1+2+3+4+5+6+7+8+9.

Sudoku bei Wikipedia hier

Kakuro bei Wikipedia hier