Chains (Ketten) und Loops (Schleifen)

Inhaltsverzeichnis

Einf�hrung

Was ist eine Kette?

Chains (Ketten) sind die grundlegendsten und gleichzeitig auch die komplexesten Strategien f�r Sudokus. Vermutlich kann jedes Sudoku nur mit Ketten der verschiedensten Schwierigkeitsgrade und mit Singles gel�st werden. Da Chaining (die Verwendung von Ketten) derma�en vielseitig und effizient ist, haben auch sehr viele Personen zur Entwicklung von Methoden, Notationen und Ausdr�cken beigetragen. Das hat auf der einen Seite viele sehr fortgeschrittene Strategien hervorgebracht, hat aber auch zu gro�er Verwirrung gef�hrt. Au�erdem gab und gibt es viele heftige Diskussionen dar�ber, welche Varianten von Chaining besser sind als andere und warum. F�r Anf�nger kann die gro�e (un�berschaubare?) Menge an verschiedenen Strategien ein bisschen �berw�ltigend wirken. Es zahlt sich aber trotzdem aus, einen Versuch zu wagen. Eine gute Vorgehensweise ist, mit einfachen Varianten, wie Remote Pairs, X-Chains, oder XY-Chains, zu beginnen und sich von dort aus weiter zu arbeiten.

Eine Chain ist nichts anderes als eine Kette von Schlussfolgerungen, die von einer Annahme (z.B.: Kandidat x in Zelle y ist nicht gesetzt) zu einem Ergebnis f�hrt. Wenn eine Chain zu einem Widerspruch f�hrt (z.B.: Annahme "x gesetzt in y" f�hrt zum Ergebnis "x nicht gesetzt in y"), wurde damit bewiesen, dass die Annahme falsch war. Wenn die Annahme in einem solchen Fall war: "wenn Kandidat x gesetzt ist", kann x eliminiert werden. Wenn die Annahme war: "wenn Kandidat x nicht gesetzt ist", kann x sofort platziert werden.

Wenn eine Chain allerdings zu keinem Widerspruch f�hrt, beweist sie gar nichts. Man muss dann mehrere solche Chains kombinieren um ein Resultat zu erhalten. So k�nnen zum Beispiel zwei Chains mit entgegengesetzten Annahmen ("x ist in y gesetzt" und "x ist in y nicht gesetzt") zum selben Ergebnis f�hren: Dieses Ergebnis muss dann war sein (das wird oft als Verity - Wahrheit - bezeichnet). Eine andere M�glichkeit w�re, dass Chains, die mit derselben Annahme starten, alle Kandidaten aus einer Zelle eliminieren (oder alle Vorkommen eines Kandidaten aus einem Haus). Das ergibt einen Widerspruch, der wieder beweist, dass die Annahme falsch ist.

Eine dritte Gruppe von Chains ben�tzt die Tatsache, dass viele (aber nicht alle!) Chains umkehrbar sind: Wenn "x nicht gesetzt in y" zu "x ist gesetzt in z" f�hrt, dann f�hrt "x nicht gesetzt in z" mit Hilfe derselben Logik (nur umgekehrt) zu "x gesetzt in y". Das eliminiert x aus allen Zellen, die beide Enden der Chain sehen k�nnen.

Links (Bindungen) und Inferences (Folgerungen)

Die Basis f�r alle Chains sind zwei Typen von grundlegenden Folgerungen, die normalerweise "Links" (Bindungen) oder "Inferences" (Folgerungen) genannt werden (in diesem F�hrer wird der Begriff "Link" synonym f�r beides verwendet).

Weak Links (Schwache Bindungen)

Wenn zwei Objekte schwach gebunden sind, k�nnen sie nicht zur selben Zeit wahr sein. Das hei�t: Wenn eines von beiden wahr ist, muss das andere falsch sein (sie k�nnen aber auch beide falsch sein; aus der Tatsache, dass eines der Objekte falsch ist, folgt daher gar nichts). In einfachen Chains sind die Objekte normalerweise Kandidaten, die im selben Haus oder in der selben Zelle sind.

Strong Links (Starke Bindungen)

Wenn zwei Objekte stark gebunden sind, k�nnen sie nicht zur selben Zeit falsch sein. Das hei�t: Wenn eines falsch ist, muss das andere wahr sein (beide wahr gibt es nur in sehr fortgeschrittenen Link-Typen). Wenn man Kandidaten verwendet, ben�tigt man f�r einen Strong Link genau zwei Kandidaten in einer Zelle oder genau zwei Vorkommen eines Kandidaten in einem Haus (ein Conjugate Pair im Coloring-Jargon).

Diese beiden Link-Typen sind die Basis f�r alle Chains, der Unterschied zwischen beiden muss daher wirklich gut verstanden werden. Noch einmal auf den Punkt gebracht:

Um eine Chain bilden zu k�nnen, m�ssen sich die Link-Typen abwechseln (daher der Name "Alternating Inference Chain" oder AIC - frei �bersetzt: Kette mit wechselnden Link-Typen). Jede Chain ist im Grunde eine AIC. Eine Chain kann daher folgenderma�en gelesen werden: "Wenn a falsch ist, muss b wahr sein, daher muss c falsch sein, d muss wahr sein, usw.". Um die Dinge noch ein bisschen komplizierter zu machen, kann man noch Folgendes ber�cksichtigen: Wenn zwei Kandidaten mit einem Strong Link verbunden sind, sind sie immer auch mit einem Weak Link verbunden. Das bedeutet, dass man �berall dort, wo man in einer Chain einen Weak Link ben�tigt, auch einen Strong Link nehmen kann (umgekehrt geht das definitiv nicht).

Das oben Gesagte gen�gt um einfache Chains verstehen zu k�nnen und es w�re vermutlich gut jetzt gleich mit ein paar konkreten Beispielen zu starten (z.B. mit Remote Pairs). Um alle Strategien in diesem Kapitel wirklich verstehen zu k�nnen, sind die folgenden Abs�tze auch wichtig. Es ist aber vielleicht besser sie erst dann anzugehen, wenn man einfache Chains wirklich verstanden hat.

Group Links (Gruppen-Bindungen)

Group Links formen Bindungen zwischen mehr als zwei Kandidaten. Normalerweise ben�tzt man nur zwei Kandidaten um einen Link zu bilden: Wenn es die letzten beiden Kandidaten im Haus oder in der Zelle sind, ist es ein Strong Link, wenn es noch andere Kandidaten gibt, ist es ein Weak Link. Wenn wir allerdings �berschneidungen zwischen H�usern ber�cksichtigen, k�nnen wir etwas fortgeschrittenere Link-Typen bilden. Betrachten wir das untere Beispiel (aus dem Kapitel �ber Locked Candidates):

Sudoku L�sungstechnik: Beispiel f�r Group+nodes

Konzentrieren wir uns auf Kandidat 5 in Zeile 3 (die Farben ignorieren wir, die stammen vom Locked Candidates-Zug). Kandidat 5 gibt es in Zeile 3 noch drei Mal (Spalten 1, 2 und 7). Jede Kombination aus zwei dieser Kandidaten ist mit einem Weak Link verbunden, ein Strong Link in Zeile 3 ist nicht m�glich (zu viele Kandidaten). Ein Strong Link existiert zwar in Block 1 zwischen r3c1 und r3c2 (die letzten beiden 5er in Block 1), nicht aber zwischen einem der Kandidaten in r3c12 und r3c7. Das �ndert sich, wenn wir r3c12 als einen einzigen Knoten betrachten, einen Group Node. Wenn wir das tun, k�nnen wir folgende Schl�sse ziehen:

Wie jeder Strong Link enth�lt auch dieser auch einen Weak Link:

Links k�nnen auch zwischen zwei Group Nodes bestehen, wie im unteren Beispiel zu sehen ist:

Sudoku L�sungstechnik: Beispiel f�r Group+nodes

Wir betrachten Kandidat 2 in Zeile 9, Spalte 4 und Block 8 (die Zellen wurden gef�rbt um der Erkl�rung leichter folgen zu k�nnen): Wir haben einen Grouped Strong Link in Zeile 9 zwischen r9c9 und r9c56 und einen weiteren in Spalte 4 zwischen r6c4 und r78c4. Beide Links funktionieren wie oben dargelegt.

Innerhalb von Block 8 existiert aber auch ein Weak Link zwischen dem Group Node r9c56 und dem Group Node r78c4 (Weak Link, weil es noch andere 2er in Block 8 gibt):

Die drei Links lassen sich zu einer Chain kombinieren (die Chain bewirkt alleine noch nichts, kann aber Teil einer l�ngeren Chain werden, siehe Grouped Nice Loops):

r6c4 =2= r78c4 -2- r9c56 =2= r9c9

ALS in Chains

ALS steht f�r "Almost Locked Set" (Fast Gesperrte Menge) und wird detailliert im Kapitel �ber ALS behandelt. F�r jetzt gen�gt es zu wissen, dass ein ALS eine Gruppe von Zellen innerhalb eines Hauses ist, die N+1 Kandidaten in N Zellen aufweist. Ein ALS f�r sich selbst genommen beweist gar nichts, aber man kann trotzdem sehr interessante Dinge mit ihm anstellen. Wird ein Kandidat aus einem ALS entfernt, wird das ALS ein Locked Set (besser bekannt als Naked Subset). Das allerdings ist genau die Definition eines Strong Links. Nehmen wir z.B. ein imagin�res ALS mit Kandidaten {1234} in drei Zellen:

