Sudoku-Logik

Sudoku wird oft als Logikrätsel beschrieben. Doch „benutze Logik“ bleibt ungenau, solange die eigentlichen Schlussfolgerungen nicht in kleinere Bestandteile zerlegt werden.

Zu jedem Zeitpunkt enthält das Raster Informationen darüber, was:

• bereits wahr ist;
• noch möglich ist;
• unmöglich ist;
• für bestimmte Zellen oder Einheiten reserviert ist;
• unter einer Bedingung wahr werden muss, wenn ein anderer Kandidat falsch ist.

Eine Sudoku-Technik ist nützlich, weil sie diese Informationen in einen Beweis umwandelt.

Dieser Beweis liefert normalerweise eines von zwei praktischen Ergebnissen:

Eintragung — eine Ziffer muss in eine Zelle;

oder:

Eliminierung — eine Ziffer kann nicht in eine Zelle.

Vom Nackten Single bis zu einer fortgeschrittenen Chain lässt sich jede Technik als spezifische Methode verstehen, eine dieser Aussagen zu beweisen.

Was bedeutet „logisch“ im Sudoku?

In diesen Guides ist eine Schlussfolgerung logisch, wenn ihr Ergebnis aus klar genannten Bedingungen und Voraussetzungen folgt und nicht aus einer zufälligen Wahl.

Die grundlegenden Bedingungen des klassischen Sudoku sind:

• jede Ziffer genau einmal in jeder Zeile;
• jede Ziffer genau einmal in jeder Spalte;
• jede Ziffer genau einmal in jedem Block.

Einige fortgeschrittene Techniken dürfen zusätzlich eine ausdrücklich genannte Voraussetzung verwenden, zum Beispiel:

Dieses Rätsel ist nachweislich eindeutig lösbar.

Entscheidend ist, dass die Voraussetzung bekannt ist und die Schlussfolgerung daraus folgt.

Logisches Lösen wird deshalb nicht dadurch definiert, dass ein Zug einfach aussieht. Eine lange Chain kann vollständig logisch sein. Eine selbstbewusste Eintragung ohne Beweis bleibt trotzdem ein Raten.

Vier wiederkehrende Arten von Sudoku-Information

Viele Techniken lassen sich durch vier Informationstypen verstehen.

1. Erzwungener Wert

Eine Ziffer ist für genau eine Zelle bewiesen.

Beispiele:

• Full House / Last Digit;
• Nackter Single;
• Versteckter Single;
• eine Eintragung, die nach einer fortgeschrittenen Eliminierung entsteht.

2. Verbotener Wert

Ein Kandidat ist in einer Zelle als unmöglich bewiesen.

Beispiele:

• eine Partnerzelle enthält die Ziffer bereits;
• Locked Candidates entfernt die Ziffer;
• ein X-Wing eliminiert sie;
• eine Chain beweist den Kandidaten falsch.

3. Reservierung

Eine Ziffernmenge ist auf eine Zellmenge beschränkt oder eine Ziffer auf bestimmte Positionen festgelegt.

Beispiele:

• ein Nacktes Paar reserviert zwei Ziffern für zwei Zellen;
• ein Verstecktes Triple reserviert drei Ziffern für drei Zellen;
• ein konjugiertes Paar reserviert eine Ziffer für eine von zwei Positionen;
• ein Fish reserviert Kandidatenpositionen über Base- und Cover-Houses.

4. Implikation

Ein Kandidatenzustand erzwingt einen anderen Zustand.

Beispiele:

• wenn A wahr ist, muss B falsch sein;
• wenn A falsch ist, muss B wahr sein;
• mehrere solcher Beziehungen hintereinander erzeugen eine Chain.

Fortgeschrittenes Sudoku wird wesentlich verständlicher, wenn Techniken nicht als unverbundene Namen, sondern als Kombinationen dieser vier Informationsarten gesehen werden.

Kandidaten sind ein Modell von Unsicherheit

Eine ungelöste Zelle kann mehrere Kandidaten besitzen:

{2,5,7}

Diese Notation sagt nicht, dass die drei Möglichkeiten gleich wahrscheinlich sind.

Sudoku ist an dieser Stelle kein Wahrscheinlichkeitsproblem. Die Kandidatenmenge bedeutet nur:

Nach allen bisherigen Schlussfolgerungen sind 2, 5 und 7 hier noch nicht ausgeschlossen.

Eine neue Deduktion kann den Zustand verändern:

{2,5,7} → {2,7}

und später:

{2,7} → {7}

Der letzte Schritt erzeugt einen Nackten Single.

Deshalb ist Kandidateneliminierung echter Fortschritt, auch wenn im Raster nicht sofort eine große gelöste Ziffer erscheint.

Legal ist schwächer als gelöst

Eine der wichtigsten Übergänge vom Anfänger- zum fortgeschrittenen Denken ist der Unterschied zwischen:

„Diese Ziffer könnte hier legal stehen.“

und:

„Diese Ziffer muss hier stehen.“

Ein Kandidat kann lokal legal sein, weil keine bereits gelöste Partnerzelle ihn blockiert.

Das beweist nicht, dass er die Lösung ist.

Eine Eintragung benötigt eine stärkere Aussage, zum Beispiel:

• jede andere Ziffer ist in der Zelle unmöglich;
• jede andere Position dieser Ziffer in der Einheit ist unmöglich;
• eine Implikationskette erzwingt den Kandidaten wahr.

Ein legaler Zug ist eine Möglichkeit. Ein gelöster Zug ist ein Beweis.

Zellorientiertes Denken

Zellorientiertes Denken fragt:

Was kann innerhalb dieser Zelle oder einer kleinen Zellgruppe passieren?

Typische Strukturen sind:

• Nackter Single;
• Bivalue-Zellen;
• Nackte Paare/Dreiergruppen;
• XY-Wing;
• W-Wing;
• XY-Chain.

Das zentrale Objekt ist häufig die Kandidatenmenge innerhalb der Zelle.

Eine Bivalue-Zelle {3,8} liefert zum Beispiel eine starke interne Beziehung:

Ist sie nicht 3, muss sie 8 sein; ist sie nicht 8, muss sie 3 sein.

Diese Beziehung wird später in Wings und Chains nützlich.

Ziffernorientiertes Denken

Ziffernorientiertes Denken fragt:

Wo kann diese eine Ziffer noch stehen?

Typische Strukturen sind:

• Versteckter Single;
• Locked Candidates;
• konjugierte Paare;
• Skyscraper;
• Two-String Kite;
• X-Wing und andere Fish;
• Simple Coloring;
• X-Chains.

Hier ist nicht die vollständige Kandidatenmenge einer Zelle wichtig, sondern die Verteilung einer Ziffer über mehrere Einheiten.

Bewusst zwischen zellorientierter und ziffernorientierter Sicht zu wechseln, ist eine der stärksten allgemeinen Lösungsgewohnheiten.

Einheitenorientiertes Denken

Eine dritte nützliche Perspektive startet bei einer Zeile, Spalte oder einem Block:

Welche Verpflichtungen bestehen innerhalb dieser Einheit?

Ein einheitenorientierter Scan kann aufdecken:

• eine letzte fehlende Ziffer;
• einen Versteckten Single;
• eine Teilmenge;
• eine Locked-Candidates-Schnittmenge;
• ein konjugiertes Paar.

Einheitenorientiertes Denken ist oft die Brücke zwischen einfachem Scanning und formaler Kandidatenanalyse.

Lokale und verteilte Logik

Sudoku-Schlussfolgerungen unterscheiden sich unter anderem darin, wie weit ihr Beweis durch das Raster reicht.

Lokale Schlussfolgerungen

Der Beweis konzentriert sich auf eine Zelle oder wenige direkt verbundene Einheiten.

Beispiele:

• Singles;
• Locked Candidates;
• Paare und Dreiergruppen.

Verteilte Schlussfolgerungen

Der Beweis spannt sich über mehrere getrennte Bereiche des Rasters.

Beispiele:

• Fish;
• W-Wing;
• Coloring;
• X-Chains;
• XY-Chains;
• später AIC und Forcing-Strukturen.

„Verteilt“ bedeutet nicht „weniger logisch“. Es bedeutet nur, dass das relevante Constraint-Netz größer ist.

Zählen ist eine der tiefsten wiederkehrenden Sudoku-Ideen

