Sudoku verwendet Zahlen, ist aber kein Rechenrätsel.
Um ein klassisches Raster zu lösen, musst du keine Summen, Produkte oder Formeln berechnen.
Die Ziffern 1–9 funktionieren hauptsächlich als neun verschiedene Symbole.
Mathematisch interessant wird Sudoku durch die Struktur um diese Symbole:
- Kombinatorik;
- lateinische Quadrate;
- Constraint Satisfaction;
- Exact Cover;
- konfliktbasierte Graphbeziehungen;
- Symmetrie;
- Suche;
- Enumeration.
Diese Struktur erklärt zugleich, warum Sudoku so einfach zu definieren ist und trotzdem einen enormen Lösungsraum besitzt.
Sudoku als eingeschränktes lateinisches Quadrat
Ein lateinisches Quadrat der Ordnung 9 ist eine 9×9-Anordnung von neun Symbolen, in der jedes Symbol in jeder Zeile und jeder Spalte genau einmal vorkommt.
Ein vollständig gelöstes klassisches Sudoku erfüllt diese beiden Bedingungen plus die 3×3-Blockbedingung.
Also:
Jedes vollständige klassische Sudoku ist ein lateinisches Quadrat mit zusätzlichen Blockbedingungen.
Aber:
Nicht jedes 9×9-lateinische Quadrat ist ein gültiges Sudoku-Raster.
Diese Beziehung ist mathematisch wichtig.
Historisch sollte daraus jedoch nicht die falsche Aussage entstehen:
„Euler erfand Sudoku.“
Lateinische Quadrate gehören zur mathematischen Vorgeschichte.
Die direkte moderne Rätselgeschichte wird separat in Geschichte des Sudoku behandelt.
Constraint Satisfaction
Sudoku ist ein natürliches Constraint-Satisfaction-Problem.
Stell dir jede Zelle als Variable vor.
Eine ungelöste Zelle kann zunächst den Bereich:
{1,2,3,4,5,6,7,8,9}
besitzen.
Vorgaben und Partnerbeziehungen verkleinern diese Domains.
Beispiel:
r4c7 Kandidaten
{2,5,8}Wird in einer Partnerzelle die 5 gesetzt, kann sie aus dieser Menge entfernt werden.
Spielerseitig heißt das Kandidatenaktualisierung.
Im CSP-Modell ist es Constraint Propagation.
Sudoku als Exact Cover
Ein klassisches Sudoku lässt sich auch als Exact-Cover-Problem formulieren.
Eine vollständige Lösung muss mehrere Bedingungsfamilien exakt erfüllen:
- jede Zelle erhält genau eine Ziffer;
- jede Zeile enthält jede Ziffer genau einmal;
- jede Spalte enthält jede Ziffer genau einmal;
- jeder Block enthält jede Ziffer genau einmal.
Jede mögliche Eintragung rNcM = d erfüllt eine bestimmte Kombination dieser Bedingungen.
Eine Sudoku-Lösung entspricht dann einer Auswahl von Eintragungen, die sämtliche Bedingungen exakt einmal abdeckt.
Diese Darstellung ist besonders nützlich für vollständige Solver und Lösungzählung.
Sudoku als graphartiges Problem
Sudoku lässt sich außerdem als Konfliktnetz betrachten.
Zellen oder Kandidatenzustände sind Knoten.
Beziehungen können ausdrücken:
Diese beiden Zustände dürfen nicht gleichzeitig wahr sein.
Genau diese Idee taucht beim manuellen Lösen wieder auf als:
- Partnerzellen;
- Weak Links;
- Strong Links;
- Chains.
Die formale Darstellung ist anders, aber dieselbe Constraint-Struktur bleibt erhalten.
Suche und Backtracking
Ein vollständiger Solver kann rekursive Suche verwenden.
Ein grober Ablauf:
- eine ungelöste Zelle auswählen;
- einen Kandidaten ausprobieren;
- Constraints propagieren;
- bei Widerspruch zurückgehen;
- weiter suchen, bis Lösungen gefunden sind.
Mit geeigneter Zellwahl und früher Constraint Propagation kann dies sehr effizient sein.
Ein solcher Solver beantwortet Fragen wie:
- existiert eine Lösung?
- existiert mehr als eine?
- welche vollständige Lösung passt zu den Vorgaben?
Das ist eine andere Aufgabe als ein Human-Style-Solver, der einen erklärbaren Lösungsweg mit benannten Techniken erzeugt.
Wie viele vollständige Sudoku-Raster gibt es?
Für klassische 9×9-Sudoku beträgt die Zahl vollständiger gültiger Raster:
6.670.903.752.021.072.936.960
ungefähr:
6,671 × 10²¹
Bertram Felgenhauer und Frazer Jarvis veröffentlichten eine Enumeration dieses Lösungsraums.
Diese Zahl behandelt durch Symmetrien oder Ziffernumbenennung verwandte Raster zunächst als unterschiedliche vollständige Raster.
Wesentlich verschiedene Raster
Viele vollständige Sudoku lassen sich ineinander überführen durch gültigkeitserhaltende Transformationen, zum Beispiel:
- Umbenennen der Ziffern;
- Vertauschen von Zeilen innerhalb eines Bands;
- Vertauschen von Spalten innerhalb eines Stacks;
- Vertauschen ganzer Bands oder Stacks;
- Transposition;
- weitere Kombinationen dieser Symmetrien.
Fasst man Raster unter der Standard-Sudoku-Symmetriegruppe zusammen, bleiben:
5.472.730.538
wesentlich verschiedene vollständige Raster.
Das sind immer noch Milliarden.
Warum diese Zahlen nicht der Zahl möglicher Sudoku-Rätsel entsprechen
Ein vollständiges Lösungsraster ist nur der Ausgangspunkt.
Aus demselben Raster können sehr viele unterschiedliche Vorgabenmengen gewählt werden.
Einige davon:
- besitzen keine eindeutige Lösung;
- andere sind minimal;
- andere enthalten redundante Vorgaben;
- andere erzeugen unterschiedliche Schwierigkeitsgrade und Lösungswege.
Darum ist:
Zahl der vollständigen Raster
nicht dasselbe wie:
Zahl aller möglichen veröffentlichten Sudoku-Rätsel.
Symmetrie bei der Rätselerzeugung
Mathematische Symmetrie
Transformationen können vollständige gültige Raster auf andere gültige Raster abbilden.
Symmetrie der Vorgabenanordnung
Ein Konstrukteur kann Vorgaben zum Beispiel rotationssymmetrisch anordnen.
Diese zweite Form ist hauptsächlich eine ästhetische oder redaktionelle Entscheidung.
Sie ist keine klassische Sudoku-Regel.
Kombinatorik und Vorgabenauswahl
Ein Generator muss aus 81 Zellpositionen eine Vorgabenmenge auswählen.
Die Zahl möglicher Teilmengen ist riesig.
Aber nur ein kleiner Teil davon besitzt gleichzeitig die gewünschten Eigenschaften:
- konsistent;
- eindeutig;
- mit dem Zieltechnikset menschenähnlich lösbar;
- passend kalibriert;
- redaktionell brauchbar.
Darum ist Sudoku-Erzeugung ein Such- und Validierungsproblem.
Minimale Vorgabenzahl als Extremalproblem
Die Frage:
Wie wenige Vorgaben kann ein eindeutiges klassisches Sudoku besitzen?
ist ein mathematisches Extremalproblem.
Die bewiesene Antwort lautet 17.
Diese Grenze sagt nichts darüber aus, wie schwierig oder elegant ein bestimmtes 17-Vorgaben-Sudoku ist.
Schwierigkeit als Human-Computing-Problem
Ein vollständiger Solver kann ein Rätsel rechnerisch sehr schnell lösen, das für einen Menschen schwierig wirkt.
Darum ist die Laufzeit eines Backtracking-Solvers kein gutes menschliches Schwierigkeitsmaß.
Ein besseres Modell untersucht:
- benötigte menschliche Techniken;
- Anzahl und Reihenfolge der Schritte;
- Abhängigkeiten zwischen ihnen;
- Erkennungsaufwand;
- Spielerdaten.
Warum verschiedene Sudoku-Solver verschiedene Aufgaben erfüllen
Vollständiger Solver / Lösungzähler
Beantwortet:
- existiert eine Lösung?
- existiert genau eine?
- welche vollständigen Lösungen gibt es?
Human-Style-Solver
Erzeugt:
- benannte Schritte;
- erklärbare Eliminierungen;
- einen nachvollziehbaren Lösungsweg;
- Material für Schwierigkeitsanalyse.
Generator
Kombiniert:
- Lösungsraster;
- Vorgabenauswahl;
- Eindeutigkeitsprüfung;
- Human-Style-Analyse;
- Difficulty Rating;
- Qualitätsfilter.
Ein einziges Verfahren muss nicht alle drei Aufgaben übernehmen.
FAQ
Basiert Sudoku auf Arithmetik?
Nein. Die Ziffern funktionieren hauptsächlich als unterschiedliche Symbole.
Ist jedes Sudoku ein lateinisches Quadrat?
Jedes vollständig gelöste klassische Sudoku-Raster ist ein lateinisches Quadrat mit zusätzlichen Blockbedingungen.
Ist jedes lateinische Quadrat ein Sudoku?
Nein.
Wie viele vollständige klassische Sudoku-Raster gibt es?
6.670.903.752.021.072.936.960.
Warum gibt es „nur“ ungefähr 5,47 Milliarden wesentlich verschiedene Raster?
Weil sehr viele vollständige Raster unter Ziffernumbenennung und gültigkeitserhaltenden Sudoku-Symmetrien äquivalent sind.
Macht der riesige Lösungsraum Sudoku automatisch schwierig?
Nein. Schwierigkeit entsteht aus dem konkreten Startzustand und seinem menschlichen Lösungsweg.
Was du als Nächstes lernen solltest
Lies Wie Sudoku erzeugt werden für die praktische Konstruktion und Wie Sudoku-Schwierigkeit bewertet wird für Human-Style-Ratings.