Ein ALS wird �ber einen Weak Link erreicht (ein Kandidat muss aus dem ALS entfernt werden) und auch wieder �ber einen Weak Link verlassen (das resultierende Locked Set eliminiert irgendeinen Kandidaten au�erhalb des ALS). Der n�tige Strong Link zwischen den beiden Weak Links ist die Tatsache, dass das ALS, wie oben beschrieben, ein Locked Set wird.

Chains versus Nets

Was eine Chain und was ein Net ist, dar�ber wurden zwischen Sudoku Spielern schon jede Menge hei�er Diskussionen gef�hrt. HoDoKu verwendet die folgende Definition: In einer Chain folgt jeder Schritt ausschlie�lich aus dem Schritt unmittelbar vor ihm. Wenn ein Schritt nur dann funktioniert, wenn man die Folgen eines Schrittes weiter vorne in der Kette mit einbezieht, wird aus der Chain ein Net. Das gleiche gilt, wenn sich die Chain in Zweige aufteilt, die sich sp�ter wieder treffen.

Notation

Um Chains aufschreiben zu k�nnen wurden zahlreiche Notationen entwickelt. Drei Schreibweisen sind derzeit noch in Gebrauch:

Forcing Chain-Notation

Forcing Chain-Notation verwendet Ausdr�cke der Form [cell]=[value] (oder [cell]<>[value]) um der Chain folgen zu k�nnen. Das linke Remote Pairs-Beispiel w�re dann:

r2c7<>4 => r2c7=5 => r2c2<>5 => r2c2=4 => r3c1<>4 => r3c1=5 => r6c1<>5 => r6c1=4

Um die Ausdr�cke kurz zu halten, werden die "<>"-Teile oft weggelassen (au�er am Start und am Ende der Chain):

r2c7<>4 => r2c7=5 => r2c2=4 => r3c1=5 => r6c1=4

Diese K�rze bewirkt leider auch, dass Forcing Chain-Notation manchmal etwas schwer nachzuvollziehen ist.

Nice Loop-Notation

Nice Loop-Notation verwendet "-x-" f�r Weak Links und "=x=" f�r Strong Links. Links werden nur aufgeschrieben, wenn sie sich zwischen Zellen befinden (Links innerhalb von Zellen werden impliziert). Das Remote Pair in Nice Loop-Notation:

r2c7 -5- r2c2 -4- r3c1 -5- r6c1

Um klarzustellen, wie die Chain beginnt und endet (der erste und der letzte Link f�r Ziffer 4 werden komplett unterschlagen), k�nnen Start- und End-Links an die Notation angeh�ngt werden:

4- r2c7 -5- r2c2 -4- r3c1 -5- r6c1 -4

AIC-Notation

In AIC-Notation wird nichts ausgelassen. "-" wird f�r Weak Links verwendet, "=" f�r Strong Links, Kandidaten stehen in runden Klammern vor der betroffenen Zelle. Wenn ein Link innerhalb einer Zelle vorkommt, wird er mit in die Klammern geschrieben. Das Remote Pair:

(4=5)r2c7-(5=4)r2c2-(4=5)r3c1-(5=4)r6c1

Chains in HoDoKu anzeigen

Wenn HoDoKu eine Chain anzeigt, werden die Links zwischen Zellen durch Pfeile symbolisiert (durchgezogene Linien f�r Strong Links, strichlierte f�r Weak Links). Gr�ner Hintergrund bedeutet "Kandidat gesetzt", blauer Hintergrund bedeutet "Kandidat nicht gesetzt". In kannibalistischen Chains (die Chain eliminiert Kandidaten, die Teil der Chain selbst sind), werden die Eliminierungen bevorzugt dargestellt. In komplexen Forcing Chains/Nets kann ein Kandidat zu mehreren Chains geh�ren und daher verschiedene Farben haben. Welche Farbe schlie�lich dargestellt wird, kann nicht vorhergesagt werden.

Remote Pairs (Entfernte Paare)

Remote Pairs ist die einfachste Chaining-Strategie. Ber�cksichtig werden nur zweiwertige Zellen, die alle dieselben Kandidaten enthalten m�ssen. Da alle Zellen zweiwertig sind, enth�lt jede einen Strong Link zwischen den beiden Kandidaten. Die Links zwischen den Zellen k�nnen daher Weak Links sein (zwei benachbarte Zellen m�ssen lediglich im selben Haus sein). Um etwas eliminieren zu k�nnen, muss die Chain mindestens vier Glieder lang sein. Das Remote Pair stellt sicher, dass zwei benachbarte Zellen in der Chain verschiedene Werte haben m�ssen (welche, ist unbekannt). Jede Zelle au�erhalb des Remote Pairs, die zwei Zellen mit verschiedenen Werten sieht, kann keine der Remote Pair-Ziffern enthalten.