Viele scheinbar verschiedene Techniken entstehen daraus, dieselbe Anzahl von Objekten derselben Anzahl verfügbarer Plätze zuzuordnen.

Zählen bei Teilmengen

Wenn zwei Zellen einer Einheit zusammen nur zwei Ziffern enthalten können, sind diese Ziffern für die beiden Zellen reserviert.

Allgemeine Form:

N Zellen ↔ N Ziffern

Zählen bei versteckten Teilmengen

Wenn N Ziffern in einer Einheit nur in N Zellen vorkommen können, sind diese Zellen für genau diese Ziffern reserviert.

Es ist dieselbe Reservierung, nur aus der Gegenrichtung entdeckt.

Zählen bei Fish

Ein Basic Fish verwendet eine verwandte Idee über mehrere Einheiten hinweg.

Für eine Ziffer:

N Base Houses → Kandidatenpositionen liegen in N Cover Houses

Die Cover-Einheiten müssen die erforderlichen Vorkommen aus den Bases aufnehmen. Daher werden bestimmte externe Kandidaten in diesen Cover-Einheiten unmöglich.

Wer diese gemeinsame Zählidee erkennt, empfindet Paare, Dreiergruppen, X-Wing, Swordfish und Jellyfish weniger als unverbundene Tricks.

Strong und Weak Links sind Implikationssprache

Fortgeschrittene Kandidatenlogik verwendet häufig zwei grundlegende Link-Typen.

Weak Link

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

Für Kandidaten A und B:

Ist A wahr, muss B falsch sein.

Beide dürfen gleichzeitig falsch sein.

Strong Link

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

Für Kandidaten A und B:

Ist A falsch, muss B wahr sein.

Bei einfachen Kandidaten sind konjugierte Paare und Bivalue-Zellbeziehungen häufige Quellen für Strong Links.

Ein wichtiges fortgeschrittenes Detail: Ein einfacher Strong Link kann auch in schwacher Richtung verwendet werden, wenn die zwei Kandidaten nicht gleichzeitig wahr sein können.

Diese Flexibilität erlaubt Chains, verschiedene Inferenztypen durch das Raster zu alternieren.

Chains machen aus Implikationen einen Beweis

Eine Chain verbindet Implikationen so, dass der Wahrheitszustand eines Endpunkts den anderen einschränkt.

Eine vereinfachte Struktur kann konzeptionell so aussehen:

A falsch
→ B wahr
→ C falsch
→ D wahr

Wenn die Kette beweist, dass mindestens einer von zwei Endpunkten wahr sein muss, kann ein Kandidat eliminiert werden, der mit beiden Endpunkten kollidiert.

Die konkreten Knoten und Link-Typen unterscheiden sich je nach Chain-Familie, doch die Logik ist nicht magisch:

Jeder Schritt muss durch die unmittelbar verbundene Beziehung begründet sein.

Genau das unterscheidet eine gültige Implikationskette von einer Geschichte über Kandidaten, die nur optisch miteinander verbunden wirken.

Widerspruch ist eine Beweismethode

Ein Widerspruchsbeweis folgt diesem Schema:

1. einen klar definierten Kandidaten/Zustand annehmen;
2. logische Konsequenzen verfolgen;
3. einen unmöglichen Zustand erreichen;
4. daraus schließen, dass die ursprüngliche Annahme falsch ist.

Häufige unmögliche Zustände sind:

• eine Zelle ohne Kandidat;
• dieselbe gelöste Ziffer zweimal in einer Einheit;
• eine benötigte Ziffer ohne mögliche Position in einer Einheit;
• ein Kandidat, der gleichzeitig wahr und falsch erzwungen wird.

Widerspruch ist deshalb nicht automatisch „Raten“.

Der Unterschied liegt darin, wie die Annahme verwendet wird:

• Raten wählt einen Zweig, weil man hofft, dass er stimmt;
• Widerspruchsbeweis nimmt einen Zustand vorübergehend an, um gezielt zu beweisen, dass er unmöglich ist.

Direkter Beweis und Widerspruchsbeweis können dieselbe Logik beschreiben

Manche Sudoku-Schlussfolgerungen lassen sich auf mehrere logisch gleichwertige Arten erklären.

Ein Muster kann besitzen:

• einen direkten Zählbeweis;
• einen Implikationsbeweis;
• einen Widerspruchsbeweis.

Für die Lehre ist normalerweise die Erklärung am besten, die die wiederverwendbare Struktur am klarsten zeigt.

Ein X-Wing lässt sich zum Beispiel meist leichter als Fish-/Base-Cover-Logik verstehen als über einen langen hypothetischen Zweig, auch wenn alternative Beweise möglich sind.

Das Ziel ist nicht der spektakulärste Beweis, sondern der klarste.

Ein gültiges Muster ist nicht immer ein nützlicher Zug

Ein Solver kann ein technisch gültiges Muster finden, das keine Eliminierung erzeugt.

Zum Beispiel:

• ein X-Wing existiert, aber in den Cover-Spalten gibt es keine Zielkandidaten;
• eine Chain ist gültig, endet aber in einer Beziehung ohne Eliminierung;
• ein Nacktes Paar existiert, aber außerhalb des Paars stehen keine zusätzlichen Paarziffern mehr.

Mustererkennung und nützliche Schlussfolgerung sind deshalb zwei getrennte Prüfungen:

1. Erfüllt die Struktur die Definition der Technik?
2. Erzeugt die Struktur eine neue Eintragung oder Eliminierung?

Diese Unterscheidung verhindert, dass bloßes „Pattern Spotting“ das tatsächliche Lösen ersetzt.

Die Abhängigkeitskaskade

Ein Sudoku-Lösungsweg ist keine flache Folge isolierter Tricks.

Eine Eliminierung kann Kandidatenzustände an anderer Stelle verändern und dadurch etwas viel Einfacheres sichtbar machen.

Zum Beispiel:

Swordfish-Eliminierung
→ Kandidat entfernt
→ Versteckter Single erscheint
→ Eintragung
→ Locked Candidates erscheint
→ zwei weitere Kandidaten entfernt
→ Nackter Single erscheint

Das fortgeschrittene Muster kann den Durchbruch liefern, doch der Großteil des folgenden Fortschritts kehrt sofort zu einfacherer Logik zurück.

Deshalb scannt eine gute Lösungsstrategie nach jeder bedeutenden Eliminierung erneut.

Korrektheitssolver und menschenorientierte Solver beantworten verschiedene Fragen

Software kann Sudoku auf grundlegend verschiedene Arten lösen.

Vollständiger Solver / Lösungszähler

Seine Aufgabe ist, Fragen zu beantworten wie:

• Existiert eine Lösung?
• Wie viele Lösungen existieren?
• Wie sieht das vollständige Raster aus?

Suche, Exact Cover, Constraint-Propagation und Backtracking sind hier nützlich.

Menschenorientierter Analyzer

Seine Aufgabe ist eine andere:

• Welche erklärbare Schlussfolgerung ist verfügbar?
• Welche Technik beschreibt sie?
• Welcher Kandidat wird eliminiert?
• Welche Schwierigkeit soll der Schritt erhalten?
• Welchen Hinweis soll ein Spieler sehen?

Ein vollständiger Solver kann die Korrektheit eines Sudoku beweisen, ohne einen menschlich wirkenden Lernpfad zu erzeugen.

Ein menschenorientierter Solver kann einen eleganten Weg beschreiben, ohne für einen Computer die schnellste Methode zur Endlösung zu sein.

Beide sind nützlich, weil sie unterschiedliche Produkt- und mathematische Probleme lösen.

Eindeutigkeit ist eine zusätzliche Voraussetzung

Der größte Teil des Korpus verwendet nur die normalen Sudoku-Bedingungen.

Eindeutigkeitstechniken fügen eine weitere Voraussetzung hinzu:

Dieses Rätsel ist nachweislich eindeutig lösbar.

Damit werden Schlussfolgerungen wie Unique Rectangle und BUG+1 möglich.

Die Voraussetzung muss ausdrücklich bleiben, weil ein Kandidat mit allen lokalen Zeilen-/Spalten-/Blockregeln vereinbar sein und trotzdem verboten werden kann, wenn er eine zweite gültige Vervollständigung ermöglichen würde.

Deshalb sind Unique Solution und Unique Rectangle miteinander verbunden, aber nicht dasselbe Thema:

• das eine erklärt eine Eigenschaft des gesamten Rätsels;
• das andere verwendet diese Eigenschaft als Lösungsvoraussetzung.

Logik braucht keine universelle Reihenfolge der Techniken

Zwei kompetente Solver können unterschiedliche nächste Schritte finden.

Einer entdeckt vielleicht:

• einen Versteckten Single;

ein anderer zuerst:

• eine Locked-Candidates-Eliminierung;

und ein dritter:

• eine Teilmenge, die später zum selben Fortschritt führt.

Sudoku-Logik besitzt häufig mehrere gültige Beweiswege.

Ein menschenorientierter Solver benötigt deshalb beides:

• Korrektheit — jeder Schritt ist begründet;
• Policy — welcher gültige Schritt bevorzugt präsentiert wird.

Diese Policy beeinflusst Schwierigkeitsbewertung, Hinweise und die wahrgenommene Eleganz eines Lösungswegs.

Ein kompaktes Modell für logisches Lösen

Wenn unklar ist, nach welcher Art „Beweis“ du suchst, reduziere die Situation auf diese Fragen:

1. Was ist aktuell möglich? — Kandidaten.
2. Was ist reserviert? — Singles/Teilmengen/Fish/Positionsbeschränkungen.
3. Was kann nicht gleichzeitig wahr sein? — schwache Beziehungen.
4. Was kann nicht gleichzeitig falsch sein? — starke Beziehungen.
5. Was folgt, wenn sich dieser Zustand ändert? — Implikationen/Chains.
6. Erzeugt eine Annahme Unmöglichkeit? — Widerspruch.
7. Nutze ich eine zusätzliche Voraussetzung? — Eindeutigkeit, Variantenbedingungen usw.
8. Welche konkrete Eintragung oder Eliminierung folgt? — der nützliche Zug.

Dieser Rahmen skaliert vom Anfängerdenken bis zu fortgeschrittenem Sudoku, ohne die grundlegende Definition eines Beweises zu ändern.

FAQ

Ist Kandidateneliminierung ein echter Sudoku-Zug?

Ja. Das Entfernen eines Kandidaten ist Fortschritt, sobald die Schlussfolgerung beweist, dass dieser Kandidat unmöglich ist.

Beruhen fortgeschrittene Techniken auf anderen Sudoku-Regeln?

Normalerweise nicht. Die meisten sind tiefere Folgen derselben Zeilen-, Spalten- und Blockbedingungen. Eindeutigkeitstechniken sind ein wichtiger Sonderfall, weil sie ausdrücklich eine zusätzliche Voraussetzung einer eindeutigen Lösung verwenden.

Ist Widerspruch dasselbe wie Raten?

Nein. Ein Widerspruchsbeweis nimmt einen Zustand an, um zu beweisen, dass er unmöglich ist. Zufälliges Raten wählt einen Zustand ohne Beweis und behandelt ihn anschließend so, als sei er richtig.

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

Mehrere gültige Schlussfolgerungen können gleichzeitig vorhanden sein, und Solver verwenden unterschiedliche Suchprioritäten sowie verschiedene Technikbibliotheken.

Erzeugt jedes gültige Muster eine Eliminierung?

Nein. Eine Struktur kann die Definition einer Technik erfüllen und im aktuellen Raster trotzdem kein nützliches Ziel besitzen.

Besteht Sudoku-Logik nur aus Eliminierungen?

Nein. Sudoku-Schlussfolgerungen umfassen Eintragungen, Eliminierungen, Reservierungen, Implikationen und Widerspruch. Eliminierungen werden mit steigender Schwierigkeit immer wichtiger.

Ist ein Computer-Solver noch „Logik“?

Das hängt vom Solver ab. Ein vollständiger Suchsolver kann Lösungen finden, ohne menschenorientierte Deduktionen zu erzeugen. Ein Human-Style-Analyzer ist gezielt darauf ausgelegt, erklärbare logische Schritte auszugeben.

Was als Nächstes lernen?

Lies Sudoku Chains, um Implikationssprache in konkrete Kettenschlussfolgerungen umzusetzen, Muss man bei Sudoku raten? für die Grenze zwischen Beweis und Suche sowie Sudoku und Mathematik für die algorithmische Sicht auf das Rätsel.