Auf dieser Seite
Wie wenige Vorgaben kann ein klassisches 9×9-Sudoku besitzen und trotzdem genau eine Lösung haben?
Diese Frage klingt zunächst wie eine einfache Suche nach besonders „leeren“ Rätseln. Tatsächlich ist sie ein mathematisches Extremalproblem, bei dem Eindeutigkeit für jede mögliche Vorgabenmenge berücksichtigt werden muss.
Die bewiesene Untergrenze lautet:
Ein eindeutig lösbares klassisches 9×9-Sudoku benötigt mindestens 17 Vorgaben.
Eindeutige Rätsel mit 17 Vorgaben existieren. Eindeutige Rätsel mit 16 Vorgaben existieren nicht.
Diese Aussage betrifft ausschließlich die klassische 9×9-Regelstruktur und sagt nichts darüber aus, wie schwierig ein 17-Vorgaben-Rätsel für einen Menschen ist.
Was zählt als Sudoku-Vorgabe?
Eine Vorgabe ist eine Ziffer, die bereits im Ausgangsraster fest eingetragen ist und vom Spieler nicht verändert wird.
In einem klassischen 9×9-Sudoku gibt es 81 Zellen. Wenn ein Rätsel 17 Vorgaben besitzt, sind 64 Zellen zunächst leer.
Die Vorgabenzahl beschreibt jedoch nur, wie viele Werte sichtbar sind. Sie sagt nicht, wo diese Werte liegen, welche strukturelle Information sie liefern oder wie stark sie den Raum möglicher vollständiger Raster einschränken.
Zwei Rätsel mit derselben Zahl an Vorgaben können deshalb völlig unterschiedliche Eigenschaften besitzen.
Warum Eindeutigkeit Teil der Minimum-Frage ist
Ohne Eindeutigkeit wäre die Frage nach möglichst wenigen Vorgaben wenig interessant.
Ein fast leeres Raster kann sehr viele gültige Vervollständigungen besitzen. Das bedeutet aber nicht, dass es ein gutes klassisches Sudoku-Rätsel ist.
Die eigentliche Frage lautet daher:
Wie klein kann eine Vorgabenmenge sein, wenn genau eine vollständige Sudoku-Lösung mit ihr kompatibel sein soll?
Damit wird die Vorgabenzahl mit einer globalen Eigenschaft des gesamten Rätsels verknüpft.
Eine Vorgabenmenge muss genügend Information enthalten, um alle alternativen vollständigen Raster auszuschließen.
Warum 17 nicht offensichtlich war
Schon lange waren viele eindeutige Sudoku mit sehr wenigen Vorgaben bekannt.
Dass 17-Vorgaben-Sudoku existieren, beweist jedoch nur:
Die Untergrenze ist höchstens 17.
Um zu beweisen, dass 17 tatsächlich die globale Untergrenze ist, musste zusätzlich gezeigt werden:
Kein einziges eindeutiges klassisches Sudoku mit nur 16 Vorgaben existiert.
Das ist deutlich schwieriger.
Man kann nicht einfach einige Milliarden zufällige 16-Vorgaben-Raster testen und aus ihrem Scheitern schließen, dass kein Gegenbeispiel existiert. Ein Beweis muss den gesamten relevanten Suchraum abdecken.
Wie der Beweis gegen 16 Vorgaben funktionierte
Gary McGuire, Bastian Tugemann und Gilles Civario veröffentlichten 2012 ein rechnergestütztes Ergebnis, das sämtliche möglichen 16-Vorgaben-Fälle ausschloss.
Der zentrale Gedanke bestand nicht darin, blind alle Kombinationen von 16 Zellen aus allen denkbaren Lösungsgittern durchzuprobieren.
Stattdessen wurde die Struktur vollständiger Sudoku-Raster ausgenutzt. Für ein gegebenes Lösungsraster lassen sich bestimmte Zellmengen identifizieren, die von einer eindeutigen Vorgabenmenge „getroffen“ werden müssen. Solche Strukturen reduzieren die Menge sinnvoll zu untersuchender Kandidaten drastisch.
Anschließend konnte exhaustiv geprüft werden, ob irgendeine 16-Zellen-Menge sämtliche notwendigen Bedingungen erfüllt und eine eindeutige Lösung festlegt.
Das Ergebnis war negativ.
Damit blieb 17 als kleinste mögliche Vorgabenzahl übrig.
Was ist ein Unavoidable Set?
Ein Unavoidable Set ist, vereinfacht gesagt, eine Zellmenge eines vollständigen Lösungsrasters, aus der mindestens eine Zelle als Vorgabe gewählt werden muss, wenn genau dieses Lösungsraster eindeutig festgelegt werden soll.
Warum?
Weil die Werte innerhalb eines solchen Sets auf eine alternative Weise verändert werden könnten, ohne die Sudoku-Regeln zu verletzen. Wenn keine Zelle des Sets als Vorgabe festgehalten wird, bleibt diese alternative Struktur mit der Vorgabenmenge kompatibel.
Daher muss jede eindeutige Vorgabenmenge jedes relevante Unavoidable Set treffen.
Diese Perspektive verwandelt die Suche nach kleinen eindeutigen Rätseln in eine strukturierte Hitting-Set-artige Aufgabe: Finde eine möglichst kleine Auswahl von Zellen, die alle notwendigen Strukturen abdeckt.
Warum 17 zufällige Vorgaben nicht genügen
Die Zahl 17 ist eine globale Untergrenze, keine Erfolgsformel.
Wenn du aus einem vollständigen Sudoku-Raster zufällig 17 Zellen auswählst, ist es äußerst unwahrscheinlich, dass diese Auswahl genau eine Lösung bestimmt.
Die Vorgaben müssen an den richtigen Stellen liegen und gemeinsam genügend Information liefern, um alle Alternativen auszuschließen.
Darum gilt:
„17 Vorgaben sind möglich“ bedeutet nicht „jede Auswahl von 17 Vorgaben funktioniert“.
Tatsächlich sind eindeutige 17-Vorgaben-Rätsel hochstrukturierte Sonderfälle innerhalb eines enorm großen Raums möglicher Vorgabenmengen.
Minimum vs minimale Sudoku-Rätsel
Die Wörter klingen ähnlich, beschreiben aber verschiedene Eigenschaften.
Sudoku mit minimaler Vorgabenzahl
Ein Rätsel mit minimaler Vorgabenzahl im globalen Sinn besitzt so wenige Vorgaben wie überhaupt möglich.
Für klassisches 9×9-Sudoku bedeutet das:
17 Vorgaben.
Minimales Sudoku
Ein konkretes Sudoku ist minimal, wenn keine einzelne seiner Vorgaben entfernt werden kann, ohne dass die Eindeutigkeit verloren geht.
Ein minimales Sudoku kann 17 Vorgaben haben, muss es aber nicht.
Auch ein Rätsel mit 18, 24 oder 30 Vorgaben kann minimal sein, wenn jede einzelne Vorgabe für seine Eindeutigkeit notwendig ist.
Ist jedes eindeutige 17-Vorgaben-Sudoku minimal?
Ja.
Angenommen, ein eindeutiges 17-Vorgaben-Sudoku hätte eine redundante Vorgabe. Dann könnte diese entfernt werden, und es bliebe ein eindeutiges Sudoku mit 16 Vorgaben zurück.
Da ein solches 16-Vorgaben-Sudoku nachweislich nicht existieren kann, ist jede Vorgabe eines eindeutigen 17-Vorgaben-Sudoku notwendig.
Daher ist jedes eindeutige 17-Vorgaben-Sudoku automatisch minimal.
Die Umkehrung gilt jedoch nicht: Nicht jedes minimale Sudoku besitzt 17 Vorgaben.
Kann ein Raster mit 16 Vorgaben überhaupt existieren?
Natürlich kann man 16 Ziffern regelkonform in ein 9×9-Raster eintragen.
Die bewiesene Aussage lautet nicht, dass 16 konsistente Vorgaben unmöglich wären.
Sie lautet:
Keine Menge von 16 Vorgaben bestimmt genau eine klassische 9×9-Sudoku-Lösung.
Ein solches Ausgangsraster kann keine Lösung oder mehrere Lösungen haben. Es kann aber nicht eindeutig sein.
Bedeutet weniger Vorgaben ein schwierigeres Sudoku?
Nein.
Vorgabenzahl und menschliche Schwierigkeit sind unterschiedliche Größen.
Ein Rätsel mit vielen Vorgaben kann einen sehr engen, schwer erkennbaren logischen Bottleneck enthalten. Ein anderes mit deutlich weniger Vorgaben kann früh zahlreiche Singles und einfache Kandidateneliminierungen bieten.
Schwierigkeit hängt eher davon ab:
- welche Techniken benötigt werden;
- wie schwer sie zu erkennen sind;
- wie viele Schritte nötig sind;
- wie stark Schritte voneinander abhängen;
- wie viele produktive Alternativen ein Spieler in einem Zustand sieht.
Darum ist ein 17-Vorgaben-Sudoku nicht automatisch „Expert“.
Warum Konstrukteure normalerweise nicht die 17-Vorgaben-Grenze jagen
Ein gutes Sudoku muss nicht besonders wenige Vorgaben besitzen.
Für Konstrukteure und Generatoren sind oft andere Ziele wichtiger:
- ein interessanter menschlicher Lösungsweg;
- eine gewünschte Schwierigkeitsstufe;
- Einsatz bestimmter Techniken;
- klare logische Progression;
- ästhetische Vorgabenmuster;
- Symmetrie;
- reproduzierbare Qualität.
Das aggressive Entfernen möglichst vieler Vorgaben kann diese Ziele sogar verschlechtern.
Die Zahl 17 ist daher vor allem mathematisch bemerkenswert. Sie ist kein allgemeines Qualitätskriterium für veröffentlichte Rätsel.
Minimale Vorgaben bei Varianten und anderen Rastergrößen
Die 17-Vorgaben-Untergrenze gilt für klassisches 9×9-Sudoku mit den üblichen Zeilen-, Spalten- und 3×3-Blockregeln.
Ändert man das System, ändert sich auch das Extremalproblem.
Beispiele:
- kleinere oder größere Sudoku-Raster;
- Diagonal Sudoku;
- Jigsaw Sudoku;
- Killer Sudoku;
- Varianten mit zusätzlichen Regionen oder Constraints.
Zusätzliche Regeln können Information liefern, die im klassischen Sudoku aus Vorgaben stammen müsste. Deshalb lässt sich die Zahl 17 nicht einfach auf andere Varianten übertragen.
Warum das Ergebnis wichtig ist
Die 17-Vorgaben-Grenze ist ein gutes Beispiel dafür, wie tief Sudoku trotz seiner einfachen Regeln werden kann.
Sie verbindet:
- kombinatorische Struktur;
- Eindeutigkeit;
- vollständige Suche;
- mathematische Reduktion des Suchraums;
- rechnergestützte Beweise.
Gleichzeitig lehrt sie eine wichtige Produkt- und Spielperspektive:
Eine interessante mathematische Grenze ist nicht automatisch ein gutes Difficulty- oder Qualitätsmaß.
Für Spieler ist die benötigte Logik wichtiger als die bloße Zahl sichtbarer Ziffern.
FAQ
Wie wenige Vorgaben kann ein eindeutiges klassisches 9×9-Sudoku besitzen?
17.
Gibt es eindeutige Sudoku mit 16 Vorgaben?
Nein. Eine exhaustive rechnergestützte Suche hat alle möglichen eindeutigen 16-Vorgaben-Fälle ausgeschlossen.
Wer bewies, dass 17 Vorgaben notwendig sind?
Gary McGuire, Bastian Tugemann und Gilles Civario veröffentlichten den rechnergestützten Ausschluss aller 16-Vorgaben-Sudoku.
Ist jedes 17-Vorgaben-Sudoku eindeutig?
Nein. Nur bestimmte Vorgabenmengen mit 17 Zellen bestimmen genau eine Lösung.
Ist jedes eindeutige 17-Vorgaben-Sudoku minimal?
Ja. Andernfalls könnte eine Vorgabe entfernt werden und es gäbe ein eindeutiges 16-Vorgaben-Sudoku, was unmöglich ist.
Ist jedes minimale Sudoku ein 17-Vorgaben-Rätsel?
Nein. Minimal bedeutet nur, dass keine vorhandene Vorgabe entfernt werden kann, ohne Eindeutigkeit zu verlieren.
Ist jedes 17-Vorgaben-Sudoku schwierig?
Nein. Vorgabenzahl ist kein zuverlässiges Maß für menschliche Schwierigkeit.
Gilt die 17-Vorgaben-Grenze auch für Sudoku-Varianten?
Nein. Sie gilt speziell für klassisches 9×9-Sudoku. Zusätzliche Regeln oder andere Rastergrößen verändern das Problem.
Was du als Nächstes lernen solltest
Lies Eindeutige Sudoku-Lösungen, um genauer zu verstehen, wie Lösungsanzahl geprüft wird.
Lies Wie Sudoku-Rätsel erzeugt werden, um zu sehen, wie Konstrukteure Vorgaben entfernen und Eindeutigkeit wiederholt validieren.
Lies Wie Sudoku-Schwierigkeit bewertet wird, wenn du wissen möchtest, warum die Zahl der Vorgaben nicht mit Difficulty gleichgesetzt werden sollte.
Lies Sudoku und Mathematik für den größeren kombinatorischen Kontext.