Sudoku Sudoku sieht wie ein Zahlenspiel aus, aber die Ziffern sind keine Mengen. Im klassischen Sudoku ist 8 nicht größer als 3; beide sind nur verschiedene Symbole.
Die eigentliche Mathematik liegt in den sich überschneidenden Bedingungen. Jede Zelle gehört zu einer Zeile, einer Spalte und einem Block. Lösen heißt beweisen, welche Platzierungen noch möglich sind.
Die Mathematik des Sudoku besteht vor allem aus Kombinatorik, Logik und Bedingungen. Ein 9x9-Sudoku verlangt, die Ziffern 1 bis 9 so zu setzen, dass jede Zeile, Spalte und jeder 3x3-Block jede Ziffer genau einmal enthält.
Ist Sudoku wirklich Mathematik?
Ja, aber nicht wegen der Ziffern. Die Ziffern sind Etiketten und könnten durch Buchstaben oder Farben ersetzt werden.
Klassisches Sudoku ist ein Logikproblem: Bedingungen einhalten und ermitteln, welche Werte erzwungen sind.
Die Mathematik des Sudoku umfasst daher Permutationen, Bedingungen, Symmetrien, Beweise und Eindeutigkeit.
Aufbau des 9x9-Gitters
Ein Standardgitter hat 81 Zellen: 9 Zeilen und 9 Spalten, gruppiert in neun 3x3-Blöcke.
Es gibt 27 Häuser: 9 Zeilen, 9 Spalten und 9 Blöcke. Jedes Haus enthält die Ziffern 1 bis 9 genau einmal.
Jede Zelle gehört zu drei Häusern. Diese Überlappung erzeugt die logische Kraft des Rätsels.
Sudoku in Zahlen
| Thema | Zahl oder Idee | Bedeutung |
|---|---|---|
| Größe | 9x9 | 81 Zellen |
| Symbole | Ziffern 1-9 | Etiketten, keine Mengen |
| Häuser | Zeilen, Spalten, Blöcke | 27 insgesamt |
| Regel | Jede Ziffer einmal | In jedem Haus |
| Modell | Constraint Satisfaction | Auch Exact Cover |
| Vollständige Gitter | 6,670,903,752,021,072,936,960 | Gültige 9x9-Lösungen |
| Wesentliche Gitter | 5,472,730,538 | Nach Symmetrien |
| Minimum Hinweise | 17 | Für eindeutige Lösung |
Das Bedingungssystem
Eine Lösung erfüllt vier Forderungen: eine Ziffer pro Zelle, jede Ziffer einmal pro Zeile, einmal pro Spalte und einmal pro Block.
Formal kann man Sudoku mit 324 exakten Bedingungen modellieren: 81 Zell-, 81 Zeilen-Ziffer-, 81 Spalten-Ziffer- und 81 Block-Ziffer-Bedingungen.
Ein Kandidat wie Zeile 4, Spalte 7, Ziffer 9 erfüllt vier Bedingungen zugleich.
Wie viele Gitter sind möglich?
Es gibt 6,670,903,752,021,072,936,960 vollständige 9x9-Sudoku-Lösungsgitter.
Nach Abzug üblicher Symmetrien bleiben 5,472,730,538 wesentlich verschiedene Gitter.
Der Lösungsraum ist riesig, aber die Regeln sind stark genug für Rätsel mit genau einer Antwort.
Hinweise, Eindeutigkeit und Schwierigkeit
Ein Rätsel beginnt mit Hinweisen. Mathematisch reduzieren sie alle möglichen Lösungen auf genau eine.
Gute Rätsel bewahren Eindeutigkeit und bieten einen interessanten logischen Weg.
Das Minimum für ein klassisches Sudoku mit eindeutiger Lösung liegt bei 17 Hinweisen; 16 reichen nicht aus.
Die Logik des Lösens
Menschliche Techniken sind kleine Beweise. Ein Naked Single zeigt, dass eine Zelle nur noch einen Kandidaten hat.
Paare, Tripel, gesperrte Kandidaten, Fischmuster, Wings und Ketten sind fortgeschrittene Formen derselben Idee.
Praktisch wird das in unserem Leitfaden zu Sudoku-Techniken.
Sudoku als Exact-Cover-Problem
Computer können Sudoku in ein Exact-Cover-Problem verwandeln: Platzierungen werden so gewählt, dass jede Bedingung genau einmal erfüllt ist.
Donald Knuths Algorithm X mit Dancing Links ist eine bekannte Methode; Backtracking mit Bedingungsweitergabe ist ebenfalls üblich.
Normale 9x9-Gitter sind schnell lösbar, verallgemeinerte Sudokus auf größeren Brettern sind jedoch NP-vollständig.
Symmetrien und Transformationen
Man kann Zeilen innerhalb eines Bandes, Spalten innerhalb eines Stapels oder ganze Bänder tauschen, drehen, spiegeln oder Ziffern umbenennen.
Wenn alle 1er zu 7ern und alle 7er zu 1ern werden, bleibt die Lösung gültig.
Diese Symmetrien helfen beim Zählen von Gittern und beim Erzeugen ausgeglichener Hinweisbilder.
Math Sudoku, Killer Sudoku und Calcudoku
Die Suchintention ist wichtig. Mathematik des Sudoku meint meist die Theorie des klassischen Sudoku. Math Sudoku kann Rechenvarianten meinen.
Für Summen probieren Sie Killer Sudoku. Für eine stärker arithmetische Variante probieren Sie Calcudoku.
Im klassischen Sudoku liegt die Mathematik in den Bedingungen; in diesen Varianten ist Rechnen Teil der sichtbaren Regeln.
Sudoku ist mathematisch, weil man beweist, was erzwungen ist, nicht weil man rechnet.
Das ist die Eleganz von Sudoku: neun einfache Symbole, ein kleines Gitter und genug Struktur für sehr viel Logik.
Häufig gestellte Fragen
Kombinatorik, Logik, Constraint Satisfaction, Exact Cover, Symmetrien und verwandte Ideen.
Nein. Im klassischen Sudoku sind Ziffern Symbole, keine Mengen.
6,670,903,752,021,072,936,960 vollständige Lösungen oder 5,472,730,538 wesentlich verschiedene Gitter.
Für ein eindeutiges klassisches Sudoku sind mindestens 17 Hinweise nötig.
Nicht unbedingt. Math Sudoku meint oft Rechenvarianten wie Killer Sudoku oder Calcudoku.