Die Mathematik des Sudoku
Ein Sudoku-Gitter ist ein kleines mathematisches Objekt, und über es ist viel bewiesen worden. Hier sind die wichtigsten Ergebnisse, vom einfachsten zum tiefsten, jedes mit seinem Beweis: vollständig, wenn er in wenige Zeilen passt, als Idee, wenn er einen langen Artikel oder einen Computer brauchte.
Direkte Äquivalenz
Sudoku ist ein Graphenfärbungsproblem
Satz. Ein Sudoku zu lösen heißt, einen Graphen mit 81 Knoten mit 9 Farben zu färben und dabei die Farben einzuhalten, die die Vorgaben festlegen. Jeder Knoten hat genau 20 Nachbarn.
Nehmen wir einen Knoten pro Feld und verbinden zwei Knoten, wenn ihre Felder eine Zeile, eine Spalte oder einen Block teilen. Die neun Ziffern werden zu neun Farben, und den Graphen zu färben heißt, jedem Knoten eine Farbe zu geben, ohne dass zwei Nachbarn dieselbe haben.
Beweis
Von einer Lösung zu einer Färbung: Jeder Knoten bekommt die Farbe der Ziffer seines Feldes. Zwei benachbarte Felder teilen eine Zeile, eine Spalte oder einen Block, enthalten also verschiedene Ziffern, und ihre Knoten bekommen verschiedene Farben.
Von einer Färbung zu einer Lösung: Die neun Felder einer Zeile sind alle miteinander benachbart und brauchen daher neun verschiedene Farben. Da es nur neun gibt, kommt jede genau einmal in der Zeile vor. Dasselbe gilt für jede Spalte und jeden Block: Liest man die Farben wieder als Ziffern, erhält man eine Lösung.
Die Nachbarn gezählt
Ein Feld hat 8 andere Felder in seiner Zeile, 8 in seiner Spalte und 8 in seinem Block. Aber 2 Felder seines Blocks liegen auch in seiner Zeile und 2 in seiner Spalte: Sie wurden doppelt gezählt.
8 + 8 + 8 − 2 − 2 = 20
Der Graph hat also 81 × 20 ÷ 2 = 810 Kanten, jede von ihren beiden Enden aus gezählt. Und da eine Zeile neun Farben braucht und neun genügen, braucht der Graph genau neun: Seine chromatische Zahl ist 9.
In My Sudoku
So gesehen ist ein Nackter Single ein Knoten, dessen 20 Nachbarn schon 8 der 9 Farben verwenden: Ihm bleibt nur eine.
Quelle: Wikipedia: Mathematics of Sudoku.
Logische Kodierung
Sudoku ist ein Problem der exakten Überdeckung
Satz. Eine Sudoku-Lösung ist eine Auswahl von 81 Zeilen aus den 729 Zeilen einer 0-1-Matrix mit 324 Spalten, die jede Spalte genau einmal überdeckt.
Jeder Zug im Sudoku setzt eine Ziffer d in ein Feld (z, s), und jede Setzung erfüllt vier Bedingungen auf einmal:
- Feld: Das Feld (z, s) enthält eine Ziffer;
- Zeile: Die Ziffer d steht in Zeile z;
- Spalte: Die Ziffer d steht in Spalte s;
- Block: Die Ziffer d steht im Block von (z, s).
Jede Art kommt 81-mal vor: 81 Felder, und 9 Ziffern für jede der 9 Zeilen, der 9 Spalten und der 9 Blöcke.
4 × 81 = 324 Bedingungen · 81 × 9 = 729 Setzungen
Schreiben wir eine Matrix mit einer Zeile pro Setzung und einer Spalte pro Bedingung, mit einer 1, wo die Setzung die Bedingung erfüllt. Jede Zeile enthält genau vier Einsen. Eine 7 in Z2S5 zu setzen, überdeckt zum Beispiel vier Spalten:
- Feld Z2S5
- eine 7 in Zeile 2
- eine 7 in Spalte 5
- eine 7 in Block 2
Beweis
Eine exakte Überdeckung wählt Zeilen der Matrix so, dass jede Spalte unter ihnen genau eine 1 hat. Die 81 Feldbedingungen geben jedem Feld genau eine Ziffer; die Zeilen-, Spalten- und Blockbedingungen setzen jede Ziffer genau einmal in jede Zeile, jede Spalte und jeden Block. Das ist eine Sudoku-Lösung, und umgekehrt erfüllen die 81 Setzungen einer Lösung jede Bedingung einmal. Die Vorgaben sind im Voraus gewählte Zeilen.
exakte Überdeckung ⟺ Lösung: 81 von 729 Zeilen
In My Sudoku
Viele Lösungsprogramme arbeiten mit dieser Form, darunter Donald Knuths Algorithmus X mit seinen Dancing Links („tanzenden Verweisen“): Sie verzweigen immer bei der Bedingung mit den wenigsten verbleibenden Möglichkeiten. Die Suche von My Sudoku macht es mit den Feldbedingungen genauso: Sie probiert zuerst das Feld mit den wenigsten möglichen Ziffern.
Die Matrix zeigt auch, dass die beiden Singles eine einzige Idee sind: Ein Nackter Single ist eine Feldbedingung, ein Versteckter Single eine Zeilen-, Spalten- oder Blockbedingung, der nur noch eine Setzung bleibt. In beiden Fällen eine Spalte mit einer einzigen 1.
Quellen: Donald E. Knuth, Dancing Links (2000), Wikipedia: Mathematics of Sudoku.
Zählung per Computer, mit Symmetrien
Es gibt 6.670.903.752.021.072.936.960 Gitter
Satz. Es gibt genau 6.670.903.752.021.072.936.960 Möglichkeiten, ein 9 × 9-Gitter nach den Regeln auszufüllen, rund 6,67 × 10²¹. Lässt man Symmetrien außer Acht, sind 5.472.730.538 davon wesentlich verschieden.
Bertram Felgenhauer und Frazer Jarvis zählten sie 2005; Ed Russell und Frazer Jarvis zählten kurz darauf die wesentlich verschiedenen.
Warum nicht (9!)⁹?
Jede Zeile lässt sich auf 9! = 362.880 Arten ordnen, man könnte also (9!)⁹ Gitter erwarten, rund 1,1 × 10⁵⁰. Doch diese Zahl zählt beliebige neun übereinandergelegte Zeilen, mit Ziffern, die sich in Spalten und Blöcken wiederholen: Die Bedingungen sind nicht unabhängig, und die wahre Zahl ist viel kleiner.
Ein nachprüfbarer Teil: ein Vielfaches von 9!
Benennen wir die Ziffern eines Gitters um: Jede 1 wird zur 5, jede 5 zur 2 und so weiter, nach einer der 9! Arten, die neun Ziffern zu vertauschen. Jede Zeile, jede Spalte und jeder Block enthält weiterhin jede Ziffer einmal: Das Ergebnis ist wieder ein Gitter. Zwei verschiedene Umbenennungen eines Gitters ergeben zwei verschiedene Gitter, und ein umbenanntes Gitter erneut umzubenennen ergibt eines derselben Familie. Die Gitter zerfallen also in Familien von genau 9! Gittern, und ihre Zahl ist ein Vielfaches von 9!:
6.670.903.752.021.072.936.960 = 9! × 18.383.222.420.692.992
Wie gezählt wurde
Felgenhauer und Jarvis legten den ersten Block auf 1 bis 9 in Leserichtung fest, was den Faktor 9! erklärt, und zählten die Möglichkeiten, die ersten drei Zeilen zu vervollständigen: 2.612.736, also 56 × 6⁶. Viele davon gleichen sich, weil eine durch Vertauschen von Spalten oder Umbenennen von Ziffern in eine andere übergeht, und lassen sich auf ebenso viele Arten vervollständigen; nachdem sie sie gruppiert hatten, ließen sie für jede Gruppe einen Computer die Möglichkeiten zählen, die letzten sechs Zeilen auszufüllen. Die Gesamtzahl zerlegt sich so, ihr letzter Faktor ist eine Primzahl:
9! × 72² × 2⁷ × 27.704.267.971
Wesentlich verschiedene Gitter
Ein Gitter an seiner Diagonale zu spiegeln, zwei Bänder oder zwei Stapel von Blöcken, zwei Zeilen eines Bandes oder zwei Spalten eines Stapels zu vertauschen oder seine Ziffern umzubenennen, ergibt ein Gitter, das im Grunde dasselbe ist. Diese Operationen bilden eine Gruppe mit 9! × 3.359.232 Elementen. Teilt man die Zahl dadurch, erhält man rund 5.472.448.000: nahe dran, aber falsch. Einige Gitter sind symmetrisch und bleiben bei einer Operation unverändert; ihre Familie ist deshalb kleiner als die Gruppe, und die Division zählt sie zu wenig. Das Lemma von Burnside, das die Gitter zählt, die jede Operation unverändert lässt, berichtigt das:
5.472.730.538 wesentlich verschiedene Gitter
Dieselbe Zählung von Hand, für 4 × 4
| 1 | 2 | 3 | 4 |
| 3 | 4 | 1 | 2 |
| 2 | 1 | 4 | 3 |
| 4 | 3 | 2 | 1 |
Mit vier Ziffern und 2 × 2-Blöcken passt die ganze Zählung in wenige Zeilen. Füllen wir den ersten Block: 4! = 24 Arten, und nach Umbenennen der Ziffern dürfen wir annehmen, dass er 1 2 / 3 4 lautet. Der Rest von Zeile 1 enthält dann 3 und 4, der Rest von Zeile 2 enthält 1 und 2, in der einen oder anderen Reihenfolge: 4 Arten. Ebenso der Rest der Spalten 1 und 2: 4 Arten. Von diesen 16 Kombinationen lassen 12 genau eine Möglichkeit, den letzten Block zu füllen, und 4 keine:
24 × 12 = 288 Gitter
Unter den lateinischen Quadraten
Ein Gitter ist ein lateinisches Quadrat der Ordnung 9, jede Ziffer einmal pro Zeile und Spalte, mit der Blockregel obendrauf. Es gibt 5.524.751.496.156.892.842.531.225.600 lateinische Quadrate der Ordnung 9: Die Blöcke lassen nur etwa eines von 828.000 übrig.
Quellen: Frazer Jarvis, Sudoku enumeration problems, OEIS A002860, Wikipedia: Mathematics of Sudoku.
Beweis in wenigen Zeilen
Die Vorgaben zeigen mindestens acht verschiedene Ziffern
Satz. In einem Sudoku mit eindeutiger Lösung kommen mindestens acht der neun Ziffern unter den Vorgaben vor.
Acht verschiedene Ziffern, wohlgemerkt, nicht acht Vorgaben.
Beweis
Angenommen, zwei Ziffern, etwa 4 und 7, kommen unter den Vorgaben nicht vor. Nehmen wir eine Lösung und vertauschen darin überall 4 und 7.
Jede Zeile enthielt eine 4 und eine 7 und enthält sie weiterhin: Sie haben nur die Plätze getauscht. Dasselbe gilt für jede Spalte und jeden Block, also ist das neue Gitter ebenfalls eine Lösung. Es unterscheidet sich vom ersten überall, wo eine 4 oder eine 7 stand, und hält alle Vorgaben ein, denn keine ist eine 4 oder eine 7. Das Rätsel hätte zwei Lösungen. Unter den Vorgaben darf also höchstens eine Ziffer fehlen.
Genau an der Grenze
Das Rätsel mit 17 Vorgaben weiter unten liegt genau an der Grenze: Seine Vorgaben zeigen acht Ziffern, keine 6.
Auf einem N × N-Gitter verlangt dasselbe Argument N − 1 verschiedene Symbole unter den Vorgaben.
Quelle: Wikipedia: Mathematics of Sudoku.
Beweis durch Konstruktion
Vier Felder können ein Rätsel verderben
Satz. Enthalten vier Felder an den Ecken eines Rechtecks, in zwei Zeilen, zwei Spalten und zwei Blöcken, in einer Lösung a b / b a und ist keines davon eine Vorgabe, dann hat das Rätsel eine zweite Lösung.
Beweis
| a | b |
| b | a |
| b | a |
| a | b |
Vertauschen wir a und b in den vier Feldern. Jede der beiden Zeilen enthält weiterhin ein a und ein b, ebenso jede der beiden Spalten. Die vier Felder liegen paarweise in zwei Blöcken, und jedes Paar enthält ein a und ein b: Nach dem Tausch stimmen die Blöcke weiterhin. Sonst ändert sich nichts: Das neue Gitter ist ebenfalls eine Lösung und hält alle Vorgaben ein, denn keines der vier Felder ist eine.
Unvermeidbare Mengen
Eine solche Menge von Feldern, von denen mindestens eines eine Vorgabe sein muss, heißt unvermeidbare Menge. Hier hat ein Rätsel mit 77 Vorgaben, nur vier leeren Feldern, zwei Lösungen: Die Zahl der Vorgaben sagt wenig, ihre Lage viel.
Nie weniger als vier Felder
Umgekehrt unterscheiden sich zwei verschiedene Lösungen desselben Rätsels immer in mindestens vier Feldern. Ein Rätsel mit 78 oder mehr Vorgaben hat also nie zwei Lösungen, und das Rechteck ist die kleinste Mehrdeutigkeit, die es gibt.
Betrachten wir die Felder, in denen sich die beiden Lösungen unterscheiden. Eine Zeile kann nicht nur eines davon enthalten: Ihre acht anderen Felder enthielten in beiden Lösungen dieselben acht Ziffern, und für das letzte bliebe dieselbe neunte. Eine Zeile oder Spalte, die eines dieser Felder enthält, enthält also mindestens zwei. Nehmen wir eines, x. Seine Zeile enthält ein weiteres, y; seine Spalte ein weiteres, z; und die Zeile von z ein weiteres, w. Dieses Feld w ist weder x, das nicht in der Zeile von z liegt, noch y, das in der Zeile von x liegt. Das sind vier verschiedene Felder.
In My Sudoku
Die Technik Unique Rectangle dreht das um: Da ein richtiges Rätsel nur eine Lösung hat, kann ein solches Rechteck nie entstehen, und die Kandidaten, die es bilden würden, lassen sich streichen.
Quelle: Wikipedia: Mathematics of Sudoku.
Vollständiger Computerbeweis
Ein Rätsel braucht mindestens 17 Vorgaben
Satz. Ein 9 × 9-Sudoku mit eindeutiger Lösung hat mindestens 17 Vorgaben. Es gibt welche mit 17, keines mit 16.
Gary McGuire, Bastian Tugemann und Gilles Civario bewiesen es 2012 durch eine vollständige Computersuche. Zehntausende Rätsel mit 17 Vorgaben sind bekannt.
Idee des Beweises
Der Beweis beruht auf den oben gesehenen unvermeidbaren Mengen: Mengen von Feldern eines Gitters, die die Vorgaben treffen müssen, sonst ließen sich ihre Ziffern zu einer zweiten Lösung umordnen. Vorgaben, die ein Gitter festlegen, müssen jede seiner unvermeidbaren Mengen treffen: Sie bilden eine Treffermenge (hitting set) dieser Familie. Die Suche lief so ab:
- für jedes der 5.472.730.538 wesentlich verschiedenen Gitter viele seiner unvermeidbaren Mengen finden;
- alle Mengen von 16 Feldern aufzählen, die sie alle treffen, der schwierige Teil, für den die Autoren einen neuen Algorithmus entwarfen;
- prüfen, ob die Ziffern des Gitters in diesen 16 Feldern es festlegen;
- das war nie der Fall.
Es ist ein echter Beweis, aber einer, den nur ein Computer führen kann: Von Hand könnte ihn niemand nachprüfen.
Derselbe Beweis im Kleinen
Auf 4 × 4-Gittern ist dieselbe Suche winzig. Unter den 288 Gittern wird keines durch 3 seiner Felder festgelegt, manche aber durch 4: Das Minimum ist dort 4, was ein Computer in einem Augenblick prüft, indem er alle Fälle durchgeht.
Minimal ist nicht kleinstmöglich
Ein Rätsel ist minimal, wenn das Entfernen einer beliebigen Vorgabe eine zweite Lösung zulässt, und kleinstmöglich, wenn kein Rätsel weniger Vorgaben hat: 17. Ein Rätsel kann mit 25 Vorgaben minimal sein, ohne dass eine davon wegfallen kann, während andere Rätsel mit weniger auskommen.
Abgesehen von denen der Stufe Sehr leicht sind die Rätsel von My Sudoku minimal: Es füllt ein Gitter zufällig und entfernt dann die Vorgaben einzeln in zufälliger Reihenfolge, wobei es jede zurücksetzt, deren Entfernen eine zweite Lösung zulässt. Seine Rätsel haben am Ende meist 22 bis 27 Vorgaben.
Quellen: Gary McGuire, Bastian Tugemann, Gilles Civario, There is no 16-Clue Sudoku (2012), Wikipedia: Mathematics of Sudoku.
Beweis durch Reduktion
Sudoku ist NP-vollständig
Satz. Zu entscheiden, ob ein teilweise ausgefülltes Sudoku mit n² × n² Feldern und Blöcken von n × n eine Lösung hat, ist ein NP-vollständiges Problem.
Takayuki Yato und Takahiro Seta bewiesen es 2003, ausgehend von lateinischen Quadraten. Ein Problem ist NP-vollständig, wenn es zwei Eigenschaften hat: Es liegt in NP, das heißt, eine vorgeschlagene Lösung lässt sich schnell prüfen, und es ist NP-schwer, das heißt, jedes Problem in NP lässt sich in Polynomialzeit darauf zurückführen. Der Beweis hat zwei Teile.
Teil A: Sudoku liegt in NP
Nehmen wir ein ausgefülltes Gitter mit Seitenlänge N = n². Um es zu prüfen, geht man seine N Zeilen, N Spalten und N Blöcke durch und vergleicht es mit den Vorgaben. Zu prüfen, ob eine Zeile jedes Symbol von 1 bis N einmal enthält, kostet etwa N Schritte; die Zeilen kosten also etwa N × N, ebenso die Spalten und die Blöcke:
3 × N × O(N) = O(N²)
Das ist eine Zahl von Schritten proportional zu den N² Feldern des Gitters. Eine Lösung zu finden, kann schwer sein; eine zu prüfen, geht schnell.
Teil B: Sudoku ist NP-schwer
Ein lateinisches Quadrat der Ordnung N füllt ein N × N-Gitter mit N Symbolen, jedes einmal pro Zeile und Spalte: die Sudoku-Regeln ohne die Blöcke.
| 1 | 2 | 3 |
| 2 | 3 | 1 |
| 3 | 1 | 2 |
Charles Colbourn bewies 1984, dass es NP-vollständig ist zu entscheiden, ob sich ein teilweise ausgefülltes lateinisches Quadrat vervollständigen lässt. Yato und Seta verwandeln jedes teilweise ausgefüllte lateinische Quadrat L in Polynomialzeit in ein teilweise ausgefülltes Sudoku S(L): Die Vorgaben von S(L) sind so angeordnet, dass sich seine freien Felder nur so füllen lassen, wie L vervollständigt werden kann. Jede Vervollständigung von L ergibt genau eine Lösung von S(L) und umgekehrt (eine parsimonische Reduktion):
L lässt sich vervollständigen ⟺ S(L) hat eine Lösung
Ein schnelles Verfahren für Sudoku ergäbe also ein schnelles Verfahren für lateinische Quadrate. Da das Vervollständigen lateinischer Quadrate NP-vollständig ist, ist Sudoku NP-schwer; mit Teil A ist es NP-vollständig.
Was es nicht bedeutet
Es bedeutet nicht, dass 9 × 9-Rätsel schwer sind: Ihre Größe ist fest, und ein Computer löst jedes in einem Augenblick. Die NP-Vollständigkeit betrifft die ganze Familie, wenn n wächst: Man kennt kein Verfahren, das jedes Gitter in einer Zeit löst, die polynomiell in seiner Größe ist, und eines zu finden, bewiese P = NP, eine der großen offenen Fragen der Mathematik, auf deren Lösung das Clay-Institut eine Million Dollar ausgesetzt hat.
Eine zweite Lösung: ASP-vollständig
Yato und Seta beweisen mehr: Bei gegebenem Sudoku und einer seiner Lösungen zu entscheiden, ob es eine weitere gibt, ist genauso schwer. Das Problem ist ASP-vollständig (vom englischen Another Solution Problem, „Problem einer weiteren Lösung“). Das ist die Frage, vor der jeder Rätselmacher steht, denn ein richtiges Rätsel hat genau eine Lösung.
Deshalb überlässt der Generator von My Sudoku nichts dem Zufall: Nach jeder Vorgabe, die er entfernt, prüft eine Suche, ob es eine zweite Lösung gibt, und hält bei der ersten an; findet sie eine, kommt die Vorgabe zurück.
Quellen: Takayuki Yato, Takahiro Seta, Complexity and Completeness of Finding Another Solution and Its Application to Puzzles, IEICE Transactions on Fundamentals E86-A (2003), Charles J. Colbourn, The complexity of completing partial Latin squares (1984), Wikipedia: Mathematics of Sudoku.
Kurz gesagt
| Ergebnis | Art des Beweises |
|---|---|
| Sudoku ist ein Graphenfärbungsproblem | Direkte Äquivalenz |
| Sudoku ist ein Problem der exakten Überdeckung | Logische Kodierung |
| Es gibt 6.670.903.752.021.072.936.960 Gitter | Zählung per Computer, mit Symmetrien |
| Die Vorgaben zeigen mindestens acht verschiedene Ziffern | Beweis in wenigen Zeilen |
| Vier Felder können ein Rätsel verderben | Beweis durch Konstruktion |
| Ein Rätsel braucht mindestens 17 Vorgaben | Vollständiger Computerbeweis |
| Sudoku ist NP-vollständig | Beweis durch Reduktion |