Sudoku

Sudoku ist ein Logikrätsel. Das Sudoku Puzzle besteht aus einem 9\times 9-Gitter, das wiederum in neun 3 \times 3-Blöcke unterteilt ist. Insgesamt gibt es 81 Felder. Diese sollen so gefüllt werden, dass die Ziffern von 1 bis 9

• in jeder Zeile,
• in der Spalte und
• in jedem Block

genau einmal vorkommen. Dabei sind bereits einige Zahlen so eingetragen, sodass jedes Sudoku eine eindeutige Lösung hat. Die Anzahl der voreingetragenen Zahlen und die Lösungsstategien, die angewendet werden müssen, bestimmen den Schwierigkeitsgrad des Sudokus.^[1]
Damit ein Sudoku eindeutig lösbar sein kann, müssen mindestens 17 Zahlen vorgegeben sein. Bisher gibt es keine mathematische Erklärung dafür, es wurde lediglich mit Hilfe eines Hitting Set Algorithmus von McGurie et al. gezeigt. ^[2]

Abb. 1 - Beispiel für die Lösung eines Sudokus Swiss Logic Puzzle Federation

Es gibt darüberhinaus weitere Varianten des Sudokus, die beispielsweise mehrere Quadrate miteinander verbinden oder größere Quadrate einbeziehen. ^[1:1]

Der folgende Artikel fokussiert sich auf die oben beschriebenen, klassischen Sudokus.

Herkunft

Das Spiel geht auf Leonard Eulers Latin Square aus dem 18. Jahrhundert zurück. Das heute bekannte Sudoku wurde von Howard Grans erstmals im Jahr 1979 in der us-amerikanischen Zeitschrift "Dell Pencil Puzzles & Word Games" veröffentlicht, damals unter dem Namen Number Place.
Bekannt wurde das Sudoku zwischen 1984 und 1986 in Japan, als es in der Japanischen Zeitschrift Nikoli regelmäßig abgedruckt wurde. Die Bezeichnung Sudoku, eine Abkürzung des ursprünglichen japanischen Namen „Sūji wa dokushin ni kagiru“, hat sich ab 1986 etabliert. Dieser Name beschreibt die Logik des Spiels, nämlich dass die jeweiligen Zahlen nur einmal vorkommen dürfen. ^[1:2]
In den 2000er Jahren verbreitete sich das Sudoku weltweit.^[3]

Anzahl möglicher Sudokus

Wenn jedes Feld mit einer der Ziffern von 1 bis 9 belegt werden würde, ergeben sich dafür 9⁸¹ Möglichkeiten. Wenn man nun alle Möglichkeiten eliminiert, die die Regeln des Sudokus verletzten, bleiben nach Bertram Felgenhauer und Frazer Jarvis nur noch 6.670.903.752.021.072.936.960 (ca. 6,7 Trilliarden oder 6,7 ⋅ 1021) vollständig ausgefüllte Sudokus übrig.
Man kann diese Zahl noch weiter reduzieren, indem man Symmetrien betrachtet und dadurch die Sudokus in einander überführt. Es ist hier nicht von Bedeutung, ob das Sudoku mit Ziffen, Symbolen oder Farben gefüllt wird. Man kann immer zwei Ziffern paarweise tauschen, ohne dass sich der Recht des Sudokus verändert. Das Gleiche gilt für das paarweise Vertauschen von zwei Zeilen, Spalten oder 3er Blockreihen. Man kann das Sudoku auch spiegeln oder drehen, ohne dass sich das Sudoku an sich verändert. Letztendlich bleiben dann nur noch 5.472.730.538 (5,5 Milliarden) verschiedene Sudokus übrig.^[4]

Lösungsstrategien

Das Lösen von Sudokus kann unterschiedlich angegangen werden:

• deterministische Algorithmen, wie Backtracking, Linear Integer Programming und Constraint Programming
• evolutionäre Algorithmen wie z.B. der Harmony Search Algorithmus

Literaturverzeichnis