Statt eines Remote Pairs k�nnen immer auch ein oder zwei Simple Color-Z�ge ausgef�hrt werden.

Sudoku L�sungstechnik: Beispiel f�r Remote+Pair Sudoku L�sungstechnik: Beispiel f�r Remote+Pair

Linkes Beispiel: Wenn r2c7 5 ist, muss r3c1 auch 5 sein und r2c2 und r6c1 m�ssen 4 sein oder genau umgekehrt. Anders ausgedr�ckt: Wenn r2c7 5 ist, ist r6c1 4; wenn r2c7 4 ist, ist r6c1 5 (die Zellen r2c7 und r6c1 haben entgegengesetzte Polarit�t). Jede Zelle, die diese beiden Zellen sieht (im Beispiel r6c7) kann weder 4 noch 5 sein.

Das rechte Beispiel startet mit r7c8 und endet mit r8c4. Die Chain ist 8 Zellen lang. Alle Zellen, die Remote Pair-Zellen mit entgegengesetzter Polarit�t sehen, k�nnen weder 2 noch 8 sein.

X-Chain (Einerkette)

X-Chains sind Chains, die nur eine Ziffer verwenden. X-Chains der L�nge 4 werden manchmal auch Turbot Fish genannt und k�nnen mit Hilfe einer der spezialisierten Turbot-Varianten (Skyscraper, 2-String Kite, oder Empty Rectangle) leicht gefunden werden.

Wichtig ist bei X-Chains, dass sie mit einem Strong Link starten und enden m�ssen. Das stellt sicher, dass einer der Endpunkte die Ketten-Ziffer enthalten muss. Diese Ziffer kann daher aus allen Zellen gel�scht werden, die beide Enden der X-Chain sehen.

Sudoku L�sungstechnik: Beispiel f�r X-Chain Sudoku L�sungstechnik: Beispiel f�r X-Chain

Linke Seite: Wenn r1c2 nicht 7 ist, muss r1c9 7 sein, r2c8 kann nicht 7 sein, r7c8 muss 7 sein, r7c3 kann nicht 7 sein und r4c3 muss 7 sein. Wenn andererseits r4c3 nicht 7 ist, dann muss r7c3 7 sein, r7c8 kann nicht 7 sein, r2c8 muss 7 sein, r1c9 kann nicht 7 sein und r1c2 muss 7 sein. Wie man es auch betrachtet, eine der Zellen r1c2 oder r4c3 muss 7 sein. r4c2 sieht beide diese Zellen und kann daher nicht auch noch 7 sein.

Rechte Seite: Die X-Chain beweist, dass entweder r4c2 oder r6c5 3 sein muss. 3 kann von r6c123 eliminiert werden.

XY-Chain (Zweierkette)

Eine XY-Chain ist eine Chain, die nur zweiwertige Zellen verwendet (�hnlich wie Remote Pairs), allerdings k�nnen die Zellen beliebige Kandidaten haben. Die einzige Einschr�nkung (au�er der offensichtlichen Notwendigkeit, dass die Links korrekt sein m�ssen) ist, dass die XY-Chain mit einen Strong Link f�r ein und dieselbe Ziffer starten und enden muss. Wie bei X-Chains beweist das, dass diese Ziffer in einem der Endpunkte der Chain platziert werden muss, und dass sie daher aus allen Zellen eliminiert werden kann, die beide Enden der Chain sehen.

Wie bei Remote Pairs sind auch hier alle Strong Links innerhalb der Zellen und alle Weak Links zwischen den Zellen.

Sudoku L�sungstechnik: Beispiel f�r XY-Chain Sudoku L�sungstechnik: Beispiel f�r XY-Chain

Linkes Beispiel: 3- r7c4 -9- r5c4 -8- r5c6 -2- r2c6 -3 (sprich: wenn r7c4 nicht 3 ist muss sie 9 sein; r5c4 kann dann nicht 9 und muss 8 sein; r5c6 kann nicht 8 und muss 2 sein; r2c6 kann nicht 2 und muss 3 sein; die andere Richtung bleibt dem Leser �berlassen). Wenn man Spalte 6 betrachtet, sieht man, dass sie nur noch zwei Kandidaten 2 �brig hat. r5c6 und r2c6 sind daher mit einem Strong Link f�r 2 verbunden. F�r die XY-Chain ben�tigen wir hier aber keinen Strong Link, sondern einen Weak Link. Man kann aber den Strong Link nehmen und ihn, wie oben ausgef�hrt, als Weak Link verwenden

