Die Grundlage vieler Sudoku Lösungs-Methoden sind Links (Verknüpfungen) und Chains (Ketten). Eine Chain ist eine Kette von Schlussfolgerungen, die von einer Annahme ausgeht und zu einem Ergebnis führt. Die Kettenglieder bestehen aus Kandidaten. Ein Kandidaten-Paar ist durch eine logische Verknüpfung (Link) miteinander verbunden.

Man unterscheidet zwei Arten von Links: Weak Links und Strong Links.

Weak und Strong Links

Ein Weak Link (schwache Bindung) zwischen einem Kandidaten-Paar besteht immer dann, wenn die beiden Kandidaten nicht die einzigen im selben Haus oder in derselben Zelle sind. Wenn zum Beispiel in einer Zeile noch drei oder mehr Kandidaten einer bestimmten Zahl vorkommen, so handelt es sich bei den Verbindungen zwischen je zwei dieser Kandidaten um Weak Links. Wenn in einer Zelle noch mehr als zwei Kandidaten vorkommen, so handelt es sich bei den Verbindungen zwischen diesen Kandidaten ebenfalls um Weak Links.

Ein Strong Link (starke Bindung) zwischen einem Kandidaten-Paar besteht immer dann, wenn die beiden Kandidaten die einzigen im selben Haus oder derselben Zelle sind. Wenn zum Beispiel in einer Zeile ein Kandidat einer bestimmten Zahl nur noch genau zweimal vorkommt, so handelt es sich bei der Verbindung zwischen diesem Kandidaten-Paar um einen Strong Link. Wenn in einer Zelle nur noch genau zwei Kandidaten vorkommen, so handelt es sich bei einer Verbindung zwischen diesen Kandidaten ebenfalls um einen Strong Link.

Beispiele für Weak und Strong Links

Wir wollen in der ersten Zeile des Sudokus im folgenden Bild verschiedene Links zwischen Kandidaten suchen:

Betrachten wir den Kandidaten 7. Er kommt in der ersten Zeile nur in der grünen und in der blauen Zelle vor, also genau zweimal. Daher besteht zwischen dem Kandidaten-Paar 7 in der ersten Zeile ein Strong Link. Ein Strong Link wird mit einem Doppelpfeil dargestellt:

Schreibweise: r1c2(7) ⇔ r1c9(7)

Der Kandidat 9 hingegen kommt in der ersten Zeile 3 mal vor. Zwischen zwei Paaren des Kandidaten 9 besteht daher nur ein Weak Link. Ein Weak Link wird mit einem einfachen Pfeil dargestellt:

Schreibweise: r1c2(9) ↔ r1c7(9)    /    r1c7(9) ↔ r1c9(9)    /    r1c2(9) ↔ r1c9(9)

Weak und Strong Links können auch zwischen Kandidaten einer einzigen Zelle hergestellt werden. Da in der grünen Zelle nur noch die zwei Kandidaten 7 und 9 vorkommen, besteht zwischen diesem Kandidaten-Paar ein Strong Link.

Schreibweise: r1c2(7 ⇔ 9)

In der blauen Zelle hingegen kommen noch 4 Kandidaten vor. Zwischen jedem Kandidaten-Paar dieser Zelle besteht daher nur ein Weak Link.

Schreibweise: r1c9(1 ↔ 6)    /    r1c9(6 ↔ 7)    /    usw.

Die Art der Links zwischen einem Kandidaten-Paar muss immer peinlich genau unterschieden werden, denn sie ist für die logischen Schlussfolgerungen von essenzieller Bedeutung. Alle Chain- und viele andere Sudoku Lösungs-Methoden beruhen auf einer Verkettung von Kandidaten-Paaren über eine bestimmte Reihenfolge von Weak und Strong Links. Die Methoden können nur verstanden werden, wenn man die Grundlagen zu Links und Chains verstanden hat.

Logik von Weak Links

Welche Art von Schlussfolgerung kann man aufgrund eines Links zwischen einem Kandidaten-Paar ziehen?

Betrachten wir zum Beispiel den Weak Link zwischen folgendem Kandidaten-Paar im obigen Bild:

r1c2(9) ↔ r1c7(9)

Weil der Kandidat 9 in Zeile 1 (r1) dreimal vorkommt, handelt es sich beim Link zwischen dem Kandidaten 9 in der Zelle r1c2 und der Zelle r1c7 um einen Weak Link. Bei einem Weak Link gilt folgende Schlussfolgerung:

Schreibweise: r1c2(+9) → r1c7(-9)

