WaBis

walter.bislins.ch

Sudoku: XY-Chain

XY-Chains sind 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. XY-Chains gibt es in zwei Varianten: normale XY-Chains wie hier beschrieben, und die XY-Chain Loop.

XY-Chains 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. 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.

Der Aufbau einer XY-Chain 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 erste und letzte Zelle der Kette wird dunkler gefärbt. Die Kandidaten dieser Zellen werden im Kandidaten-Gitter abwechslungsweise grün und blau markiert, der erste und letzte Kandidat Z wird violett markiert. Eine XY-Chain ist symmetrisch. Das heisst, sie kann auch vom Ende zum Start gebildet werden. Die Sudoku-App präsentiert nur eine Variante.

Allen Chains ist gemein, dass der erste und der letzte Kandidat der Chain denselben Wert Z haben muss. Nach den Chain-Regeln müssen alle ungeraden Links zwischen zwei Kandidaten Strong Links sein, alle geraden Links dürfen Weak Links sein. Nach der Logik von Chains muss der erste Kandidat Z oder der letzte Kandidat Z der XY-Chain (oder beide) die Lösungs-Zahl der entsprechenden Zelle sein. Für alle Zellen, welche nicht zur XY-Chain gehören und die erste und letzte Zelle der XY-Chain gleichzeitig sehen, kann daher nach den Sudoku-Regeln die Ketten-Ziffer Z ausgeschlossen werden. Der Kandidat Z kann aus diesen Zellen gelöscht werden.

XY-Chains 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 Kette zu bilden. Ist eine solche Kette gefunden, sucht man nach Zellen ausserhalb der Chain, welche die Start-Zelle und die End-Zelle der Kette gleichzeitig sehen. Aus diesen Zellen löscht man den Kandidaten Z.

Logik der XY-Chain

Um die Logik hinter XY-Chains zu verstehen, muss man die Grundlagen zu Links und Chains beherrschen. Eine XY-Chain 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.

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.

Fall 3 und 4: Wenn wir von der Annahme ausgehen, dass Z die Lösungs-Zahl der ersten Zelle ist, ergibt sich folgende Logik-Kette:

( +Z ⇒ -A ) → ( ?A ⇒ ?B ) → ( ?B ⇒ ?C ) → ( ?C ⇒ ?Z )

Wegen dem Weak Link zwischen der ersten und zweiten Zelle können wir nicht bestimmen, ob dort A oder B die Lösungs-Zahl ist. Es können daher ab dieser Stelle für diesen Fall keine weiteren Folgerungen gemacht werden. Dasselbe Prinzip gilt, wenn wir annehmen, dass Z die Lösungs-Zahl der letzten Zelle ist und die Logik von rechts nach links anwenden.

Zusammenfassung: Egal mit welcher der vier Annahmen wir starten, in jedem Fall ist Z die Lösungs-Zahl der ersten oder letzten Zelle, oder gar von beiden Zellen. Wir können zwar noch nicht bestimmen, in welcher der End-Zellen Z die Lösungs-Zahl ist, aber wir können ausschliessen, dass Z die Lösungs-Zahl jener nicht zur XY-Chain gehörenden Zellen sein kann, welche die beiden End-Zellen der XY-Chain gleichzeitig sehen.

Beispiel XY-Chain 4

Zahlen-Gitter
XY-Chain

Kandidaten-Gitter
XY-Chain Kandidaten-Gitter

Code: (25678)(267)(5678)(245)319(478)(48) 3(27)(578)9(25)(45)6(478)1 419867352 (69)8(46)3(59)2(45)17 (79)531(79)(48)(48)26 1(47)2(456)(578)(4568)(458)39 (5678)(4679)(45678)(567)1(568)2(689)3 (25678)(2679)(5678)(2567)431(689)(58) (2568)31(256)(258)97(468)(458) [1]

In diesem Beispiel wurde folgende XY-Chain aus vier Zellen gefunden:

r2c6( 4 ⇔ 5 ) ↔ r2c5( 5 ⇔ 2 ) ↔ r2c2( 2 ⇔ 7 ) ↔ r6c2( 7 ⇔ 4 )

Der gemeinsame Kandidat Z der Start- und End-Zelle ist 4 (violett markiert). Einer der beiden muss nach der Logik der XY-Chain die Lösungs-Zahl der entsprechenden Zelle sein.

Die rote Zelle sieht sowohl die Start-Zelle der Kette, als auch die End-Zelle der Kette. Da für eine dieser beiden Zellen (oder für beide) die Ziffer 4 die Lösungs-Zahl sein muss, kann nach den Sudoku-Regeln der Kandidat 4 für die rote Zelle ausgeschlossen werden. Der rot markierte Kandidat 4 kann somit gelöscht werden.

Hinweis: In diesem Beispiel muss man noch eine XY-Chain der Länge 6 und eine XY-Chain Loop der Länge 6 anwenden, um die Lösung des Rätsels zu finden.

Verwandte Methode der XY-Chain

Eine der XY-Chain verwandte Methode stellt die XY-Wing Chain dar. Sie ist eine XY-Chain, in welcher die Zellen zwischen den Start- und End-Zellen identische Kandidaten-Paare enthalten:

Die durch die XY-Wing Chain gebildete Kette sieht wiefolgt aus, wenn sie aus 5 Zellen besteht:

( Z ⇔ X ) ↔ ( X ⇔ Y ) ↔ ( Y ⇔ X ) ↔ ( X ⇔ Y ) ↔ ( Y ⇔ Z )

 XY-Wing Chain

Quellen

www.ahr-sudoku.de
http://www.ahr-sudoku.de/solving.php/technic/Double%20Implication%20Chain
Weitere Infos zur Seite
Erzeugt Sonntag, 17. Februar 2013
von wabis
Zum Seitenanfang
Geändert Sonntag, 6. Dezember 2015
von wabis