Rechtes Beispiel: 8- r6c5 -4- r8c5 -1- r8c4 -9- r3c4 -8

Nice Loop/AIC (Nette Schleife)

Nice Loop Propagation Rules (Ausbreitungsregeln f�r Nette Schleifen)

Nice Loops sind Chains, deren Ende mit der Startzelle verlinkt ist. Um das Finden dieser Chains einfacher zu gestalten, wurden Ausbreitungsregeln definiert. Wie bei der Nice Loop-Notation (siehe oben), wird auch bei diesen Regeln alles, was sich innerhalb der Zelle abspielt, ignoriert, lediglich Links zwischen Zellen werden ber�cksichtigt:

Betrachten wir Regel Nummer 2: Wenn eine Zellen mit einem Weak Link erreicht und auch wieder verlassen wird, muss der zwischen den Weak Links n�tige Strong Link innerhalb der Zelle sein. Die Zelle muss daher zweiwertig sein und der ausgehende Link muss f�r eine andere Ziffer sein als der eingehende.

Ob man jetzt die Ausbreitungsregeln verwendet oder versucht die Linktypen zu alternieren, bleibt nat�rlich jedem selbst �berlassen. Der folgende Link f�hrt zu einem Nice Loop Tutorial, das die Regeln im Detail und mit jeder Menge Beispielen erkl�rt (leider nur auf Englisch).

Der Link zur�ck zur Ausgangszelle entscheidet �ber den Typ der Nice Loop: Discontinuous (unterbrochen) oder Continuous (ununterbrochen). Wenn der letzte Link einen Widerspruch hervorruft, ist die Schleife unterbrochen. Wenn sich die Schleife aber "nett" schlie�t (man k�nnte ihr wieder und wieder rund herum folgen ohne ein Ende zu entdecken), ist die Schleife ununterbrochen.

Discontinuous Nice Loop (Unterbrochene Nette Schleife)

Schlie�t die Schleife mit einem Widerspruch, so ist sie unterbrochen. Die Auswirkungen kann man am besten anhand der Beispiele erkennen.

Sudoku L�sungstechnik: Beispiel f�r Discontinuous+Nice+Loop+%28delete+candidate%29 Sudoku L�sungstechnik: Beispiel f�r Discontinuous+Nice+Loop+%28set+cell%29

Linkes Beispiel: r1c8 -7- r7c8 -8- r7c9 -4- r4c9 -5- r4c8 =5= r1c8. Die Schleife startet mit einem Weak Link f�r 7 (die Annahme ist: "wenn r1c8 7 ist"), aber die Ausgangszelle wird �ber einen Strong Link f�r 5 wieder erreicht. Das bedeutet: "Wenn Zelle r1c8 7 ist, ist sie 5", oder (da 5 und 7 in der selben Zelle sind und daher mit einem Weak Link verbunden sind) "wenn Zelle r1c8 7 ist, ist sie nicht 7" - eine Widerspruch, der beweist, dass die Annahme falsch war. 7 kann von r1c8 gel�scht werden.

Rechtes Beispiel: r8c2 =4= r8c9 -4- r9c9 -2- r9c3 =2= r7c2 =4= r8c2. Die Schleife startet mit einem Strong Link f�r 4 (Annahme: "wenn r8c2 nicht 4 ist") und endet auch wieder mit einem Strong Link f�r 4. Das hei�t: "Wenn r8c2 nicht 4 ist, ist sie 4" - ein Widerspruch, der beweist, dass r8c2 wirklich 4 sein muss. 4 kann in r8c2 platziert werden (HoDoKu setzt keine Ziffern bei Nice Loops, es eliminiert alle anderen Kandidaten aus der Zelle, was ein Naked Single �brig l��t). Man kann die Schleife auch als Verity betrachten: Die Schleife beweist, dass r8c2 4 sein muss, wenn sie nicht 4 ist. Aber wenn die Zelle 4 ist, ist sie nat�rlich auch 4. Beide M�glichkeiten (r8c2=4 und r8c2<>4) f�hren zum selben Ergebnis: r8c2=4, das daher wahr sein muss.

Alternate Inference Chain Type 1 (Kette mit alternierenden Link Typen Typ 1)

Jede AIC kann als eine Kombination von einer oder mehreren Discontinuous Nice Loops gesehen werden (HoDoKu meldet einen Zug nur dann als AIC, wenn er mehr als einen Kandidaten eliminiert; AICs mit nur einer Eliminierung werden immer als Discontinuous Nice Loop ausgegeben). AICs starten und enden mit einem Strong Link und haben dazwischen abwechselnd Weak und Strong Links ohne weitere Einschr�nkungen.