Die Umkehrung gilt jedoch nicht: Wenn der eine Kandidat des Paares nicht als Lösungs-Zahl der Zelle angenommen wird, weiss man nicht, ob der andere Kandidat des Paares die Lösungs-Zahl seiner Zelle ist oder nicht, da ja im selben Haus noch weitere mögliche Kandidaten vorhanden sind.

Schreibweise: r1c2(-9) → r1c7(?9)

Logik von Strong Links

Betrachten wir den folgenden Strong Link im Bild:

r1c2(7) ⇔ r1c9(7)

Weil der Kandidat 7 in Zeile 1 nur zweimal vorkommt, handelt es sich beim Link zwischen diesem Kandidaten-Paar um einen Strong Link. Bei einem Strong Link gelten folgende Schlussfolgerungen:

Schreibweise: r1c2(-7) ⇒ r1c9(+7)     und     r1c2(+7) ⇒ r1c9(-7)

Chain-Regeln

Wenn zwei Kandidaten-Paare über einen gemeinsamen Kandidaten verbunden werden, wird eine Kette mit 3 Kandidaten gebildet. Zum Beispiel wird folgende 3-er Kette mit dem gemeinsamen Kandidaten 5 der Zelle r8c1 gebildet:

r5c1(5) ⇔ r8c1(5) ↔ r8c4(5)

Die Kette kann zu einer 4-er Kette über den gemeinsamen Kandidaten in Zelle r8c4 verlängert werden:

r5c1(5) ⇔ r8c1(5) ↔ r8c4(5) ⇔ r4c4(5)

Beachte, dass hier zwischen den ersten beiden Kandidaten und den letzten beiden Kandiaten ein Strong Link besteht, während zwischen den mittleren beiden Kandidaten nur ein Weak Link besteht. Auf diese Weise können beliebig viele Kandidaten-Paare miteinander zu Chains verbunden werden. Links dürfen dabei auch zwischen Kandidaten derselben Zelle bestehen wie dies zum Beispiel bei W-Wings der Fall ist.

Die Logik von Links kann mit Chains über mehrere Kandidaten ausgeweitet werden. Damit eine nützliche Schlussfolgerung über die ganze Chain gezogen werden kann, müssen jedoch folgende Chain-Regeln eingehalten werden:

Betrachten wir das Beispiel:

r5c1(5) ⇔ r8c1(5) ↔ r8c4(5) ⇔ r4c4(5)

Die 4 Chain-Regeln sind erfüllt: Die Anzahl Kettenglieder ist 4, also eine gerade Anzahl. Der erste und letzte Link sind Strong Links. Alle ungeraden Links (1 und 3) sind Strong Links. Alle geraden Links (2) dürfen Weak Links sein, was hier der Fall ist.

Was kann nun bei einer solchen Chain für einen Schlussfolgerung gezogen werden?

Logik von Chains

Begründung

Weil eine Chain immer mit einem Strong Link beginnt, untersucht man zuerst den Fall, dass der erste Kandidat nicht die Lösungs-Zahl seiner Zelle ist. Durch Anwenden der Logik der einzelnen Links kann dann folgende Kette von Schlussfolgerungen gezogen werden:

r5c1(-5) ⇒ r8c1(+5) → r8c4(-5) ⇒ r4c4(+5)

In Worten: Wenn die erste 5 der Chain nicht die Lösungs-Zahl der Zelle ist, muss wegen dem Strong Link die 5 die Lösungs-Zahl der zweiten Zelle sein. Wenn in der zweiten Zelle die 5 die Lösungs-Zahl ist, kann in der dritten Zelle die 5 als Lösungs-Zahl ausgeschlossen werden, egal welche Art von Link zwischen diesen Zellen besteht. Wenn in der dritten Zelle also die 5 nicht die Lösungs-Zahl sein kann, muss wegen dem Strong Link in der letzten Zelle die 5 die Lösungs-Zahl sein. Diese Folgerungen können auf beliebig lange Ketten angewandt werden, solange die Chain-Regeln eingehalten werden.

Zusammenfassung: Wenn der erste Kandidat der Chain nicht die Lösungs-Zahl seiner Zelle ist, muss der letzte Kandidat der Chain die Lösungs-Zahl seiner Zelle sein.

Was passiert, wenn wir mit der Annahme starten, dass der erste Kandidat der Chain die Lösungs-Zahl seiner Zelle ist?

r5c1(+5) ⇒ r8c1(-5) → r8c4(?5) ⇒ r4c4(?5)

