Sudoku: XY-Wing
Der XY-Wing ist eigentlich eine kurze XY-Chain aus drei Zellen. Allen Chains ist gemein, dass der erste und der letzte Kandidat der Chain denselben Wert haben. Nach der Logik von Chains müssen einer oder beide Kandidaten die Lösungs-Zahl für die jeweilige Zelle sein. Alle Zellen, welche nicht zum XY-Wing gehören und die erste und letzte Zelle des XY-Wings gleichzeitig sehen, können nach den Sudoku-Regeln diese Zahl nicht auch enthalten. Dieser Kandidat kann somit aus diesen Zellen gelöscht werden.
XY-Wings findet man nur mit Hilfe des Kandidaten-Gitters. Um Zellen mit genau zwei Kandidaten schnell zu finden, ist die Funktion Zellen mit einer bestimmten Anzahl Kandidaten färben ein praktisches Hilfsmittel.
Bei der Suche nach XY-Wings konzentriert man sich auf Zellen mit genau zwei Kandidaten. Man startet mit einer solchen zweiwertigen Zelle. Diese Zelle ist der Pivot (Angelpunkt). Die beiden Kandidaten der Zelle benennt man mit X und Y. Danach sucht man zwei weitere Zweier-Zellen, welche die Pivot-Zelle sehen können. Diese Zellen nennt man Pincer (Zangen). Einer der Kandidaten der ersten Pincer Zelle muss den Wert X haben. Den anderen Kandidaten dieser Zelle nenne ich Z. Einer der Kandidaten der zweiten Pincer-Zelle muss den Wert Y haben. Der andere Kandidat dieser Zelle muss ebenfalls den Wert Z haben. Die Pincer-Zellen dürfen nicht im selben Haus liegen, da es sich sonst nicht um einen XY-Wing handelt, sondern um ein Naked Triple.
Logik des XY-Wings
Die beiden Z-Kandidaten bilden den Anfang und das Ende der Kette. Die durch den XY-Wing gebildete Kette sieht wiefolgt aus:
- ( Z ⇔ X ) ↔ ( X ⇔ Y ) ↔ ( Y ⇔ Z )
Hier sind die Chain-Regeln erfüllt. Die Kandidaten, die durch die grossen Buchstaben X, Y und Z gekennzeichnet sind, bilden die Kettenglieder. Zwischen den Kandidaten einer Zelle bestehen jeweils Strong Links, zwischen den Zellen Weak Links.
Die Logik von Chains besagt nun, dass einer der beiden Kandidaten Z oder beide die Lösungs-Zahl für die jeweilige Zelle sein müssen. Beide Z Kandidaten nicht gesetzt ist nicht möglich. Daher kann der Kandidat Z aus allen nicht zum XY-Wing gehörenden Zellen gelöscht werden, welche die beiden Pincer-Zellen gleichzeitig sehen.
Beispiel XY-Wing
Zahlen-Gitter
Kandidaten-Gitter
Die Sudoku-App füllt die Zellen eines XY-Wings mit hellbauer Farbe. Die beiden Pincer-Zellen werden etwas dunkler gezeichnet. Die Zellen des XY-Wings bilden eine kurze XY-Chain. Die Zellen der Chain werden im Zahlen-Gitter nummeriert. Die Pivot-Zelle des XY-Wings hat die Nummer (2), die beiden Pincer-Zellen haben die Nummern (1) und (3).
In diesem Beispiel betrachten wir die hellblauen Zellen. Jede dieser Zellen enthält ganau zwei Kandidaten. Die Pivot-Zelle (2) enthält die beiden Kandidaten X = 7 und Y = 9. Die Pincer-Zelle (1) sieht die Pivot-Zelle (sie ist in derselben Zeile) und enthält einen Kandidaten X = 7. Der andere Kandidat ist Z = 2. Die Pincer-Zelle (3) sieht ebenfalls die Pivot-Zelle (sie ist in derselben Box), ist aber nicht im selben Haus wie die Zelle (1), was eine Bedingung für den XY-Wing ist. Sie enthält einen Kandidaten Y = 9. Der andere Kandidat dieser Zelle ist Z = 2. Die beiden Z Kandidaten der Pincer-Zellen haben also denselben Wert und sind violett markiert.
Nach der Logik des XY-Wings muss einer der violett markierten Kandidaten mit der Nummer 2 (oder beide) die Lösungs-Zahl für die entsprechende Zelle sein. In welchen Pincer-Zellen die Lösungs-Zahl gesetzt werden kann, können wir noch nicht sagen. Wir wissen nur, dass mindestens eine der Pincer-Zellen die Lösungs-Zahl 2 enthalten muss. Daher können andere Zellen, welche beide Pincer-Zellen gleichzeitig sehen, diese Lösungs-Zahl nicht auch enthalten. Im Beispiel sehen die roten Zellen die beiden Pincer-Zellen und enthalten je einen Kandidaten 2. Die rot markierten Kandidaten können also gelöscht werden.
Die Lösungs-Zahlen für die Zellen des XY-Wings wissen wir an dieser Stelle noch nicht, aber durch das Ausschliessen von 2-er Kandidaten in anderen Zellen sind wir einen Schritt weiter gekommen.
Die Chain für dieses Beispiel ist:
- r8c4( 2 ⇔ 7 ) ↔ r8c9( 7 ⇔ 9 ) ↔ r9c8( 9 ⇔ 2 )
Die Strong Links befinden sich beim XY-Wing immer innerhalb der Zellen, die Weak Links zwischen zwei Zellen.