[Kettenlogik ①] Grundlagen: Starke und schwache Verbindungen
Kettenlogik (Chain) ist das zentrale theoretische Rahmenwerk für fortgeschrittene Sudoku-Techniken. Fast alle fortgeschrittenen Eliminierungstechniken — vom einfachen X-Wing bis zu komplexen AICs — können durch Kettenlogik verstanden und beschrieben werden. Dieser Artikel erkundet die zwei grundlegendsten Konzepte der Kettenlogik: starke Verbindungen und schwache Verbindungen.
Was ist eine Kette?
Im Sudoku ist eine Kette (Chain) eine Sequenz von Verbindungen zwischen Kandidaten durch bestimmte logische Beziehungen. Stellen Sie sich vor: Wenn wir zwischen Kandidaten Schlussfolgerungsbeziehungen wie „wenn A wahr ist, dann ist B wahr/falsch" etablieren und diese Beziehungen verknüpfen können, bilden wir eine Kette.
Das Wesen einer Kette ist logische Weitergabe: Von einem Punkt ausgehend, durch eine Reihe logischer Schlussfolgerungen, zu einer Schlussfolgerung gelangend. Diese Schlussfolgerung wird typischerweise verwendet um:
- Zu bestimmen, dass ein Kandidat wahr sein muss (Platzierung bestätigen)
- Zu bestimmen, dass ein Kandidat falsch sein muss (Kandidat eliminieren)
Um Ketten zu verstehen, müssen wir zuerst die Grundeinheiten verstehen, die Ketten bilden: Verbindungen (Links). Verbindungen beschreiben die logische Beziehung zwischen zwei Kandidaten, unterteilt in starke und schwache Verbindungen basierend auf der Stärke der Beziehung.
Starke Verbindung (Strong Link)
Eine starke Verbindung existiert zwischen zwei Kandidaten A und B genau dann, wenn: genau einer von A und B wahr ist, und der andere falsch.
Mit anderen Worten, wenn A falsch ist, muss B wahr sein, und wenn A wahr ist, muss B falsch sein (gegenseitig ausschließend und vollständig).
Notation: A = B oder A ═══ B (Doppellinie)
Quellen starker Verbindungen
Starke Verbindungen können aus folgenden Situationen entstehen:
1. Starke Verbindung in einer Bi-Wert-Zelle
Wenn eine Zelle nur zwei Kandidaten hat, existiert eine starke Verbindung zwischen diesen zwei Kandidaten.
Logik: Wenn 4 falsch ist, muss die Zelle 7 sein; wenn 7 falsch ist, muss die Zelle 4 sein.
Bi-Wert-Zellen sind die häufigste Quelle starker Verbindungen, da sie intuitiv sind: Die Zelle enthält entweder diese Zahl oder jene.
2. Starke Verbindung aus konjugiertem Paar
Wenn eine Ziffer nur an zwei Positionen innerhalb einer Einheit (Zeile, Spalte oder Block) erscheint, existiert eine starke Verbindung zwischen diesem Kandidaten an diesen zwei Positionen. Diese Beziehung wird konjugiertes Paar genannt.
Logik: Zeile 5 muss eine 3 haben. Wenn R5C2 nicht 3 ist, muss R5C8 3 sein; und umgekehrt.
Die beiden Enden einer konjugierten Paar-Verbindung sind dieselbe Ziffer an verschiedenen Positionen, nicht verschiedene Ziffern an derselben Position. Dies unterscheidet sich grundlegend von starken Verbindungen in Bi-Wert-Zellen.
3. Gruppierte starke Verbindung
Allgemeiner gilt: Wenn eine Gruppe von Kandidaten und eine andere Gruppe die Beziehung „genau eine Gruppe ist wahr" erfüllen, existiert eine starke Verbindung. Dies wird in fortgeschrittenen Techniken behandelt und im dritten Artikel dieser Serie ausführlich diskutiert.
Kerneigenschaften starker Verbindungen
- Genau einer wahr: Genau ein Ende einer starken Verbindung ist wahr, das andere ist falsch
- Falsch propagiert wahr: Wenn ein Ende falsch ist, muss das andere wahr sein
- Wahr propagiert falsch: Wenn ein Ende wahr ist, muss das andere falsch sein
Schwache Verbindung (Weak Link)
Eine schwache Verbindung existiert zwischen zwei Kandidaten A und B genau dann, wenn: wenn A wahr ist, dann muss B falsch sein.
Mit anderen Worten, höchstens einer von A und B ist wahr (beide können falsch sein, aber beide können nicht wahr sein).
Notation: A - B oder A ─── B (Einfachlinie)
Quellen schwacher Verbindungen
Schwache Verbindungen haben ebenfalls mehrere Quellen:
1. Schwache Verbindung zwischen verschiedenen Kandidaten in derselben Zelle
Innerhalb derselben Zelle existiert eine schwache Verbindung zwischen zwei beliebigen verschiedenen Kandidaten.
Logik: Eine Zelle kann nur eine Zahl enthalten. Wenn 1 platziert wird, kann es nicht 5 sein.
2. Schwache Verbindung zwischen gleichen Kandidaten in derselben Einheit
Innerhalb derselben Einheit (Zeile, Spalte oder Block) existieren paarweise schwache Verbindungen zwischen allen Positionen desselben Kandidaten.
Logik: Eine Ziffer kann nur einmal in einem Block erscheinen. Wenn R1C7 6 ist, können R2C8 und R3C9 nicht 6 sein.
Im Vergleich zu starken Verbindungen sind schwache Verbindungen allgegenwärtiger. Tatsächlich definieren die Grundregeln des Sudoku (keine wiederholten Ziffern in Zeile, Spalte oder Block; eine Ziffer pro Zelle) im Wesentlichen eine große Anzahl von schwachen Verbindungsbeziehungen.
Kerneigenschaften schwacher Verbindungen
- Höchstens einer wahr: Höchstens ein Ende einer schwachen Verbindung ist wahr
- Wahr propagiert falsch: Wenn ein Ende wahr ist, muss das andere falsch sein
- Können beide falsch sein: Beide Enden können gleichzeitig falsch sein (anders als starke Verbindungen!)
Vergleich von starken und schwachen Verbindungen
Das Verständnis des Unterschieds zwischen starken und schwachen Verbindungen ist der Schlüssel zur Beherrschung der Kettenlogik. Fassen wir mit einer Vergleichstabelle zusammen:
| Eigenschaft | Starke Verbindung | Schwache Verbindung |
|---|---|---|
| Kerneigenschaft | Genau einer wahr, einer falsch | Höchstens einer wahr |
| Logische Weitergabe | Falsch → Wahr, Wahr → Falsch | Wahr → Falsch |
| Können beide wahr sein | ✗ Nein | ✗ Nein |
| Können beide falsch sein | ✗ Nein | ✓ Ja |
| Notation | ═══ (Doppellinie) oder = | ─── (Einfachlinie) oder - |
| Häufige Quellen | Bi-Wert-Zellen, Konjugierte Paare | Gleiche Zelle versch. Ziffern, Gleiche Einheit gleiche Ziffer |
Sonderfall: Starke Verbindungen sind auch schwache Verbindungen
Hier ist ein wichtiges Konzept zu verstehen: Starke Verbindungen sind oft auch schwache Verbindungen.
Starke Verbindung Perspektive: Wenn 4 falsch ist, muss 7 wahr sein → Starke Verbindung existiert
Schwache Verbindung Perspektive: Wenn 4 wahr ist, muss 7 falsch sein → Schwache Verbindung existiert auch
Schlussfolgerung: Diese zwei Kandidaten haben sowohl eine starke als auch eine schwache Verbindung!
Starke Verbindung Perspektive: Wenn 3 bei R5C2 falsch ist, muss 3 bei R5C8 wahr sein → Starke Verbindung existiert
Schwache Verbindung Perspektive: Wenn 3 bei R5C2 wahr ist, muss 3 bei R5C8 falsch sein (gleiche Zeile kann keine zwei 3en haben) → Schwache Verbindung existiert auch
Schlussfolgerung: Konjugierte Paare erfüllen auch beide Bedingungen!
Wenn zwei Kandidaten die Beziehung „genau einer wahr, einer falsch" erfüllen (weder beide wahr noch beide falsch möglich), haben sie sowohl eine starke als auch eine schwache Verbindung. Dies ist die „stärkste" Verbindungsbeziehung und sehr nützlich beim Kettenaufbau.
Merkhilfe: Bi-Wert-Zellen und konjugierte Paare haben immer sowohl starke als auch schwache Verbindungen.
Das Konzept des „Sehens"
Bei der Kettenlogik wird das Konzept des „Sehens" (see) häufig verwendet. Das Verständnis von „Sehen" ist entscheidend für die Identifizierung von Verbindungsbeziehungen.
Kandidat A „sieht" Kandidat B bedeutet, dass eine schwache Verbindung zwischen A und B existiert.
Wenn A wahr ist, dann muss B falsch sein — A kann B „eliminieren".
„Sehen"-Beziehungen existieren zwischen:
- Verschiedenen Kandidaten in derselben Zelle
- Gleichem Kandidaten in derselben Zeile
- Gleichem Kandidaten in derselben Spalte
- Gleichem Kandidaten im selben Block
Dieses Konzept wird häufig bei der Diskussion von Kettenanwendungen verwendet, wie „Kandidaten, die von beiden Enden gesehen werden können, können eliminiert werden".
Warum ist die Unterscheidung zwischen starken und schwachen Verbindungen so wichtig?
Die Unterscheidung zwischen starken und schwachen Verbindungen ist der Grundstein der Kettenlogik. Ihre Unterschiede bestimmen:
Starke Verbindungen erlauben es, „wahr" aus „falsch" zu schließen; schwache Verbindungen erlauben es, „falsch" aus „wahr" zu schließen. Kettenlogik nutzt diese beiden verschiedenen Weitergaberichtungen, um komplexe logische Schlussfolgerungen aufzubauen.
Beim Aufbau von Ketten müssen Sie korrekt identifizieren, ob jeder Schritt eine starke oder schwache Verbindung ist, um korrektes Schlussfolgern zu gewährleisten. Eine schwache Verbindung fälschlicherweise als starke zu behandeln führt zu falschen Schlussfolgerungen.
Viele scheinbar verschiedene Techniken (wie X-Wing, Skyscraper, XY-Wing usw.) sind im Wesentlichen Ketten mit spezifischen Mustern. Das Verständnis von starken und schwachen Verbindungen ermöglicht es Ihnen, diese Techniken in einem einheitlichen Rahmen zu verstehen.
Nächste Schritte
Dieser Artikel hat die zwei grundlegendsten Konzepte der Kettenlogik vorgestellt: starke und schwache Verbindungen. Mit dem Verständnis dieser Konzepte können wir beginnen zu lernen, wie wir sie kombinieren, um vollständige Ketten aufzubauen.
Im nächsten Artikel werden wir diskutieren:
- Wie man starke und schwache Verbindungen abwechselnd verwendet, um Ketten aufzubauen
- Regeln für die Weitergabe von wahr/falsch-Zuständen in Ketten
- Der „Färbungs"-Ansatz bei der Kettenlogik
- Methoden, um Schlussfolgerungen aus Kettenenden zu ziehen
- Sudoku-Glossar - Schnellreferenz für in diesem Artikel verwendete Begriffe
- XY-Wing Technik - Praktische Anwendung der Kettenlogik
- XY-Chain Technik - Erweiterte Anwendung von Bi-Wert-Zellenketten