Sudoku-Enzyklopädie · Mathematik und Informatik

Die Mathematik von Sudoku

Aktualisiert am 2026-10-05

Ein lateinisches Quadrat mit Blöcken

In einem lateinischen Quadrat kommt jedes Symbol in jeder Zeile und jeder Spalte einmal vor. Ein vollständig ausgefülltes Sudoku ist ein lateinisches Quadrat der Größe 9 mit einer zusätzlichen Bedingung: Auch jeder der neun 3×3-Blöcke enthält jede Ziffer einmal.

Quellen: Wikipedia: Latin square

Wie viele Raster es gibt

Bertram Felgenhauer und Frazer Jarvis zählten 2005 die vollständig ausgefüllten 9×9-Raster: Es gibt 6.670.903.752.021.072.936.960, etwa 6,67 × 10²¹. Viele davon sind dasselbe Raster in anderer Gestalt. Zählt man zwei Raster als eines, wenn sich das eine durch Umbenennen der Ziffern, Drehen, Spiegeln oder durch solche Umordnungen von Zeilen und Spalten, die die Gültigkeit des Rasters erhalten, in das andere überführen lässt, bleiben 5.472.730.538 wesentlich verschiedene Raster übrig. Diese Zahl berechneten Ed Russell und Frazer Jarvis.

Quellen: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Das Minimum von 17 Vorgaben

Kein Standard-Sudoku im Format 9×9 mit 16 oder weniger Vorgaben hat genau eine Lösung. Gary McGuire, Bastian Tugemann und Gilles Civario zeigten dies durch eine vollständige Computersuche und gaben das Ergebnis im Januar 2012 bekannt. Siebzehn ist das Minimum, keine Garantie: Viele Raster mit 17 Vorgaben haben dennoch mehr als eine Lösung.

Quellen: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku als Graphenfärbung

Zeichne für jede der 81 Zellen einen Punkt und verbinde zwei Punkte immer dann, wenn ihre Zellen in derselben Zeile, Spalte oder demselben Block liegen. Dieser Sudoku-Graph hat 810 Verbindungen, und jeder Punkt hat genau 20 Nachbarn. Das Rätsel zu lösen bedeutet, die durch die Vorgaben festgelegten Farben so zu erweitern, dass verbundene Punkte niemals dieselbe Farbe haben. Mindestens neun Farben sind nötig, weil jede Zeile, Spalte und jeder Block eine Gruppe aus neun Punkten bildet, die alle miteinander verbunden sind. Jedes vollständig ausgefüllte Raster zeigt, dass neun Farben ausreichen.

Quellen: Wikipedia: Sudoku graph

Im Allgemeinen schwer, bei 9×9 schnell

Für Sudoku-Raster, die beliebig groß werden können (n²×n² mit n×n-Blöcken), ist die Entscheidung, ob ein teilweise ausgefülltes Raster vervollständigt werden kann, NP-vollständig. Dieses Ergebnis veröffentlichten Takayuki Yato und Takahiro Seta 2003. Effiziente Computerprogramme lösen gewöhnliche 9×9-Rätsel typischerweise in einem Bruchteil einer Sekunde, wobei die Dauer vom Programm, vom Computer und vom Rätsel abhängt.

Quellen: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Siehe auch

Quellen

Alle Artikel →