Auf dieser Seite
Bei einem normalen veröffentlichten klassischen Sudoku erwarten wir, dass genau eine vollständige Lösung zu den Vorgaben passt.
Diese Eindeutigkeit ist jedoch nicht einfach eine zusätzliche lokale Sudoku-Regel. Sie ist eine Eigenschaft der gesamten Vorgabenmenge.
Ein Raster kann in jeder Zeile, jeder Spalte und jedem Block lokal widerspruchsfrei aussehen und trotzdem mehrere vollständige Lösungen zulassen.
Um Eindeutigkeit sauber zu verstehen, muss man deshalb zwischen lokalen Kandidatenregeln, vollständigen Lösungen und globaler Lösungsanzahl unterscheiden.
Die drei möglichen Zustände der Lösungsanzahl
Für ein gegebenes Ausgangsraster gibt es grundsätzlich drei Fälle.
Keine Lösung
Die Vorgaben sind so angeordnet, dass kein vollständig gültiges Sudoku alle Bedingungen gleichzeitig erfüllen kann.
Ein offensichtlicher direkter Widerspruch kann dafür genügen, aber auch ein zunächst unauffälliges Raster kann erst tiefer im Suchraum unlösbar werden.
Genau eine Lösung
Es existiert genau ein vollständiges gültiges Raster, das mit allen Vorgaben kompatibel ist.
Das ist der übliche Zielzustand für ein klassisches veröffentlichtes Sudoku.
Mehr als eine Lösung
Mindestens zwei verschiedene vollständige Raster erfüllen dieselben Vorgaben.
Für eine Eindeutigkeitsprüfung reicht es bereits, eine zweite Lösung zu finden. Ob es insgesamt zwei, zwanzig oder Millionen gibt, ist für die Frage „eindeutig oder nicht?“ nicht mehr relevant.
Die Hinweise widersprechen sich, daher kann kein ausgefülltes Gitter sie alle erfüllen.
Das ist das beabsichtigte Ziel veröffentlichter klassischer Sudokus.
Die Hinweise enthalten nicht genug Information, um eine einzige Endlösung zu erzwingen.
Die zentrale Aussage lautet:
Die Lösungsanzahl ist eine Eigenschaft des gesamten Ausgangsrätsels.
Eindeutigkeit ist keine vierte Sudoku-Regel
Die drei strukturellen Bedingungen des klassischen Sudoku sind:
- jede Zeile enthält die Ziffern 1 bis 9 genau einmal;
- jede Spalte enthält die Ziffern 1 bis 9 genau einmal;
- jeder 3×3-Block enthält die Ziffern 1 bis 9 genau einmal.
Diese Bedingungen definieren ein gültiges vollständiges klassisches Raster.
Eindeutigkeit stellt dagegen die zusätzliche globale Frage:
Wie viele gültige vollständige Raster sind mit genau diesen Ausgangsvorgaben vereinbar?
Die Unterscheidung ist wichtig.
Ein gut konstruiertes klassisches Sudoku soll normalerweise genau eine Lösung haben. Dennoch sollte „genau eine Lösung“ nicht so vermittelt werden, als wäre es bloß eine vierte lokale Peer-Regel neben Zeile, Spalte und Block.
Ein zulässiger Kandidat ist nicht automatisch die Lösung
Angenommen, eine ungelöste Zelle besitzt derzeit die Kandidaten:
{3,8}
Sowohl 3 als auch 8 können lokal zulässig sein:
- keine der Ziffern dupliziert eine Zahl in der Zeile;
- keine dupliziert eine Zahl in der Spalte;
- keine dupliziert eine Zahl im Block.
Das bedeutet nicht, dass man beliebig eine von beiden einsetzen darf.
Ein menschlicher Lösungsweg benötigt weiterhin eine Folgerung, die einen Kandidaten ausschließt oder den anderen erzwingt.
Das ist der Unterschied zwischen:
zulässig — die Ziffer verletzt im Moment keine direkte Constraint;
und:
erzwungen — jede gültige vollständige Lösung benötigt diese Ziffer genau hier.
Eindeutigkeit betrifft den vollständigen Lösungsraum und nicht bloß die unmittelbare lokale Zulässigkeit.
Wie kann ein Sudoku mehrere Lösungen haben?
Mehrere Lösungen entstehen, wenn die Vorgaben genügend Freiheit für zwei oder mehr vollständige Anordnungen lassen.
Eine kleine mehrdeutige Struktur kann beispielsweise erlauben, Kandidatenwerte gegeneinander auszutauschen, während sämtliche Zeilen-, Spalten- und Blockbedingungen weiterhin erfüllt bleiben.
Allgemeiner kann eine Vorgabenmenge schlicht zu wenig Information enthalten, um zwischen mehreren vollständigen Sudoku-Rastern zu unterscheiden.
Das kann selbst dann passieren, wenn:
- jede Vorgabe für sich legal ist;
- in keiner Einheit direkt eine Ziffer doppelt vorkommt;
- das teilweise gefüllte Raster für einen Menschen völlig plausibel aussieht.
Lokale Konsistenz ist notwendig, aber kein Beweis für Eindeutigkeit.
Kann ein Rätsel mit mehreren Lösungen trotzdem die Sudoku-Regeln erfüllen?
Ja.
Jede einzelne vollständige Lösung kann für sich sämtliche Zeilen-, Spalten- und Blockregeln erfüllen.
Das Problem ist nicht, dass diese Endraster ungültig wären.
Das Problem ist, dass dieselbe Vorgabenmenge mehr als eines von ihnen zulässt.
Für die übliche Ein-Lösungs-Sudoku-Erfahrung bedeutet das: Das Ausgangsrätsel bestimmt kein einziges finales Ergebnis.
Wie Software Sudoku-Eindeutigkeit überprüft
Ein vollständiger Solver kann Eindeutigkeit durch Zählen von Lösungen prüfen, wobei eine wichtige Optimierung möglich ist:
Für die Eindeutigkeitsfrage muss normalerweise nicht über zwei hinausgezählt werden.
Konzeptionell läuft die Prüfung so:
- löse das Sudoku und finde eine vollständige Lösung;
- setze die Suche fort und suche gezielt nach einer davon verschiedenen Lösung;
- stoppe sofort, sobald eine zweite Lösung gefunden wurde;
- wird der gesamte restliche Suchraum ohne zweite Lösung erschöpft, ist die erste Lösung eindeutig.
Die Ausgänge sind damit:
0 Lösungen → ungültiges / unerfüllbares Ausgangsrätsel
1 Lösung → eindeutig
2 gefunden → mehrere Lösungen; weiteres Zählen ist für Eindeutigkeit unnötigDer zugrunde liegende Solver kann unterschiedliche Methoden verwenden:
- Backtracking mit Constraint Propagation;
- Exact Cover / Algorithm X;
- SAT oder ein anderes Constraint-Modell;
- ein anderes vollständiges Exhaustionsverfahren.
Das öffentliche Konzept der Eindeutigkeit hängt nicht von einer bestimmten Implementierung ab.
Warum menschliche Techniken allein kein Eindeutigkeitsbeweis sind
Ein Human-Style-Solver fragt:
Kann ich den nächsten Einsatz oder die nächste Eliminierung mit einer erklärbaren Technik herleiten?
Ein Eindeutigkeitsprüfer fragt:
Wie viele vollständige Lösungen existieren?
Das sind verschiedene Aufgaben.
Ein Sudoku kann genau eine Lösung besitzen, obwohl eine bestimmte Bibliothek menschlicher Techniken gerade keinen vollständigen erklärbaren Lösungsweg findet.
Umgekehrt beweist ein Solver, der eine vollständige Lösung findet, noch keine Eindeutigkeit. Er muss zusätzlich alle möglichen zweiten Lösungen ausschließen.
Diese Trennung ist grundlegend für Generatoren und Difficulty-Systeme.
Warum Rätselgeneratoren Eindeutigkeit immer wieder prüfen
Ein Generator beginnt häufig mit einem vollständigen Lösungsraster und entfernt anschließend Vorgaben.
Nach jeder Entfernung kann das Rätsel weiterhin:
- genau eine Lösung;
- mehrere Lösungen
besitzen.
Eine robuste Konstruktionspipeline überprüft deshalb während des Prozesses wiederholt, ob Eindeutigkeit erhalten bleibt.
Vereinfacht:
vollständiges Lösungsraster
↓
Vorgaben auswählen oder entfernen
↓
Lösungsanzahl prüfen
↓
Änderung behalten oder verwerfen
↓
menschliche Lösbarkeit und Schwierigkeit analysierenDie Eindeutigkeitsprüfung ist damit eine Validierungsschicht.
Sie sollte konzeptionell vom Human-Style-Solver getrennt bleiben, der später den erklärbaren Technikpfad erzeugt.
Eindeutig bedeutet nicht leicht
Eindeutigkeit sagt nichts darüber aus, wie schwer ein Rätsel für einen Menschen ist.
Ein eindeutiges Sudoku kann:
- Leicht;
- Mittel;
- Schwer;
- Experte;
- oder sogar jenseits des von einem bestimmten Human-Style-Solver unterstützten Techniksets liegen.
Schwierigkeit hängt von den benötigten Folgerungen, ihrem Erkennungsaufwand, der Kandidatenstruktur und den Abhängigkeiten zwischen den Schritten ab.
Sudoku-Theorie entdeckenWie Sudoku-Schwierigkeit bewertet wirdErfahre, wie Sudoku-Difficulty aus benötigten Techniken, Lösungsaufwand, Abhängigkeiten, Erkennungsaufwand und Spielerdaten bewertet werden kann.Theorie-Guide lesen →Daher gilt:
Lösungsanzahl beantwortet wie viele vollständige Lösungen existieren;
während:
Schwierigkeit fragt wie schwer der beabsichtigte Weg zu entdecken und zu beweisen ist.
Eindeutig bedeutet nicht minimal
Ein eindeutiges Rätsel kann Vorgaben enthalten, die für die Eindeutigkeit gar nicht notwendig sind.
Ein Sudoku ist minimal nur dann, wenn das Entfernen irgendeiner einzelnen Vorgabe dazu führt, dass Eindeutigkeit verloren geht.
Daraus folgt:
- jedes minimale Sudoku ist definitionsgemäß eindeutig;
- nicht jedes eindeutige Sudoku ist minimal.
Ein Konstrukteur kann redundante Vorgaben bewusst behalten, etwa wegen:
- Schwierigkeit;
- visueller Symmetrie;
- Lösungsfluss;
- redaktionellem Stil.
Die globale minimale Vorgabenzahl ist wiederum noch ein anderes Konzept.
Eindeutig bedeutet nicht gut konstruiert
Genau eine Lösung ist ein wichtiges Validitätsziel, aber kein vollständiger Qualitätsstandard.
Ein hochwertiges menschliches Sudoku kann zusätzlich danach beurteilt werden:
- ob die vorgesehenen Folgerungen fair sind;
- ob der Lösungsweg flüssig oder interessant ist;
- ob die Schwierigkeit zum Label passt;
- ob die Techniken abwechslungsreich sind;
- ob unbeabsichtigte Alternativpfade vermieden werden sollen;
- ob das Vorgabenmuster ästhetischen Ansprüchen genügt.
Eindeutigkeit sagt uns, dass es ein einziges Ziel gibt.
Sie sagt nicht, ob der Weg dorthin gut ist.
Warum Eindeutigkeit für Unique Rectangle wichtig ist
Die meisten gewöhnlichen Sudoku-Techniken folgen direkt aus Kandidaten-Constraints.
Unique Rectangle ist besonders, weil die Standardbegründung zusätzlich die Annahme verwendet, dass das Rätsel genau eine beabsichtigte Lösung besitzt.
Ein sogenanntes tödliches Rechteck kann eine austauschbare Zwei-Lösungs-Struktur bewahren. Ist Eindeutigkeit bereits bekannt, darf der Kandidatenzustand verworfen werden, der genau diese Mehrdeutigkeit entstehen ließe.
Die Eindeutigkeitsannahme muss deshalb beim Vermitteln der Technik ausdrücklich genannt werden.
Aus demselben Grund sollte man uniqueness-basierte Techniken nicht blind auf irgendein beliebiges Teilraster anwenden, dessen Lösungsanzahl unbekannt ist.
Eindeutigkeit und Raten sind verschiedene Fragen
Nehmen wir an, ein Sudoku besitzt genau eine Lösung.
Daraus folgt nicht, dass ein Mensch raten muss, um sie zu finden.
Ein eindeutiges Rätsel kann vollständig logisch lösbar sein.
Gleichzeitig kann ein rekursiver Computersolver intern Verzweigungen benutzen, um genau dasselbe Rätsel zu verifizieren, obwohl die öffentlich gezeigte menschliche Lösung ausschließlich aus Deduktionen besteht.
Es sind verschiedene Ebenen:
- Eindeutigkeit beschreibt die Zahl vollständiger Lösungen;
- logische Lösbarkeit beschreibt einen verfügbaren Deduktionsweg;
- Suche beschreibt eine mögliche rechnerische Methode, den Raum von Möglichkeiten zu untersuchen.
Diese Begriffe getrennt zu halten verhindert viele Missverständnisse bei fortgeschrittenem Sudoku.
Was, wenn ein veröffentlichtes Sudoku mehrere Lösungen hat?
Wird ein Rätsel als normales klassisches Ein-Lösungs-Sudoku veröffentlicht, besitzt aber tatsächlich mehrere Lösungen, gilt das üblicherweise als Konstruktions- oder Validierungsfehler.
Ein Spieler kann dann einen Zustand erreichen, in dem kein Kandidat logisch erzwungen werden kann, weil tatsächlich mehrere vollständige Antworten verbleiben.
Allerdings beweist Feststecken allein keineswegs, dass ein Sudoku mehrere Lösungen besitzt.
Der Spieler kann schlicht eine Folgerung übersehen haben.
Die Lösungsanzahl muss global geprüft werden und darf nicht aus Frustration während des Lösens abgeleitet werden.
FAQ
Hat jedes Sudoku genau eine Lösung?
Nein. Ein Ausgangsraster kann null, eine oder mehrere gültige Vervollständigungen besitzen.
Sollte ein veröffentlichtes klassisches Sudoku genau eine Lösung haben?
Normalerweise ja. Ein eindeutiges Endergebnis ist die übliche Erwartung für klassische Sudoku-Rätsel.
Ist Eindeutigkeit eine der grundlegenden Zeilen-, Spalten- und Blockregeln?
Nein. Sie ist eine globale Eigenschaft der gesamten Vorgabenmenge.
Kann ein Sudoku zwei gültige Lösungen haben, ohne die Regeln zu brechen?
Ja. Beide vollständigen Raster können jede klassische Regel erfüllen und dennoch mit derselben unzureichenden Vorgabenmenge kompatibel sein.
Kann ein Rätsel eindeutig und trotzdem extrem schwierig sein?
Ja. Eindeutigkeit misst keine menschliche Schwierigkeit.
Beweist das Finden einer Lösung die Eindeutigkeit?
Nein. Ein vollständiger Solver muss zusätzlich ausschließen, dass eine zweite verschiedene Lösung existiert.
Wie kann Software Sudoku-Eindeutigkeit effizient prüfen?
Ein lösungszählender Solver kann stoppen, sobald er eine zweite Lösung findet. Endet die exhaustive Suche nach genau einer Lösung, ist das Rätsel eindeutig.
Ist jedes eindeutige Sudoku minimal?
Nein. Ein eindeutiges Rätsel kann redundante Vorgaben enthalten.
Kann ich Unique Rectangle ohne Eindeutigkeitsannahme verwenden?
Die übliche uniqueness-basierte Unique-Rectangle-Logik setzt voraus, dass das Rätsel als eindeutig bekannt ist.
Was du als Nächstes lernen solltest
Lies Minimale Vorgabenzahl im Sudoku für die globale 17-Vorgaben-Untergrenze und den Unterschied zwischen Minimum und minimal.
Lies Wie Sudoku-Rätsel erzeugt werden, um zu sehen, wo Eindeutigkeitsprüfung in einer Konstruktionspipeline eingesetzt wird.
Lies Unique Rectangle für eine Lösungstechnik, die die Eindeutigkeitsannahme ausdrücklich verwendet.
Lies Muss man bei Sudoku raten? für die Trennung zwischen Eindeutigkeit, logischer Deduktion, Widerspruch und rechnerischer Suche.