Für ein klassisches 9×9-Sudoku, das genau eine Lösung besitzen muss, beträgt die bewiesene minimale Zahl der Startvorgaben:
17
Eindeutige Sudoku mit 17 Vorgaben existieren.
Ein eindeutiges klassisches Sudoku mit 16 Vorgaben existiert nicht.
Diese zweite Aussage wurde durch eine vollständige rechnergestützte Suche von Gary McGuire, Bastian Tugemann und Gilles Civario bewiesen.
Das Ergebnis beantwortet eine sehr präzise mathematische Frage. Es bedeutet nicht, dass 17 Vorgaben automatisch die besten, schwierigsten oder für Generatoren wünschenswertesten Rätsel erzeugen.
Was zählt als Vorgabe?
Eine Vorgabe ist eine Ziffer, die bereits vor dem ersten Zug des Spielers eingetragen ist.
Englisch: given oder clue.
Ein Sudoku mit 17 Vorgaben beginnt mit:
- 17 ausgefüllten Zellen;
- 64 leeren Zellen.
Die vollständige Lösung enthält weiterhin 81 Ziffern.
Die Vorgabenzahl beschreibt den Startzustand, nicht die Größe der Lösung.
Warum Eindeutigkeit Teil der Frage ist
Ohne Eindeutigkeitsbedingung könnten wir viele Vorgaben entfernen und einen Startzustand mit sehr vielen möglichen vollständigen Lösungen erhalten.
Das beantwortet nicht das klassische Minimum-Clue-Problem.
Die tatsächliche Frage lautet:
Was ist die kleinste Vorgabenmenge, die genau ein gültiges vollständiges klassisches 9×9-Raster bestimmt?
Damit müssen zwei Bedingungen gleichzeitig gelten:
- Die Vorgaben sind mit einer Lösung vereinbar.
- Keine zweite Lösung existiert.
Warum 17 nicht offensichtlich war
Forscher und Sudoku-Sammler kannten gültige eindeutige Rätsel mit 17 Vorgaben.
Lange Zeit hatte jedoch niemand ein Beispiel mit 16 gefunden.
Aber:
„Niemand hat eines gefunden“
ist nicht dasselbe wie:
„Es existiert keines.“
Die Herausforderung bestand darin zu beweisen, dass sich im riesigen Sudoku-Suchraum kein unbekanntes 16-Vorgaben-Rätsel versteckt.
Der Beweis gegen 16 Vorgaben
McGuire, Tugemann und Civario überführten das Problem in eine vollständige rechnergestützte Suche mit unavoidable sets und hitting sets.
Auf hoher Ebene:
- mit vollständigen Sudoku-Lösungsrastern beginnen;
- Strukturen bestimmen, die eine Vorgabenmenge treffen muss, damit Eindeutigkeit erhalten bleibt;
- mögliche Vorgabenpositionen als Hitting-Set-Problem behandeln;
- kleine Hitting Sets effizient enumerieren;
- die 16-Vorgaben-Fälle vollständig testen;
- kein eindeutiges 16-Vorgaben-Sudoku finden.
Damit ist die Untergrenze bewiesen:
Jedes eindeutige klassische 9×9-Sudoku benötigt mindestens 17 Vorgaben.
Der Beweis ist rechnergestützt.
Es handelt sich nicht um einen kurzen elementaren Beweis aus Zell- oder Einheitenzählung.
Was ist ein Unavoidable Set?
Für ein bestimmtes Lösungsraster ist ein unavoidable set eine Zellmenge mit folgender Eigenschaft:
Ein eindeutiges Rätsel auf Basis dieses Lösungsrasters muss mindestens eine Vorgabe aus dieser Menge enthalten.
Warum?
Bleiben alle Zellen dieser Menge ohne Vorgabe, kann eine alternative Vervollständigung bestehen bleiben.
Eine gültige Vorgabenmenge muss deshalb jedes relevante unavoidable set „treffen“.
Daher stammt die Hitting-Set-Formulierung des Beweises.
Für diese öffentliche Einführung reicht diese Intuition aus; die Forschungsarbeit enthält die rechnerischen Details.
Minimum vs minimal
Diese Unterscheidung ist wichtig.
Sudoku mit minimaler Vorgabenzahl
Verwendet die global kleinstmögliche Zahl von Vorgaben.
Für eindeutige klassische 9×9-Sudoku:
17 Vorgaben.
Minimales Sudoku
Jede einzelne vorhandene Vorgabe ist für dieses konkrete Rätsel notwendig.
Entfernt man eine beliebige davon, geht die Eindeutigkeit verloren.
Ein minimales Sudoku kann:
- 18;
- 24;
- oder mehr Vorgaben
besitzen.
„Minimal“ bedeutet nicht „hat 17 Vorgaben“.
Es bedeutet:
Keine Vorgabe ist für die Eindeutigkeit redundant.
Ist jedes eindeutige 17-Vorgaben-Sudoku automatisch minimal?
Ja.
Könnte man eine Vorgabe entfernen und die Eindeutigkeit behalten, entstünde ein eindeutiges Sudoku mit 16 Vorgaben.
Das ist durch das Minimum-Ergebnis ausgeschlossen.
Die Umkehrung gilt nicht:
Ein minimales Sudoku muss nicht 17 Vorgaben besitzen.
Kann ich beliebige 17 Zellen eines Lösungsrasters auswählen?
Nein.
Die meisten beliebigen 17-Zellen-Teilmengen erzeugen kein gutes eindeutiges Sudoku.
Sie können:
- mehrere Lösungen zulassen;
- bei inkonsistent gewählten Startziffern gar keine Lösung besitzen;
- nicht mit dem vorgesehenen Human-Style-Modell lösbar sein;
- einen unpassenden Schwierigkeitsgrad erzeugen.
Die globale Untergrenze sagt nur, dass bestimmte eindeutige 17-Vorgaben-Sudoku existieren.
Sie sagt nicht, dass 17 beliebige Positionen genügen.
Bedeutet 17 Vorgaben automatisch Experte?
Nein.
Die Vorgabenzahl ist ein schlechter alleiniger Indikator menschlicher Schwierigkeit.
Schwierigkeit hängt außerdem ab von:
- Position der Vorgaben;
- Kandidatenstruktur;
- benötigten Techniken;
- Zahl der Schritte;
- Abhängigkeitstiefe;
- Erkennungsaufwand.
Ein sehr leeres Raster kann einfache Logik freilegen.
Ein dichteres Raster kann eine schwierige Chain verbergen.
Darum sind Minimale Vorgabenzahl und Schwierigkeitsbewertung getrennte Theory-Seiten.
Kann ein Sudoku mit 16 Vorgaben mehrere Lösungen besitzen?
Natürlich.
Der Satz schließt nur eindeutige klassische Sudoku mit 16 Vorgaben aus.
Ein 16-Vorgaben-Startzustand kann:
- mehrere Lösungen;
- keine Lösung;
- oder einfach ein teilweise gültig wirkendes Raster
besitzen.
Er kann nur nicht genau eine klassische Lösung bestimmen.
Warum das für einen Generator wichtig ist
Vor allem zeigt es, worauf ein praktischer Generator nicht optimieren sollte.
Ein sinnvoller Generator sollte anstreben:
eindeutig
+ menschenähnlich lösbar
+ kalibrierte Schwierigkeit
+ abwechslungsreich
+ reproduzierbarund nicht:
so wenige Vorgaben wie möglichExtreme Vorgabenreduktion kann viel Rechenzeit kosten, ohne automatisch bessere Rätsel zu erzeugen.
Die Vorgabenzahl bleibt nützliche Metadaten.
Sie ist aber kein Qualitätsziel für sich.
Forschung vs Gameplay
Das 17-Vorgaben-Ergebnis ist faszinierend, weil es eine harte Grenze in der kombinatorischen Struktur des Sudoku beschreibt.
Beim Spielen ist die wichtigere Frage:
Erzeugt genau diese Vorgabenanordnung einen fairen, interessanten Lösungsweg?
Das sind unterschiedliche Qualitätskriterien.
FAQ
Wie wenige Vorgaben kann ein eindeutiges klassisches 9×9-Sudoku besitzen?
17.
Gibt es eindeutige Sudoku mit 16 Vorgaben?
Nein. Der 16-Vorgaben-Fall wurde durch vollständige rechnergestützte Suche ausgeschlossen.
Ist jedes 17-Vorgaben-Sudoku schwer?
Nein.
Ist jedes eindeutige 17-Vorgaben-Sudoku minimal?
Ja.
Ist jedes minimale Sudoku ein 17-Vorgaben-Sudoku?
Nein.
Warum kann die Vorgabenzahl die Schwierigkeit nicht bestimmen?
Weil die Positionen und die daraus entstehende Schlussfolgerungsstruktur deutlich wichtiger sind als die reine Anzahl.
Was du als Nächstes lernen solltest
Lies Eindeutige Sudoku-Lösungen für die globale Ein-Lösungs-Eigenschaft.
Lies Wie Sudoku erzeugt werden für die praktische Pipeline zur Auswahl und Prüfung von Vorgaben.