Kakuro und Sudoku - Die Mathematik
Ein Kurzüberblick über die beiden beliebten Zahlenrätsel aus Japan.
Faszination Zahlen bei Sudoku
Die Zahl der möglichen 9 × 9-Sudokus beträgt nach einer Berechnung aus dem Jahre 2005 6.670.903.752.021.072.936.960 = 9! · 722 · 27 · 27.704.267.971; der letzte Faktor ist eine Primzahl. Es gibt immer noch 5.472.730.538 Möglichkeiten bei Berücksichtigung von Symmetrien. Die Zahl gültiger 16 × 16-Sudokus ist bis heute unbekannt. Die maximale Zahl von Vorgaben, die zu einer nicht-eindeutigen Lösung führen, ist, unabhängig von der Variante, um vier geringer als die Gesamtzahl aller Felder (normalerweise 77 bei der 9x9-Variante). Die Mindestzahl von Vorgaben, die zu einer eindeutigen Lösung führen – zu bestimmen ist bisher ein nicht gelöstes Problem. Die Mindestzahl, die bisher für die Standardvariante ohne Symmetrieforderung gefunden wurde, ist 17, bei drehsymmetrischer Anordnung sind es 18.
Lösungsmethodik bei Sudoku
Algorithmisch: Eine Lösungsmethode ist die Behandlung als Schnittmengenproblem. Aus den vorgegebenen Ziffern lässt sich für jedes Feld eine Menge von Kandidatenziffern bestimmen, die für ein Feld die Schnittmenge aus je drei Mengen ist: Diese sind die Komplemente der jeweils in derselben Zeile, Spalte und im selben Quadrat enthaltenen Ziffern zur Menge aller Ziffern (ohne die Null). In einfachen Fällen hat das Rätsel die Eigenschaft, dass mindestens ein Feld eine einelementige Kandidatenmenge besitzt, oder dass ein Element aus einer Kandidatenmenge eines Feldes nicht in den Kandidatenmengen aller anderen Felder derselben Spalte oder Zeile oder desselben Quadrats vorkommt. Dieser Kandidat kann dann fest in das jeweilige Feld eingesetzt werden und die betreffende Ziffer aus den Kandidatenmengen der übrigen Felder in derselben Zeile, Spalte und im selben Quadrat entfernt werden. Dieses Verfahren wird dann solange wiederholt, bis alle Zellen aufgefüllt sind. Bei den meisten eindeutig lösbaren Rätseln, insbesondere den schwierigen, führt diese Methode allein nicht zur Lösung. In diesen Fällen müssen z. B. Paare oder Tripel von Kandidaten gemeinsam betrachtet werden, um die Kandidatenmengen in einem ersten Schritt zu verkleinern. Hierbei werden logische Verknüpfungen zwischen mehreren Feldern gesucht, von denen klar ist, dass bestimmte Zahlen in den Feldern dieser Gruppe stehen, wodurch diese Zahlen für die nicht in der Gruppe befindliche als Lösungen ausscheiden (Beispiel: {1, 2} {2, 3} {3, 1}; wenn diese Kandidatenmengen z. B. in einer Reihe stehen, ist klar, dass diese Gruppe die Zahlen 1, 2 und 3 enthalten muss, wodurch sie aus allen anderen Kandidatenmengen in dieser Reihe ausscheiden). Alternativ kann, falls in einem Iterationsschritt keine einelementige Kandidatenmenge existiert, aus einer der (kleinsten) Kandidatenmengen eine Zahl ausgewählt werden, um eine der mehreren möglichen Lösungen zu erhalten (Versuch-und-Irrtum-Methode). In Lösungsprogrammen wird diese Methode wohl am häufigsten zu finden sein, da es in den meisten Fällen am Ende ökonomischer ist, die Brute-Force-Methode einzusetzen, als alle Felder auf Untergruppen zu überprüfen.
