Sudoku: XY-Chain Loop
XY-Chain Loops sind geschlossene Ketten, die Kandidaten mit verschiedenen Zahlen verwenden, wobei immer zwei Zahlen X und Y ein Kandidaten-Paar in einer Zelle bilden. Daher der Name XY-Chain Loop. XY-Chains gibt es in zwei Varianten: normale XY-Chains und die XY-Chain Loop wie hier beschrieben.
XY-Chains Loops bestehen aus mindestens vier Zellen, die nicht alle im selben Haus liegen dürfen. In jeder Zelle der Kette können verschiedene Kandidaten-Paare stehen, aber der erste und letzte Kandidat der Kette muss die gleiche Zahl Z sein und die erste und letzte Zelle müssen im selben Haus liegen. Da jede Zelle der Kette ein Kandidaten-Paar enthält, sind diese Kandidaten paarweise durch einen Strong Link miteinander verbunden. Zwischen den Zellen der Kette müssen daher nur Weak Links bestehen. Jede Zelle der XY-Chain Loop kann als Start-Zelle angesehen werden und die Reihenfolge der Zellen kann in zwei Richtungen betrachtet werden. Eine XY-Chain Loop kann also in mehrere Varinaten gezeichnet werden. Die Sudoku-App zeigt jeweils nur eine Variante an.
Der Aufbau einer XY-Chain Loop der Länge 4 ist folgender:
- |→ ( Z ⇔ A ) ↔ ( A ⇔ B ) ↔ ( B ⇔ C ) ↔ ( C ⇔ Z ) ←|
Jeder Ausdruck ( X ⇔ Y ) stellt eine Zelle dar, welche die Kandidaten X und Y enthält. Dieses Kandidaten-Paar ist durch einen Strong Link verbunden, weil die Kandidaten die einzigen zwei der Zelle sind. Die Sudoku-App färbt alle Zellen der Kette hellblau ein und nummeriert die Zellen im Zahlen-Gitter. Die Kandidaten dieser Zellen werden im Kandidaten-Gitter abwechslungsweise blau und grün markiert.
XY-Chain Loops findet man nur mit Hilfe des Kandidaten-Gitters. Am besten nimmt man dazu den Filter-Modus zuhilfe und lässt sich Zellen mit einer bestimmten Anzahl Kandidaten färben. Dann versucht man zwischen diesen Zellen nach obigem Aufbau eine geschlossene Kette zu bilden.
Aufgrund der hohen Symmetrie einer XY-Chain Loop können meist sehr viele Kandidaten aus Zellen ausserhalb der Loop gelöscht werden. In einer XY-Chain Loop müssen entweder alle blau markierten Kandidaten die Lösungs-Zahlen der entsprechenden Zellen sein, oder alle grün markierten. Man sucht nun externe Zellen, das sind Zellen ausserhalb der Kette, die zwei Kandidaten der Kette mit dem selben Wert X aber unterschiedlicher Farbe gleichzeitig sehen. Da entweder der blaue Kandidat X oder der grüne Kandidat X die Lösungs-Zahl der Ketten-Zellen sein muss, kann dieser Kandidat aus der externen Zelle ausgeschlossen werden.
Logik der XY-Chain Loop
Um die Logik hinter XY-Chain Loops zu verstehen, muss man die Grundlagen zu Links und Chains beherrschen. Eine XY-Chain Loop zum Beispiel der Länge 4 hat den folgenden Aufbau:
- |→ ( Z ⇔ A ) ↔ ( A ⇔ B ) ↔ ( B ⇔ C ) ↔ ( C ⇔ Z ) ←|
Die Logik funktioniert wiefolgt:
Fall 1: Nehmen wir zunächst an, der erste Kandidat Z sei nicht die Lösungs-Zahl der Zelle. Dann ergibt sich folgende Schlussfolgerungs-Kette:
- |→ ( -Z ⇒ +A ) → ( -A ⇒ +B ) → ( -B ⇒ +C ) → ( -C ⇒ +Z ) →|
Wenn Z nicht die Lösungs-Zahl der ersten Zelle ist, muss A die Lösungs-Zahl dieser Zelle sein. Damit kann aber A als Lösungs-Zahl für die zweite Zelle ausgeschlossen werden, also muss B deren Lösungs-Zahl sein, usw. Wenn wir also annehmen, dass Z nicht die Lösungs-Zahl der ersten Zelle ist, muss folglich Z die Lösungs-Zahl der letzten Zelle sein. Weil die Kette geschlossen ist, kann Z in diesem Fall nicht die Lösungs-Zahl der ersten Zelle sein, womit sich die Logik-Kette schliesst. Im Fall 1 müssen alle grün markierten Kandidaten die Lösungs-Zahlen der jeweiligen Zellen sein.
Fall 2: Die gleiche Argumentations-Kette können wir von rechts nach links bilden:
- |← ( +Z ⇐ -A ) ← ( +A ⇐ -B ) ← ( +B ⇐ -C ) ← ( +C ⇐ -Z ) ←|
Wenn wir also annehmen, dass Z nicht die Lösungs-Zahl der letzten Zelle ist, muss Z die Lösungs-Zahl der ersten Zelle sein. Im Fall 2 müssen alle blau markierten Kandidaten die Lösungs-Zahlen der jeweiligen Zellen sein.
Zusammenfassung: Wir sehen, dass entweder alle blau markierten Kandidaten die Lösungs-Zahlen der entsprechenden Zellen sein müssen, oder alle grün markierten Kandidaten. Wir können zwar noch nicht bestimmen, ob die blauen oder grünen Kandidaten die Lösungs-Zahlen sind. Aber aus einer Zelle ausserhalb der Kette, welche sowohl einen blauen Kandidaten X als auch einen grünen Kandidaten X gleichzeitig sieht, kann dieser Kandidat X nach den Sudoku-Regeln ausgeschlossen werden.
Beispiel XY-Chain Loop 6
Zahlen-Gitter
Kandidaten-Gitter
In diesem Beispiel wurde folgende XY-Chain Loop aus sechs Zellen gefunden:
- |→ r2c2( 2 ⇔ 7 ) ↔ r6c2( 7 ⇔ 4 ) ↔ r4c3( 4 ⇔ 6 ) ↔ r4c1( 6 ⇔ 9 ) ↔ r4c5( 9 ⇔ 5 ) ↔ r2c5( 5 ⇔ 2 ) ←|
Nach der Logik der XY-Chain Loop müssen entweder alle blau markierten Kandidaten die Lösungs-Zahlen sein oder alle grün markierten Kandidaten.
Jede rot markierte Zelle sieht sowohl einen blau als auch einen grün markierten Kandidaten X. Da einer dieser beiden Kandidaten die Lösungs-Zahl der entsprechenden Zelle sein muss, kann der Kandidat X aus der roten Zelle ausgeschlossen werden.
Im Beispiel sehen die roten Zellen der Spalte 2 je einen blau und grün markierten Kandidaten 7. Da einer dieser Kandidaten die Lösungszahl der entsprechenden Zelle sein muss, kann in derselben Spalte die 7 in keiner anderen Zelle mehr vorkommen. Alle rot markierten Kandidaten der roten Zellen können daher gelöscht werden.
In der Spalte 5 sehen die Rot markierten Zellen je einen blau und grün markierten Kandidaten 5. In Spalte 5 können die rot markierten 5-er Kandidaten gelöscht werden.