Sudoku-Logik

Sudoku-Logik bedeutet, aus einer kleinen Menge von Einschränkungen Schlussfolgerungen abzuleiten, die zwingend wahr sein müssen.

Zu Beginn eines Rätsels verraten die Vorgaben für einzelne Zellen noch relativ wenig. Die eigentliche Stärke entsteht durch das Zusammenspiel der Regeln:

• Jede Zeile benötigt die Ziffern 1–9 genau einmal.
• Jede Spalte benötigt die Ziffern 1–9 genau einmal.
• Jeder 3×3-Block benötigt die Ziffern 1–9 genau einmal.

Ein logischer Lösungsschritt gewinnt aus diesen Einschränkungen neue Information.

Manchmal ist diese Information eine Ziffer, die du setzen kannst.

Manchmal lautet sie nur:

Dieser Kandidat ist unmöglich.

Auch das ist echter Fortschritt.

Vier Arten von Information

Die meisten Schlussfolgerungen des aktuellen Lernwegs lassen sich als eine von vier Informationsarten verstehen.

1. Erzwungener Wert

Diese Zelle muss X sein.

Beispiele:

• letzte fehlende Ziffer
• Naked Single
• Hidden Single

2. Verbotener Wert

Diese Zelle kann nicht X sein.

Beispiele:

• Locked Candidates
• Teilmengen
• Fish
• Wings
• Chain-Eliminierungen

3. Reservierung

Diese N Ziffern gehören in diese N Zellen, auch wenn ihre genaue Reihenfolge noch nicht feststeht.

Beispiele:

• Naked Pair
• Hidden Pair
• Tripel

4. Implikation

Wenn dieser Kandidat einen bestimmten Zustand hat, wird ein anderer Kandidat in einen anderen Zustand gezwungen.

Beispiele:

• Strong/Weak Links
• Coloring
• X-Chains
• XY-Chains

Kandidaten sind ein Modell von Unsicherheit

Ein Kandidat ist keine schwache Vermutung.

Er bedeutet:

Diese Ziffer wurde im aktuellen Zustand noch nicht ausgeschlossen.

Für eine Zelle r4c7 könnte die Kandidatenmenge lauten:

{2,5,8}

Mit jeder neuen Schlussfolgerung schrumpft diese Menge.

Wird daraus:

{8}

hast du einen Naked Single.

Aus mathematischer Sicht ist Kandidatenpflege eine menschenlesbare Form der Constraint Propagation oder Einschränkungsfortpflanzung: Jeder gelöste Wert schränkt seine Partner ein, und jede neue Einschränkung kann weitere Einschränkungen auslösen.

Zellorientiertes Denken

Zellorientierte Logik fragt:

Was kann diese Zelle enthalten?

Typische Techniken:

• Naked Single
• Naked Pair
• Naked Triple
• XY-Wing / Beziehungen zwischen Bivalue-Zellen

Beispiel:

Zwei Zellen in einer Zeile sind beide {3,9}.

Diese Zellen reservieren 3 und 9.

Andere Zellen der Zeile können keine der beiden Ziffern verwenden.

Die genaue Reihenfolge ist unbekannt.

Die Reservierung ist trotzdem sicher.

Ziffernorientiertes Denken

Ziffernorientierte Logik fragt:

Wo kann diese Ziffer stehen?

Typische Techniken:

• Hidden Single
• Locked Candidates
• Hidden Subsets
• X-Wing
• Swordfish
• Simple Coloring
• X-Chain

Beispiel:

Alle Kandidaten 6 eines Blocks liegen in Zeile 4.

Die genaue 6-Zelle ist unbekannt.

Aber der Block garantiert, dass Zeile 4 ihre 6 innerhalb dieses Blocks erhält.

Deshalb kann Kandidat 6 aus Zeile 4 außerhalb des Blocks entfernt werden.

Das ist ein wiederkehrendes Sudoku-Prinzip:

Die genaue Eintragung kann noch unbekannt sein, während eine schwächere Positionsinformation bereits stark genug ist, um Kandidaten auszuschließen.

Lokale und verteilte Logik

Lokale Schlussfolgerungen

Ihr Beweis liegt hauptsächlich in einer Zelle, Einheit oder Schnittstelle:

• Singles
• Locked Candidates
• Paare
• Tripel

Verteilte Schlussfolgerungen

Ihr Beweis verbindet Informationen über weiter entfernte Einheiten oder Zellen:

• X-Wing
• Swordfish
• Skyscraper
• W-Wing
• Coloring
• Chains

Fortgeschrittenes Sudoku führt keine neuen Regeln für Zeilen, Spalten oder Blöcke ein.

Es kombiniert dieselben Einschränkungen lediglich über eine größere Abhängigkeitsstruktur.

Zählen ist eines der tiefsten wiederkehrenden Sudoku-Prinzipien

Mehrere scheinbar unterschiedliche Techniken beruhen auf Mengen- und Zählargumenten.

Teilmengenzählen

N Zellen ↔ N Ziffern

Können drei Zellen zusammen nur drei Ziffern enthalten, sind diese Ziffern für genau diese Zellen reserviert.

Fish-Zählen

N Grundeinheiten → N Deckeinheiten

Benötigen N Grundeinheiten jeweils eine Kopie einer Ziffer und liegen alle möglichen Positionen innerhalb von N gegenüberliegenden Einheiten, sind diese Deckeinheiten durch die Grundmengen belegt.

Hidden-Subset-Zählen

N Ziffern → N mögliche Zellen

Haben N benötigte Ziffern außerhalb von N Zellen keine möglichen Positionen, sind diese Zellen für sie reserviert.

Die betrachteten Objekte ändern sich.

Die Logik eingeschränkter Mengen bleibt erstaunlich ähnlich.

Implikationslogik

Fortgeschrittenes Lösen wird leichter verständlich, wenn Kandidatenbeziehungen als Implikationen geschrieben werden.

Strong Link

Zwei Kandidatenzustände können nicht beide falsch sein.

A falsch
→ B wahr

Weak Link

Zwei Kandidatenzustände können nicht beide wahr sein.

A wahr
→ B falsch

Durch abwechselnde Links kann sich ein Zustand fortpflanzen:

falsch
→ wahr
→ falsch
→ wahr

Eine nützliche Chain macht aus dieser Fortpflanzung eine Schlussfolgerung über einen Endpunkt, einen Zielkandidaten oder einen Widerspruch.

Widerspruch als Beweismethode

Angenommen, du nimmst vorübergehend an:

Kandidat A ist wahr.

Danach folgt jede weitere Konsequenz zwingend.

Führt die Chain zu einem unmöglichen Zustand, war die Annahme falsch.

Das ist nicht dasselbe, wie A zufällig einzutragen und zu hoffen.

Die vorübergehende Annahme dient dazu, den gegenteiligen Zustand zu beweisen.

Mögliche Widersprüche sind zum Beispiel:

• doppelte gelöste Ziffer in einer Einheit
• eine ungelöste Zelle ohne Kandidaten
• eine benötigte Ziffer ohne legale Position in einer Einheit
• ein unmöglicher Chain-Zustand

Warum „zulässig“ schwächer ist als „gelöst“

Eine Ziffer kann in einer Zelle zulässig sein, weil sie keinen unmittelbaren Konflikt erzeugt.

Das bedeutet nicht, dass sie dort logisch bestimmt ist.

Beispiel:

r5c4 {3,8}

Beide Kandidaten können zulässig sein.

Die 3 allein deshalb zu wählen, weil sie passt, ist keine Schlussfolgerung.

Eine logische Eintragung muss erklären, warum 8 ausgeschlossen wurde oder warum 3 auf andere Weise erzwungen ist.

Dieser Unterschied ist sowohl für die Regeln als auch für das Lernsystem zentral.

Nützliche Schlussfolgerung und gültiges Muster

Ein Muster kann vorhanden sein, ohne das Raster zu verändern.

Zum Beispiel:

• ein Naked Pair, dessen Ziffern ohnehin in keiner anderen Zelle der Einheit vorkommen
• ein X-Wing, in dessen Deckspalten keine weiteren Zielkandidaten liegen
• eine Chain, deren Endpunkte kein gemeinsames Ziel sehen

Die Struktur kann gültig sein.

Der Lösungsschritt ist trotzdem unproduktiv.