Eine AIC Typ 1 startet und endet mit einem Strong Link f�r dieselbe Ziffer und beweist somit, dass diese Ziffer in Start- oder End-Zelle platziert werden muss. Das eliminiert diese Ziffer aus allen Zellen, die beide Enden der AIC sehen k�nnen.

Sudoku L�sungstechnik: Beispiel f�r Alternate+Inference+Chain+Type+1 Sudoku L�sungstechnik: Beispiel f�r Alternate+Inference+Chain+Type+1+%28cannibalistic%29

Linkes Beispiel: 5- r1c2 -3- r1c4 =3= r3c4 =9= r7c4 =2= r7c2 -2- r8c3 -5. Entweder r1c2 oder r8c3 muss 5 sein, also k�nnen weder r123c3 noch r78c2 5 sein.

Rechtes Beispiel: 6- r2c5 -7- r2c1 =7= r6c1 =6= r6c7 -6- r2c7 =6= r3c8 -6. Hier f�llt auf, dass einer der eliminierten Kandidaten (6 in r2c7) tats�chlich Teil der Chain selbst ist. Das ist absolut erlaubt. Die AIC ist "kannibalistisch".

Alternate Inference Chain Type 2 (Kette mit alternierenden Link Typen Typ 2)

Eine AIC Typ 2 startet und endet mit einem Strong Link f�r zwei verschiedene Ziffern in zwei Zellen, die einander sehen. Das beweist, dass die Endziffer nicht in der Startzelle und die Startziffer nicht in der Endzelle sein kann.

Sudoku L�sungstechnik: Beispiel f�r Alternate+Inference+Chain+Type+2 Sudoku L�sungstechnik: Beispiel f�r Alternate+Inference+Chain+Type+2

Linkes Beispiel: 4- r6c2 =4= r9c2 -4- r9c5 -9- r5c5 =9= r5c4 =8= r6c4 -8. Wir starten mit 4 in r6c2 und enden mit 8 in r6c4. 4 kann nicht in r6c4 sein und 8 nicht in r6c2. Beweis f�r Kandidat 4: Wenn r6c2<>4 ist, muss r6c4 8 sein, also kann r6c4 nicht 4 sein. Ist aber r6c2 4, kann r6c4 auch nicht 4 sein, weil sich die Zellen sehen. Wir haben eine Verity, die beweist, dass r6c4 nicht 4 sein kann.

Rechtes Beispiel: 8- r1c8 -2- r1c7 =2= r6c7 =6= r6c3 =5= r4c2 =2= r4c8 -2. 2 kann nicht in r1c8 sein und 8 nicht in r4c8.

Continuous Nice Loops (AIC Loops) (Ununterbrochene Nette Schleifen)

Continuous Nice Loops und AIC Loops sind genau dasselbe. Sie sind nicht so h�ufig wie Discontinuous Nice Loops, hat man aber eine gefunden, ist sie normalerweise sehr effizient. Eine Schleife ist ununterbrochen, wenn der Link zur�ck zur Startzelle gemeinsam mit dem ersten Link den Ausbreitungsregeln entspricht, oder anders ausgedr�ckt, wenn in der Start-/Endzelle kein Widerspruch auftritt.

Was Continuous Nice Loops so effizient macht, ist die Tatsache, dass alle Weak Links in der gesamten Schleife zu Strong Links umgewandelt werden. Das hei�t, dass alle zus�tzlichen Kandidaten in den H�usern oder Zellen, die die Weak Links beinhalten, gel�scht werden k�nnen.

Sudoku L�sungstechnik: Beispiel f�r Continuous+Nice+Loop%2FAIC+Loop Sudoku L�sungstechnik: Beispiel f�r Continuous+Nice+Loop%2FAIC+Loop

Linkes Beispiel: 5= r7c6 =2= r6c6 -2- r4c5 -3- r8c5 =3= r8c6 =5= r7c6 =2. Zelle r7c6 wird mit einem Strong Link f�r 2 verlassen und mit einem Strong Link f�r 5 wieder erreicht (erste Ausbreitungsregel). Ein Weak Link existiert zwischen den Kandidaten 2 und 5 in Zelle r7c6, alle Regeln f�r AICs werden eingehalten. Die Eliminierungen: Der erste Weak Link ist innerhalb der Startzelle zwischen 2 und 5, alle anderen Kandidaten in dieser Zelle k�nnen gel�scht werden (6 und 8). Der n�chste Weak Link ist in Block 5 zwischen 2 in r6c6 und 2 in r4c5, alle anderen Kandidaten 2 in Block 5 k�nnen eliminiert werden. Der n�chste Weak Link ist f�r 3 in Spalte 5 (eliminiert 3 von r26c5) und zu guter Letzt gibt es noch einen Weak Link zwischen 3 und 5 in r8c6 (eliminiert 8 in dieser Zelle).

