WaBis

walter.bislins.ch

Sudoku: X-Chain Nice Loop

X-Chains gibt es in drei Varianten: normale X-Chain, X-Chain Nice Loop und X-Chain Discontinuous Loop. Eine X-Chain Nice Loop besteht aus einer geraden Anzahl Kettengliedern. X-Chains Nice Loops sind Ketten, die nur Kandidaten mit der gleichen Zahl verwenden. Die Start- und End-Zelle der Kette sehen einander, sind also im selben Haus. Dadurch bildet die Kette eine geschlossene Schleife (Loop).

Chains verlangen, dass jeder zweite Link ein Strong Link sein muss. Die anderen Links dürfen Weak Links sein. Weil eine X-Chain Nice Loop aus einer geraden Anzahl Kettengliedern besteht, symmetrisch und geschlossen ist, kann jedes der Kettenglieder als Startpunkt der Kette betrachtet werden.

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 geraden Anzahl Zellen besteht und die erste und letzte Zelle der Kette im selben Haus sind (gleiche Zeile, Spalte oder Box), bildet die Kette eine X-Chain Nice Loop.

Ist eine solche Kette gefunden, färbt man die Zellen abwechslungsweise mit zwei verschiedenen Farben ein (dies erledigt die Sudoku-App). Dann sucht man Zellen ausserhalb der Chain, welche zwei Zellen mit zwei verschiedenen Farben gleichzeitig sehen. Aus diesen Zellen kann der betrachtete Kandidat X gelöscht werden.

Logik der X-Chain Nice Loop

Um die Logik hinter X-Chains Nice Loops zu verstehen, muss man die Grundlagen zu Links und Chains beherrschen. Eine X-Chain Nice Loop zum Beispiel der Länge 6 hat den folgenden Aufbau. Für die nachfolgenden Betrachtungen färben wir alle ungeraden Zellen grün und alle geraden Zellen blau ein.

|↔ (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.

Finden wir heraus, was die Chain bewirkt: Wir starten bei der ersten grünen Zelle, die einen Strong Link zur nächsten blauen Zelle 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 zweiten Zelle sein. In der ditten Zelle kann dann die Lösungs-Zahl X ausgeschlossen werden usw.

|→ (-X)(+X)(-X)(+X)(-X)(+X) →|

Wir sehen, dass unter dieser Annahme in jeder blauen Zelle X die Lösungs-Zahl sein muss.

Wenn wir aber annehmen, dass in der letzten Zelle der Kandidat X nicht die Lösungs-Zahl der Zelle ist, können wir dieselbe Logik in Gegenrichtung anwenden:

|← (+X)(-X)(+X)(-X)(+X)(-X) ←|

Wir sehen, dass unter dieser Annahme in jeder grünen Zelle X die Lösungs-Zahl sein muss.

Zusammenfassend können wir sagen, dass entweder in allen blauen oder in allen grünen Zellen X die Lösungs-Zahl sein muss. Damit kann in allen Zellen, die nicht zur X-Chain gehören, die aber sowohl eine grüne als auch eine blaue Zelle gleichzeitig sehen, der Kandidat X für diese Zelle ausgeschlossen werden kann. Er kann aus diesen Zellen gelöscht werden.

Beispiel X-Chain Nice Loop 6

Zahlen-Gitter
X-Chain Nice Loop

Kandidaten-Gitter
X-Chain Nice Loop Kandidaten-Gitter

Code: (1579)(4567)(1567)(259)8(256)3(2679)(2479) (389)(468)(6)(239)715(269)(249) (3579)(567)24(356)(356)(79)18 (2578)(2578)(57)(35)(35)9(178)46 (57)9461823(57) 613724(89)(589)(59) 43(15)8976(25)(125) (257)(2567)814(2356)(79)(2579)(23579) (1257)(2567)9(235)(356)(2356)(1478)(2578)(123457) (Methode 35/37)

In diesem Beispiel betrachten wir alle Zellen, die den Kandidaten 1 enthalten. Die Zellen der gefundenen X-Chain Nice Loop sind grün und blau gefärbt. Die Reihenfolge der Kettenglieder ist im Zahlen-Gitter nummeriert. Die erste Zelle (1) und die letzte Zelle (6) der Kette sind im selben Haus (gleiche Zeile), womit die Kette geschlossen ist.

Nach der Logik der X-Chain Nice Loop muss entweder in allen grünen Zellen oder in allen blauen Zellen der Kandidat 1 die Lösungs-Zahl der jeweiligen Zelle sein.

Die rote Zelle ist eine Zelle ausserhalb der Chain, die sowohl eine grüne Zelle (3) als auch eine blaue Zelle z.B. (4) sieht. Da entweder die Zelle (3) oder die Zelle (4) als Lösungs-Zahl eine 1 enthalten muss, kann diese Zahl aus der roten Zelle ausgeschlossen werden. Der rote Kandidat 1 kann aus der roten Zelle gelöscht werden.

Beachte, dass zwischen den Zellen (1) und (2), (3) und (4), (5) und (6) 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), (6) und (1) dürfen Weak Links bestehen. In diesem Beispiel sind zwei der Weak Links ebenfalls Strong Links, was aber nach den Chain-Regeln erlaubt ist.

Vergleich X-Chain Nice Loop 4 mit X-Wing

Eine X-Chain Nice Loop mit nur 4 Kettengliedern hat eine gewisse Änlichkeit mit einem X-Wing. Die X-Chain ist jedoch einfacher zu erkennen und man kann in der Regel mehr Kandidaten löschen als beim X-Wing. Die folgenden Bilder zeigen den Unterschied:

Kandidaten-Gitter (X-Wing)
X-Wing Kandidaten-Gitter

Kandidaten-Gitter (X-Chain Loop 4)
X-Chain Loop Kandidaten-Gitter

Code: 000000300 000071500 002400018 000009040 090618230 610700000 430807600 008140000 009000000 (Methoden 28/38 und 29/38)

Weitere Infos zur Seite
Erzeugt Mittwoch, 20. Februar 2013
von wabis
Zum Seitenanfang
Geändert Samstag, 18. Juli 2015
von wabis