WaBis

walter.bislins.ch

Sudoku: X-Chain Discontinuous Loop

X-Chains gibt es in drei Varianten: normale X-Chain, X-Chain Nice Loop und X-Chain Discontinuous Loop. Eine X-Chain Discontinuous Loop besteht aus einer ungeraden Anzahl Kettengliedern mit mindestens 5 Gliedern. X-Chains Discontinuous Loops sind Ketten, die nur Kandidaten mit der gleichen Zahl verwenden. Diese X-Chain ist eine degenerierte Form der X-Chain Nice Loop, bei welcher die Start- und End-Zelle identisch ist. Daher die ungerade Anzahl Kettenglieder.

Chains verlangen, dass jeder zweite Link ein Strong Link sein muss. Die anderen Links dürfen Weak Links sein. Weil die Start-Zelle mit der End-Zelle identisch ist, bildet die X-Chain Discontinuous Loop eine Ausnahme der Regel. Zur Start- und End-Zelle der Loop führen zwei Strong Links. Weil dadurch die abwechselnde Link-Art unterbrochen wird, hat diese Kette den Zusatz Discontinuous (nicht kontinuierlich) im Namen.

X-Chains findet man nur mit Hilfe des Kandidaten-Gitters. Am besten nimmt man dazu den Filter-Modus zuhilfe. Man konzentriert sich auf eine bestimmte Kandidaten-Zahl X und sucht Zellen, die diesen Kandidaten enthalten. Dann versucht man diese Zellen nach den Chain-Regeln zu einer Kette zu verbinden. Wenn die Kette aus einer ungeraden Anzahl Zellen besteht und die erste und letzte Zelle der Kette dieselbe Zelle ist, bildet die Kette eine X-Chain Discontinuous Loop.

Ist eine solche Kette gefunden, färbt man die erste/letzte Zelle gelb und die anderen Zellen abwechslungsweise mit den zwei Farben grün und blau ein (dies erledigt die Sudoku-App). Damit lässt sich die Logik der Kette besser erkären.

In der gelben Zelle kann nur X die Lösungs-Zahl sein.

Logik der X-Chain Discontinuous Loop

Um die Logik hinter X-Chains Discontinuous Loops zu verstehen, muss man die Grundlagen zu Links und Chains beherrschen. Eine X-Chain Discontinuous Loop zum Beispiel der Länge 5 hat den folgenden Aufbau. Für die nachfolgenden Betrachtungen färben wir alle ungeraden Zellen grün und alle geraden Zellen blau ein. Die erste/letzte Zelle wird rot gefärbt.

(X)(X)(X)(X)(X)(X)

Jeder Ausdruck (X) stellt eine eigene Zelle dar, welche den Kandidaten X enthält. Die Sudoku-App nummeriert die Zellen der Kette im Zahlen-Gitter. Die Zellen der Kette werden abwechslungsweise grün und blau gefüllt und der Chain-Kandidat wird mit der gleichen Farbe markiert. Bei den beiden roten Zellen an den Enden der Kette handelt es sich um ein und dieselbe Zelle!

Finden wir heraus, was die Chain bewirkt: Wir starten bei der ersten roten Zelle (1), die einen Strong Link zur nächsten Zelle (2) hat und betrachten den Fall, dass in der ersten Zelle der Kandidat X nicht die Lösungs-Zahl der Zelle sei. Dann muss der Kandidat X wegen dem Strong Link die Lösungs-Zahl der blauen Zelle (2) sein. In der grünen Zelle (3) kann in diesem Fall die Lösungs-Zahl X ausgeschlossen werden usw.

In allen blauen Zellen muss X in diesem Fall die Lösungs-Zahl sein und in allen grünen Zellen kann X nicht die Lösungs-Zahl sein. Weil die letzte grüne Zelle mit einem Strong-Link zur letzten roten Zelle verbunden ist, müsste in dieser Zelle X die Lösungs-Zahl sein. Nun ist aber die letzte rote Zelle mit der ersten roten Zelle identisch! Wenn wir also annehmen, dass in der roten Zelle X nicht die Lösungs-Zahl ist, kommen wir zu dem Schluss, dass X die Lösungs-Zahl dieser Zelle sein muss!