Eine gute Übung sollte diesen Unterschied testen, damit Mustersammeln nicht das eigentliche Lösen ersetzt.

Die Abhängigkeitskaskade

Sudoku entwickelt sich selten als Folge isolierter benannter Techniken.

Eine realistische Sequenz kann so aussehen:

X-Wing
↓
Kandidateneliminierung
↓
Hidden Single
↓
Eintragung
↓
Partner-Update
↓
Locked Candidates
↓
Naked Single

Der fortgeschrittene Zug ist wertvoll, weil er einfachere Informationen freilegt.

Deshalb betonen die Strategie-Ratgeber immer wieder:

Nach jeder Eliminierung erneut nach einfacher Logik scannen.

Korrektheitssolver und menschenorientierter Solver

Software kann unterschiedliche Fragen beantworten.

Korrektheits- / Lösungsanzahl-Solver

Existiert eine Lösung?

Existiert genau eine?

Er kann verwenden:

• Backtracking
• Exact Cover
• SAT-/Constraint-Suche
• einen anderen vollständigen Algorithmus

Menschenorientierter Analyzer

Welche verständliche Schlussfolgerung ist als Nächstes verfügbar?

Er versucht eine Technikbibliothek in definierter Reihenfolge und protokolliert:

• Eintragungen
• Eliminierungen
• benötigte Techniken
• Abhängigkeiten
• Schwierigkeitsmerkmale

Sudoku-Software kann von beiden Arten profitieren.

Ein Solver für jede Aufgabe würde Korrektheit, Didaktik und Schwierigkeitsbewertung unnötig vermischen.

Eindeutigkeit ist eine zusätzliche Voraussetzung

Unique Rectangle folgt nicht ausschließlich aus den drei lokalen Sudoku-Einschränkungen.

Die Technik nimmt zusätzlich an:

Dieses Rätsel hat genau eine Lösung.

Diese Voraussetzung kann gültig und nützlich sein, muss aber ausdrücklich genannt werden.

Eindeutigkeitsbasierte Schlussfolgerungen sollten nur verwendet werden, wenn das Rätsel als eindeutig verifiziert wurde und das gewählte Lösungsmodell solche Techniken zulässt.

Was „logisch“ in diesen Ratgebern bedeutet

In diesen Ratgebern sollte eine logische Schlussfolgerung:

• aus bekannten Rätselregeln und ausdrücklich genannten Zusatzannahmen folgen
• aus dem aktuellen Zustand reproduzierbar sein
• Schritt für Schritt erklärbar sein
• unabhängig am Rätselzustand überprüfbar sein
• produktiv sein, wenn sie als nächster Lösungsschritt präsentiert wird

Der Name der Technik ist zweitrangig.

Der Beweis ist das Entscheidende.

FAQ

Ist das Entfernen von Kandidaten ein echter Sudoku-Zug?

Ja. Beim mittleren und fortgeschrittenen Lösen entsteht Fortschritt häufig zuerst durch Eliminierungen, bevor eine weitere Ziffer gesetzt werden kann.

Beruhen fortgeschrittene Techniken auf anderen Regeln?

Normalerweise nein. Sie kombinieren dieselben Einschränkungen über mehr Zellen oder Einheiten hinweg. Eindeutigkeitstechniken ergänzen ausdrücklich die verifizierte Annahme einer einzigen Lösung.

Ist ein Widerspruch Raten?

Nicht, wenn eine vorübergehende Annahme innerhalb eines gültigen Beweises verwendet wird und die Schlussfolgerung erzwungen ist.

Warum können zwei Solver unterschiedliche nächste Züge finden?

Mehrere Schlussfolgerungen können gleichzeitig verfügbar sein. Ein menschenorientierter Solver braucht deshalb ein Prioritätsmodell und bevorzugt normalerweise einfachere produktive Logik.

Muss jedes gültige Muster verwendet werden?

Nein. Wenn es keine neue Information erzeugt oder eine einfachere Schlussfolgerung verfügbar ist, kann es sinnvoller sein, es zu ignorieren.

Was als Nächstes?

Für die praktische Frage „Muss ich jemals raten?“ lies Muss man bei Sudoku raten?

Für die mathematische Darstellung des Rätsels geht es weiter mit Sudoku und Mathematik.