Wegen dem Strong Link zur zweiten Zelle kann in diesem Fall die 5 als Lösungs-Zahl der zweiten Zelle ausgeschlossen werden. Wenn in der zweiten Zelle die 5 nicht die Lösungs-Zahl sein kann, könnte die 5 in der dritten Zelle die Lösungs-Zahl sein oder nicht! Weil es sich beim Link zwischen der zweiten und dritten Zelle um einen Weak Link handelt, kann die 5 entweder die Lösungs-Zahl der dritten Zelle r8c4 oder einer anderen Zelle dieses Hauses (r8c2) sein. Ab der dritten Zelle kann also keine weitere Schlussfolgerung gemacht werden, wenn mit der Annahme begonnen wird, dass in der ersten Zelle die 5 die Lösungs-Zahl ist.

Damit wir mit der Logik weiter kommen, muss die Eigenschaft der Chain verwendet werden, dass diese symmetrisch ist und eine gerade Anzahl von Kettengliedern hat. Dadurch können wir die Schlussfolgerungen auch vom Ende der Kette zum Anfang machen. Weil der letzte Link ein Strong Link ist, beginnt man wieder mit der Annahme, dass die 5 in der letzten Zelle nicht die Lösungs-Zahl ist:

r5c1(+5) ⇐ r8c1(-5) ← r8c4(+5) ⇐ r4c4(-5)

Die Logik ist dieselbe wie bei der Reihenfolge von der ersten zur letzten Zelle. Wenn die 5 in der letzten Zelle nicht die Lösungs-Zahl ist, muss sie in der ersten Zelle die Lösungs-Zahl sein.

Kombinieren wir diese beiden Logik-Ketten so erhalten wir folgende Aussagen:

• Wenn in der ersten Zelle die 5 nicht gesetzt ist, muss sie in der letzten Zelle gesetzt sein.
• Wenn in der ersten Zelle die 5 gesetzt wird, kann sie in der letzten Zelle gesetzt sein oder nicht.
• Wenn in der letzten Zelle die 5 nicht gesetzt ist, muss sie in der ersten Zelle gesetzt sein.
• Wenn in der letzten Zelle die 5 gesetzt wird, kann sie in der ersten Zelle gesetzt sein oder nicht.

Daraus kann gefolgert werden, dass in jedem Falle die 5 entweder in der ersten oder in der letzten Zelle oder in beiden gleichzeitig die Lösungs-Zahl sein muss:

Diese Tabelle führt zur folgenden Logik von Chains:

Diese Tatsache bewirkt in unserem Beispiel, dass aus allen Zellen, die einen Kandidaten 5 enthalten und sowohl die erste Zelle als auch die letzte Zelle sehen (sie sind im selben Haus), der Kandidat 5 gelöscht werden kann (rote Zellen im Bild oben).

Dies ist die Folgerung bei der einfachsten Art von Chains. Dieselbe Logik kann auf verschiedene Chain-Arten angewandt werden. Die Schlussfolgerungen sind jedoch bei jeder Chain-Art etwas anders.

Chain-Arten

Wenn eine Chain nur aus lauter Kandidaten einer bestimmten Zahl besteht, spricht man von einer X-Chain. Besteht die Chain aus lauter Zellen mit je genau zwei Kandidaten, spricht man von einer XY-Chain. Bei einer XY-Chain sind immer Strong Links zwischen den Kandidaten innerhalb jeder Zelle und Weak Links zwischen den Zellen.

Chains können auf verschiedene Art zu Loops (Schleifen) geschlossen werden. Wenn sich die erste und letzte Zelle einer Chain sehen, dann ist die Chain über einen Weak Link geschlossen und man spricht von einer X-Chain Nice Loop oder einer XY-Chain Loop.

Bei einer entarteten X-Chain darf die letzte und die erste Zelle dieselbe Zelle sein. Bei dieser Art von Loop führen zu der gemeinsamen Zelle zwei Strong Links. Das bedeutet, dass in dieser Zelle der Kandidat sicher gesetzt sein muss. Eine solche Chain nennt man X-Chain Discontinuous Loop (discontinuous = nicht kontinuierlich), weil die Regel gebrochen wird, dass die Link-Art abwechseln muss.

X-Chains mit nur 4 Zellen oder XY-Chains mit nur 3 Zellen (6 Kandidaten) werden auch als eigenständige Methoden unter eigenen Namen aufgeführt. Die Sudoku-App verwendet für diese speziellen Methoden intern zum Teil dieselben Algorithmen wie für die Chains.

Es ist auch möglich Chains zu bilden, welche nicht nur einen Kandidaten und nicht nur Kandidaten-Paare einer Zelle verwenden. Es müssen aber in jedem Fall die Regeln von Chains eingehalten werden. Diese Chains können sehr kompliziert und lange sein. Sie sind sehr schwer zu finden. Die Sudoku-App hat diese Art von Chain nicht implementiert.