Rechtes Beispiel: 9= r7c5 =1= r7c9 =7= r3c9 -7- r3c3 =7= r1c3 =5= r1c6 -5- r8c6 =5= r8c4 =7= r7c4 =9= r7c5 =1. Weak Links innerhalb von Zellen finden sich in r7c5, r7c9, r1c3, r8c4 und r7c4. Weak Links zwischen Zellen sind in Zeile 3 (nichts zu l�schen) und Spalte 6.

Grouped Nice Loop/AIC (Nette Schleifen mit Gruppen-Bindungen)

Nur Group Nodes

Der einzige Unterschied zwischen (normalen) Nice Loops/AICs und Grouped Nice Loops/Grouped AICs ist, dass die zweiteren Group Links verwenden.

Sudoku L�sungstechnik: Beispiel f�r Grouped+Discontinuous+Nice+Loop+%28set+cell%29 Sudoku L�sungstechnik: Beispiel f�r Grouped+Continuous+Nice+Loop%2FAIC+Loop

Linkes Beispiel: Grouped Discontinuous Nice Loop r7c1 =2= r2c1 -2- r2c5 =2= r1c5 =8= r13c4 -8- r5c4 -3- r5c3 -2- r79c3 =2= r7c1. Die beiden Group Links sind f�r Kandidat 8 in Zellen r13c4 und f�r Kandidat 2 in r79c3. Die Logik f�r den ersten Group Link geht wie folgt: Wenn r1c5 nicht 8 ist, muss entweder r1c4 oder r3c4 8 sein; das hei�t, dass r5c3 nicht 8 sein kann. Zweiter Group Link: Wenn r5c3 2 ist, k�nnen weder r7c3 noch r9c3 2 sein; das hei�t, dass r7c1 2 sein muss.

Rechtes Beispiel: Grouped Continuous Nice Loop 2= r6c4 =1= r6c3 -1- r9c3 =1= r9c9 =2= r9c56 -2- r78c4 =2= r6c4 =1. Beide Group Links sind f�r Kandidaten 2: �berschneidung von Zeile 9 mit Block 8 (r9c56) und �berschneidung von Spalte 4 mit Block 8 (r78c4). Die Logik: Wenn r9c9 nicht 2 ist, muss entweder r9c5 oder r9c6 2 sein; das hei�t, dass weder r8c4 noch r7c4 2 sein k�nnen und es folgt daher, dass r6c4 2 sein muss. Der Weak Link zwischen den Group Nodes r9c56 und r78c4 befindet sich innerhalb von Block 8 und eliminiert alle anderen 2en aus diesem Block. Sudoku L�sungstechnik: Beispiel f�r Grouped+Alternate+Inference+Chain+Type+1 Sudoku L�sungstechnik: Beispiel f�r Grouped+Alternate+Inference+Chain+Type+2

Linkes Beispiel: Grouped AIC 5- r7c2 -6- r6c2 -3- r6c4 -7- r45c5 =7= r3c5 =6= r3c6 -6- r9c6 -5 (Group Link f�r 7 in r45c5 - gleiche Logik wie oben).

Rechtes Beispiel: Grouped AIC 4- r2c5 =4= r9c5 -4- r9c9 -1- r89c8 =1= r2c8 -1- r2c456 =1= r1c4 -1. Das Beispiel hat zwei Group Links. Einer davon (r2c456) hat drei Zellen (das Maximum f�r einen Group Node). Eine dieser Zellen ist zuf�lligerweise auch die Startzelle. Das schlie�t die Chain nicht zu einer Schleife: Ein Group Node ist nicht dasselbe wie eine einfacher Knoten (eine Zelle). Es f�hrt jedoch dazu, dass eine der Zellen des Group Nodes eliminiert wird, was die Chain kannibalistisch macht.

Group Nodes und ALS

Wenn wir ALS-Knoten in Chains und Loops zulassen, wird es erst so richtig interessant (und es ist damit noch lange nicht aus: AURs, Almost Fish usw. k�nnen ebenfalls Knoten sein). Um die unten gezeigten Chains in HoDoKu sehen zu k�nnen, muss die entsprechende Option aktiviert werden (ab Release 1.2 sind ALS-Knoten defaultm��ig ausgeschaltet).

Besonders interessant sind ALS-Knoten in Grouped Continuous Nice Loops: Wenn wir alle ALS-Kandidaten hernehmen und davon die Kandidaten, die zum Erreichen und Verlassen des ALS verwendet worden sind, abziehen (sie sind normale Weak Links, die wie �blich in Continuous Loops zu Strong Links werden), sind die verbleibenden Kandidaten auf die ALS-Zellen beschr�nkt und bewirken Eliminierungen in allen Zellen, die alle Vorkommen einer der eingesperrten Ziffern innerhalb des ALS sehen k�nnen. Bitte beachten Sie, dass das nur f�r Continuous Nice Loops gilt.