(-X)(+X)(-X)(+X)(-X)(+X)

Betrachten wir den Fall, dass in der ersten Zelle X der Kandidate sei. Dann sieht die Logik-Kette wiefolgt aus:

(+X)(-X)(?X)(?X)(?X)(?X)

Wenn in der ersten blauen Zelle X nicht die Lösungs-Zahl ist, kann wegen dem Weak Link die nächste grüne Zelle X als Lösungs-Zahl enthalten oder auch nicht. Ab dieser Stelle können wir keine weiteren Schlussfolgerungen ziehen. Da aber die erste und letzte rote Zelle dieselbe Zelle ist, muss in diesem Fall X die Lösungs-Zahl dieser Zelle sein.

Da die Kette symmetrisch ist, kann diese Logik auch in der anderen Richtung betrachtet werden. Egal mit welchem Fall man startet (X in der roten Zelle gesetzt oder nicht), wir enden immer damit, dass X die Lösungs-Zahl der roten Zelle sein muss.

Zusammenfassend können wir sagen, in der roten (bzw. der gelben Zelle im Zahlen- und Kandidaten-Gitter) muss auf jeden Fall X die Lösungs-Zahl der Zelle sein!

Aus den benachbarten Zellen kann X als Lösungs-Zahl ausgeschlossen werden. Der Kandidat X wird von der Sudoku-App im nächsten Schritt austomatisch aus diesen Zellen entfernt. In den übrigen Zellen der Kette ist noch unbestimmt, ob X die Lösungs-Zahl ist oder nicht.

Beispiel X-Chain Discontinuous Loop

Zahlen-Gitter
X-Chain Discontinuous Loop

Kandidaten-Gitter
X-Chain Discontinuous Loop Kandidaten-Gitter

Code: 8(19)4537(169)(1269)(129) (79)23614(79)85 6(17)5982(17)34 (349)(3469)(269)1(469)587(29) 5(49)(129)7(49)83(129)6 (179)8(1679)2(69)345(19) 2(467)(167)859(16)(146)3 (49)5(69)3712(469)8 (139)(39)84265(19)7 (Methode 7/7)

In diesem Beispiel betrachten wir Zellen, die den Kandidaten 1 enthalten. Die Zellen der gefundenen X-Chain Discontinuous Loop sind gelb, grün und blau gefärbt. Die Reihenfolge der Kettenglieder ist im Zahlen-Gitter nummeriert. Die gelbe Zelle (1) ist gleichzeitig die erste und die letzte Zelle der Kette. Dadurch ist die Kette zu einer Loop geschlossen. Weil die Loop aus einer ungeraden Anzahl Zellen besteht, ist es eine Discontinuous Loop, denn zur Zelle (1) führen dadurch zwei Strong Links, was die Chain-Regeln verletzt.

Nach der Logik der X-Chain Discontinuous Loop muss in der gelben Zelle der Kandidat 1 die Lösungs-Zahl dieser Zelle sein.

Beachte, dass nach den Chain-Regeln zwischen den Zellen (1) und (2), (3) und (4), (5) und (1) ein Strong Link bestehen muss, d.h. diese Zellen-Paare müssen die einzigen zwei Zellen mit dem Kandidaten 1 im selben Haus sein. Zwischen den Zellen (2) und (3), (4) und (5) dürfen Weak Links bestehen. In diesem Beispiel ist der Link zwischen den Zellen (4) und (5) ein Strong Link, was aber nach den Chain-Regeln erlaubt ist.

Diese Chain Loop kann wiefolgt dargestellt werden:

r9c1(1)r9c8(1)r5c8(1)r5c3(1)r7c3(1)r9c1(1)

Bei den roten Zellen am Anfang und Ende der Kette handelt es sich um dieselbe Zelle.

Weitere Beispiele mit X-Chain Discontinuous Loop

Weitere Infos zur Seite
Erzeugt Samstag, 23. März 2013
von wabis
Zum Seitenanfang
Geändert Samstag, 18. Juli 2015
von wabis