Ein Sudoku besitzt eine eindeutige Lösung, wenn genau ein vollständig ausgefülltes Raster alle Startvorgaben sowie alle klassischen Zeilen-, Spalten- und 3×3-Blockbedingungen erfüllt.
Das klingt einfach, beantwortet aber eine andere Frage als die Prüfung eines einzelnen Zuges.
Eine Ziffer kann lokal zulässig sein, ohne erzwungen zu sein. Und ein Startzustand kann keinerlei sichtbaren Konflikt besitzen, aber trotzdem mehrere vollständige Lösungen zulassen.
Die drei möglichen Lösungsanzahlen
Ein Startzustand kann haben:
Keine Lösung
Die Vorgaben sind mit den Sudoku-Bedingungen unvereinbar. Kein vollständiges Raster funktioniert.
Genau eine Lösung
Ein vollständiges Raster – und nur dieses – erfüllt Vorgaben und alle klassischen Bedingungen.
Mehr als eine Lösung
Die Vorgaben bestimmen kein eindeutiges Endraster. Zwei oder mehr Vervollständigungen bleiben möglich.
Veröffentlichte klassische Sudoku zielen normalerweise auf genau eine Lösung.
Eindeutigkeit ist eine globale Eigenschaft
Die lokalen klassischen Regeln sind leicht formuliert:
- keine doppelte Ziffer in einer Zeile;
- keine doppelte Ziffer in einer Spalte;
- keine doppelte Ziffer in einem Block.
Damit lässt sich prüfen, ob ein vollständiges Raster gültig ist oder ob eine einzelne Eintragung einen unmittelbaren Konflikt erzeugt.
Sie beweisen aber nicht automatisch, dass ein teilweise gefülltes Rätsel nur eine mögliche Vervollständigung besitzt.
Deshalb sind diese Aussagen verschieden:
Diese Eintragung verletzt keine Zeile, Spalte und keinen Block.
Dieses Ausgangsrätsel besitzt genau ein mögliches vollständiges Raster.
Die zweite Aussage erfordert eine Analyse des gesamten Rätsels oder eine vollständige Lösungssuche.
Zulässige Kandidaten sind nicht automatisch gelöste Ziffern
Angenommen, eine ungelöste Zelle besitzt:
{3,8}
Beide Ziffern können die lokalen Zeilen-, Spalten- und Blockbedingungen erfüllen.
Das bedeutet nicht, dass du frei eine auswählen darfst.
Eine logische Lösung braucht weiterhin eine Schlussfolgerung, die einen Kandidaten eliminiert oder den endgültigen Wert anderweitig beweist.
Darum sollte Sudoku vier Konzepte getrennt halten:
- Regelgültigkeit — verletzt ein Zustand eine Grundregel?
- Kandidatenzulässigkeit — kann diese Ziffer noch in diese Zelle?
- Schlussfolgerung — lässt sich eine Möglichkeit beweisen oder ausschließen?
- Eindeutigkeit — wie viele vollständige Lösungen passen zu den Startvorgaben?
Wie Software Eindeutigkeit prüfen kann
Ein vollständiger Solver kann den Lösungsraum durchsuchen und Lösungen zählen.
Für eine Eindeutigkeitsprüfung muss er nicht jede mögliche Lösung ausgeben. Es reicht, zwischen diesen Fällen zu unterscheiden:
0 Lösungen
1 Lösung
2 oder mehr LösungenEin typischer Ablauf:
- suchen, bis die erste Lösung gefunden wird;
- Suche fortsetzen;
- sofort stoppen, wenn eine zweite unterschiedliche Lösung gefunden wird;
- endet die Suche nach der ersten Lösung vollständig, ist das Rätsel eindeutig.
Für diese Aufgabe können zum Beispiel Backtracking, Exact Cover, SAT-/CSP-Solver oder andere vollständige Methoden verwendet werden.
Der Algorithmus kann variieren.
Die geprüfte Eigenschaft bleibt dieselbe.
Warum Generatoren Eindeutigkeit immer wieder prüfen
Ein vollständiges 81-Zellen-Lösungsraster ist bereits eine gültige Lösung.
Um daraus ein Rätsel zu machen, werden Ziffern verborgen oder als Vorgaben ausgewählt.
Jede entfernte Vorgabe reduziert die Information für den Spieler.
Nach einer bestimmten Entfernung kann plötzlich eine zweite Vervollständigung möglich werden.
Darum wiederholt die Erzeugung oft einen Zyklus wie:
Vorgabenmenge verändern
↓
Rätsel testen
↓
immer noch genau eine Lösung?Generatoren können sehr unterschiedlich arbeiten, aber ein als klassisches eindeutiges Sudoku veröffentlichtes Rätsel muss diese Eigenschaft letztlich erfüllen.
Eindeutig bedeutet nicht leicht
Eindeutigkeit ist im Wesentlichen eine Ja/Nein-Eigenschaft.
Schwierigkeit ist das nicht.
Zwei eindeutige Sudoku können völlig unterschiedliche menschliche Lösungswege besitzen:
- eines zerfällt mit Singles;
- ein anderes benötigt Locked Candidates und Teilmengen;
- ein weiteres verlangt Fish, Wings oder Chains.
Lösungsanzahl ist deshalb wichtig für Gültigkeit.
Schwierigkeit benötigt eine getrennte Analyse des Lösungswegs.
Sudoku-Theorie entdeckenWie Sudoku-Schwierigkeit bewertet wirdErfahre, warum Sudoku-Schwierigkeit nicht allein von Vorgaben abhängt und wie Techniken, Lösungsaufwand, Abhängigkeiten und Spielerdaten bessere Ratings ermöglichen.Theorie-Guide lesen →Eindeutig bedeutet nicht minimal
Ein Sudoku kann genau eine Lösung besitzen und trotzdem Vorgaben enthalten, die für die Eindeutigkeit nicht notwendig sind.
Ein minimales Sudoku erfüllt die strengere Bedingung:
Entferne eine beliebige einzelne Vorgabe und das Rätsel besitzt nicht mehr genau eine Lösung.
Minimalität beschreibt die Notwendigkeit der Vorgaben in diesem konkreten Rätsel.
Sie bedeutet nicht, dass das Sudoku die global kleinstmögliche Zahl an Vorgaben besitzt.
Sudoku-Theorie entdeckenMinimale Vorgabenzahl im SudokuErfahre, warum ein eindeutiges 9×9-Sudoku mindestens 17 Vorgaben braucht und wie eine vollständige Computersuche alle Fälle mit 16 Vorgaben ausschloss.Theorie-Guide lesen →Warum Eindeutigkeit für Unique Rectangle wichtig ist
Die meisten Sudoku-Techniken beruhen direkt auf Kandidatenbeschränkungen durch Zeilen, Spalten, Blöcke und frühere Schlussfolgerungen.
Unique Rectangle ist anders, weil die Standardbegründung voraussetzt, dass das Rätsel nur eine vorgesehene Lösung hat.
Ein Deadly Rectangle kann zwei austauschbare Vervollständigungen erzeugen. Ist Eindeutigkeit nachgewiesen, kann ein Zustand, der diese Mehrdeutigkeit erhalten würde, ausgeschlossen werden.
Diese Voraussetzung sollte bei jeder Eindeutigkeitstechnik ausdrücklich genannt werden.
Kann ein Mehrfachlösungs-Rätsel trotzdem die Sudoku-Regeln erfüllen?
Ja.
Jede einzelne vollständige Lösung kann alle klassischen Sudoku-Regeln korrekt erfüllen.
Das Problem liegt darin, dass die Startvorgaben nicht genau ein Endergebnis bestimmen.
Solche Rätsel passen daher nicht zur normalen Einzel-Lösungs-Sudoku-Erfahrung, obwohl ihre individuellen vollständigen Raster gültig sein können.
Eindeutigkeit und logische Lösbarkeit sind verschiedene Fragen
Ein vollständiger Solver kann beweisen, dass ein Sudoku genau eine Lösung besitzt, obwohl eine bestimmte menschliche Technikbibliothek aktuell keinen erklärbaren Weg zu dieser Lösung findet.
Das sind zwei unterschiedliche Fragen:
Wie viele Lösungen existieren?
und:
Welche menschenlesbaren Schlussfolgerungen lösen das Rätsel?
Diese Trennung macht sowohl Erzeugung als auch Schwierigkeitsanalyse klarer.
FAQ
Hat jedes Sudoku genau eine Lösung?
Nein. Ein Startzustand kann null, eine oder mehrere vollständige Lösungen besitzen.
Gehört Eindeutigkeit zu den Grundregeln für Zeilen, Spalten und Blöcke?
Nein. Sie ist eine globale Eigenschaft, die von veröffentlichten klassischen Sudoku normalerweise erwartet wird.
Kann ein eindeutiges Sudoku trotzdem extrem schwierig sein?
Ja. Eindeutigkeit sagt nichts darüber aus, wie anspruchsvoll die benötigten menschlichen Schlussfolgerungen sind.
Beweist eine Lösung automatisch, dass das Rätsel gut konstruiert ist?
Nein. Gute Rätsel können zusätzlich nach Schwierigkeit, Lösungsfluss, Vorgabenanordnung und benötigten Techniken bewertet werden.
Wie kann Software Eindeutigkeit effizient prüfen?
Ein vollständiger Solver kann stoppen, sobald eine zweite unterschiedliche Lösung gefunden wird. Wird die Suche nach genau einer Lösung vollständig ausgeschöpft, ist das Sudoku eindeutig.
Kann ich Unique Rectangle ohne Eindeutigkeitsvoraussetzung verwenden?
Standardmäßige Unique-Rectangle-Logik setzt voraus, dass das Rätsel nachweislich genau eine Lösung besitzt.
Was du als Nächstes lernen solltest
Lies Minimale Vorgabenzahl im Sudoku für die globale Untergrenze von 17.
Lies Wie Sudoku erzeugt werden, um zu sehen, wo Eindeutigkeitsprüfung in der Konstruktion eingesetzt wird.
Lies Unique Rectangle für eine Technik, die diese Voraussetzung ausdrücklich nutzt.