Sudoku L�sungstechnik: Beispiel f�r Grouped+Discontinuous+Nice+Loop+with+ALS+node Sudoku L�sungstechnik: Beispiel f�r Grouped+Continuous+Nice+Loop%2FAIC+Loop+with+ALS+node

Linkes Beispiel: Grouped Discontinuous Nice Loop r8c2 -5- r7c12 =5= r7c5 =2= r8c5 -2- ALS:r8c34 -5- r8c2. Wir fangen einfach an: Wenn 5 in r8c2 gesetzt ist (Annahme), k�nnen weder r7c1 noch r7c2 5 sein, r7c5 muss 5 sein und kann daher nicht 2 sein, r8c5 muss 2 sein und r8c3 kann nicht 2 sein. r8c3 war aber der einzige 2er im ALS r8c34 {256}. Das reduziert das ALS auf ein Locked Set f�r Kandidaten {56} in r8c34. M�gliche Eliminierungen f�r dieses Locked Set sind 5 in r8c2 und r8c5 und 6 in r8c6. Wir interessieren uns nur f�r r8c2, weil das unsere Startzelle war. Der Weak Link widerspricht der Annahme, 5 kann aus r8c2 gel�scht werden.

Rechtes Beispiel: Das Puzzle ist dasselbe wie f�r das Grouped Continuous Nice Loop-Beispiel von oben. Wenn wir ALS-Knoten zulassen, k�nnen wir noch ein paar Eliminierungen herausholen (nicht dass das n�tig w�re: beide Schleifen l�sen das Sudoku).

Die Schleife: Grouped Continuous Nice Loop 2= r9c9 =3= r9c6 -3- ALS:r6c56 -2- r6c4 =2= r78c4 -2- r9c56 =2= r9c9 =3. Der Weak Link in Zelle r9c9 eliminiert Kandidat 1, der Weak Link in das ALS (Kandidat 3) eliminiert alle anderen 3er aus Spalte 6. Das ALS wird �ber Kandidat 2 wieder verlassen, was alle anderen 2er aus Zeile 6 l�schen w�rde, wenn es denn welche g�be. Aber das ALS hat immer noch einen Kandidaten �brig: Kandidat 8. Er wird im ALS auf die Zellen r6c56 beschr�nkt und eliminiert 8 aus allen Zellen, die diese beiden Zellen sehen k�nnen (8 Eliminierungen im Ganzen). Die Eliminierungen f�r 2 sehen ebenfalls je eine ALS-Zelle, aber sie k�nnen nicht vom ALS eliminiert werden: Erstens m�sste jede Zelle alle 2er im ALS sehen k�nnen und zweitens ist Kandidat 2 nicht auf das ALS beschr�nkt, es ist der Ausgangskandidat. Die 2er werden vom Weak Link zwischen Group Node r78c4 und Group Node r9c56 (beide in Block 8) gel�scht.

Sudoku L�sungstechnik: Beispiel f�r Grouped+Alternate+Inference+Chain+Type+1+with+ALS+node Sudoku L�sungstechnik: Beispiel f�r Grouped+Alternate+Inference+Chain+Type+1+with+ALS+node

Zum Abschluss noch zwei AICs mit ALS-Knoten:

Linkes Beispiel: Grouped AIC 4- r8c6 -3- ALS:r78c7,r8c89,r9c8 -6- r9c4 -9- r6c4 -4. Nichts Neues hier, nur ist das ALS ziemlich gro�: 6 Kandidaten ({123469}) in 5 Zellen (r78c7,r8c89,r9c8).

Rechtes Beispiel: Grouped AIC 6- r7c1 -8- ALS:r29c3 =6= r5c3 -6. Diese Chain ist interessant, weil sie zeigt, wie ein Knoten durch ein ALS forciert werden kann. Das ALS ist r29c3 {189}. Es wird �ber Kandidat 8 in r9c3 erreicht, was das Locked Pair {19} �brig l��t. Der n�chste Knoten r5c3 hat Kandidaten {169}: 1 und 9 werden vom Locked Set eliminiert, das l��t 6 als einzigen Kandidaten in dieser Zelle, der dadurch forciert wird (er muss gesetzt werden).

HoDoKu unterst�tzt derzeit keine Links mit mehr als einem Kandidaten, die Chain wird daher wie oben gezeigt geschrieben. Eine bessere Notation w�re: 6- r7c1 -8- ALS:r29c3 -19- r5c3 -6 (das ALS muss �ber einen Weak Link erreicht und verlassen werden).

Copyright © 2008-12 by Bernhard Hobiger
Alles Material auf dieser Site unterliegt der GNU FDLv1.3.