Eine große Zahl der hier bekannten Standard-Sudokus (bisher über 120000 von etwa 1500000 Sudokus - 50000 weitere haben genau 17 Ausgangszahlen und sind damit nicht reduzierbar) wurden mittels Reduzierung analysiert - d.h. es wurden bei jedem Sudoku alle daraus abgeleiteten Sudokus untersucht, denen eine der Ausgangszahlen weggenommen wurde; ist mindestens eines dieser reduzierten Sudokus lösbar, wurde das gleiche Verfahren auf eines dieser Sudokus angewandt, wodurch die Anzahl der notwendigen Ausgangszahlen immer mehr verkleinert wurde, bis kein lösbares Sudoku mehr erzeugt werden konnte (wobei natürlich extrem viele verschiedene Wege durchlaufen werden können). Etwa 12.5 % der hier untersuchten Sudokus konnten nicht reduziert (also verkleinert) werden. Einzelheiten siehe auch unter "Notwendige Ausgangszahlen i.A. nur von 17 bis 31, extrem selten bis 40".
Dieses Programm benutzt 6 Lösungsmethoden(-gruppen) mit verschiedener Punkte-Gewichtung, und ebenfalls 6 Gruppen von Analysemethoden(-gruppen) für die Ausdünnung (ebenfalls mit unterschiedlichen Punkten gewichtet). Die Lösungsmethoden zum Auffinden einer einsetzbaren Zahl und die Ausdünn-Methoden zum Auffinden eines streichbaren Kandidaten können nicht-synchron oder synchron gerechnet werden. Bei der nicht-synchronen Rechnung wird nach dem ersten gefundenen Auffinden einer Zahl bzw. eines Kandidaten das Ergebnis (mit der geringsten Punktzahl bzw. der maximalen Zahl von Streichungen) ausgegeben, d.h. es hängt stark von der vorgegebenen Reihenfolge der Programmschritte ab, wobei natürlich versucht wurde, eine Reihenfolge zu finden, die der Vorgehensweise eines Menschen angepasst ist. Bei der synchronen Rechnung werden (im Allgemeinen bis zu mit einer Option ausgewählten Komplexität der Methoden) alle gleichzeitig gefundenen Ergebnisse dargestellt (ohne dass diese dabei schon Einfluss auf das Vorgehen haben), was den Vorteil hat, dass man alle Möglichkeiten auf einmal sieht (zur Überprüfung, ob man alle Fälle selbst auch gesehen hat) und auch erkennt, wie viele es davon gibt; allerdings liegt die Punkte-Bewertung im synchronen Fall oft um einiges höher als im nicht-synchronen Fall, weil viele der gefundenen Lösungsschritte bzw. Ausdünnschritte eventuell gar nicht zur Bestimmung des Sudokus notwendig sind. Die Punkte-Bewertung ist also abhängig von der gewählten Lösungs-Strategie (siehe Dokumentation). Wurden im nicht-synchronen Fall eine oder mehrere Zahlen eingesetzt bzw. ein oder mehrere Kandidaten gestrichen bzw. wurden im synchronen Fall alle gefundenen Zahlen eingesetzt bzw. alle gefundenen Kandidaten gestrichen, beginnt die weitere Abarbeitung wieder mit der einfachsten Methode. Für die allgemeine Bewertung eines Sudokus sollte daher i.A. die halb-synchrone Version (z.B. Option 2000) oder besser die pseudo-synchrone Version (z.B. Option 2001) benutzt werden.
Bei der Lösung und der Bewertung wird davon ausgegangen, dass zuerst versucht wird, das Sudoku ohne Anschreiben der Kandidaten (Reste) zu lösen, da beim Arbeiten mit Hand dies zuerst einmal der natürliche Weg ist - im Gegensatz zu den sonst üblichen, im Internet zu findenden Sudoku-Solvern (z.B. HoDoKu, SudokuExplainer, Sudoku Solver by Andrew Stuart), die sofort alle möglichen Kandidaten für alle Zellen aufschreiben! Es kommen also zuerst nur die direkten Methoden A, B, C und D (C und D optional) zum Einsatz. Erst dann, wenn man damit nicht weiter kommt, werden für jede Zelle alle Zahlen aufgeschrieben, die dafür in Frage kommen: die Kandidaten, die hier als Ganzes oft Rest genannt und auch der Einfachheit halber als eine mehrstellige Zahl (ohne Komma oder andere Trennzeichen) geschrieben werden - und das ist per Hand einiges an Arbeit (dafür gibt es auch Extra-Punkte). Danach versucht man, diese Reste (Kandidatenlisten) so lange auszudünnen, also zu verkürzen, bis man zu einer eindeutigen Lösung für eine Zelle kommt (Lösungsmethoden E und F). Dieses Ausdünnen (Kandidaten-Reduzierung) wird hier mit den wichtigsten 6 Methoden versucht, die weiter unten erklärt werden.
Und gibt es Standard-Sudokus, die sogar mit der (recht umständlich zu benutzenden) Super-Software von Andrew Stuart "SudokuWiki" nicht gelöst werden können ("Run out of known strategies", trotz 38 eingebauter Lösungsverfahren), z.B. das folgende:
Mit diesem Programm nur mit Trial&Error lösbar: 000000002008000700030009040000901000040030010005604000069100030007000500200000008.
Bei diesem Standard-Sudoku werden aber mit der Java-Software "Sudoku Explainer" bei 22 Ausgangszahlen 126 Ausdünnschritte - darunter 54 Mal unterschiedliche Forcing Chains (Cell Forcing Chains, Contradiction Forcing Chains, Double Forcing Chains, Nishio Forcing Chains und Region Forcing Chains) - benötigt.
Ähnlich schwierig und auch bei SudokuWiki nicht lösbar, bei "Sudoku Explainer" werden bei 23 Ausgangszahlen 129 Ausdünnschritte - darunter 55 Mal unterschiedliche Forcing Chains - benötigt: Das ist das bekannte "AI Escargot" des finnischen Mathematikers Arto Inkala: 100007090030020008009600500005300900010080002600004000300000010040000007007000300, auch hier nur mit Trial&Error bis Tiefe 8 lösbar.
Normalerweise gibt es in einem Sudoku in einem bestimmten Zustand mehrere Möglichkeiten, Zahlen zu finden bzw. Kandidaten auszudünnen. Aber es kommt auch vor, dass es nur wenige (1 bis 3) Möglichkeiten gibt, was bei der pseudo-synchronen Version (z.B. Option 2001) zu einigen Zusatzpunkten führt. Beispiele für sehr schwierige Sudokus findet man am Ende dieser Seite unter Sehr schwierige Sudokus.
Neben der Angabe der Summe aller erreichten Punkte gibt es auch die sehr aussagekräftige 2-Norm oder Euklidische Norm, d.h. die Wurzel aus der Quadratsumme aller Punkte, bei der die höheren Punktwerte stärker zur Geltung kommen - das ist nicht so extrem wie die auch angeführte Maximum- oder Tschebyscheff-Norm, also das Maximum der Punktwerte, wie sie z.B. bei SudokuExplainer benutzt wird. Ein Sudoku mit z.B. einem komplizierten Schritt mit 9 Punkten ist bestimmt schwieriger als ein Sudoku mit 3 einfachen Schritte mit jeweils 3 Punkten, obwohl in beiden Fällen die Gesamtpunktzahl 9 ist - aber die Euklidische Norm ist 3 bzw. 5.2. Umgekehrt ist ein Sudoku mit z.B. 5 komplizierten Schritten mit jeweils 16 Punkten auch bestimmt schwieriger als ein Sudoku mit nur einem komplizierten Schritt mit 16 Punkten - hier ist die Euklidische Norm 35.8 bzw. 16 (PS: Nicht-ganze Zahlen werden hier - entsprechend der englisch-amerikanischen Schreibweise - mit Punkt geschrieben).
Bemerkungen zum Paar-Begriff: Die Sudoku-Literatur ist da nicht ganz einheitlich. In diesem Programm wird als Paar eine Zelle mit zwei Kandidaten bezeichnet (eine Goldene Kette besteht z.B. aus der Verkettung von Paaren), eine Zelle mit drei Kandidaten wäre dann ein Trio usw.. Betrachtet man aber die Einheit von zwei verschiedenen Zellen, wird das hier als Doppel (2-Tupel) bezeichnet, bei drei Zellen ist das ein Tripel (3-Tupel) usw., auch wenn der Inhalt der Zellen ein Paar, Trio o.a. ist (es kann also ein Tripel sowohl aus Zellen mit Paaren als auch Trios bestehen).
- PS: Nach 10 Jahren kann man wahrscheinlich ruhigen Gewissens die Beschäftigung mit der Sudoku-Software als im Wesentlichen beendet betrachten. Laut Internet Archive wurde dieses Programm zwischen 24. September 2005 und 19. April 2012 (der Rechner www-aix.gsi.de wurde Ende 2012 stillgelegt) in verschiedenen Stadien 78 Mal gespeichert. Wen es interessiert: Hier ist dieses erste Programm zum Vergleich. Das aktuelle Programm ist etwa 110 Mal so groß und hat etwa 55 Mal so viele Zeilen wie das erste Programm :-) (Juni 2015).
- Optimierung bzw. Neu-Programmierung mehrerer Verfahren (u.a. Einzelzahl-Gitter, Ausschluss-Ketten) und Herabsetzung des Maximums für zu untersuchende Ketten; die Laufzeit des Programms wurde dadurch oft (insbesondere bei komplexeren Sudokus) um den Faktor 2 bis 3 besser. Gleichzeitig können nun auch (die selten auftretenden) 6er-Quasi-Ausschluss-Schleifen mehr als 1 Zusatzzahl haben, aber weiterhin ohne Vermeidbaren 6er-Ausschluss-Schleifen (April/Mai 2015).
- Einbau der XYZ-Wing-Methode als Erweiterung der 3er-Goldenen Kette, die sehr oft gefunden werden kann. Einbau (neben 2*2-Einzelzahl-Gittern) von 3*3- und 4*4-Einzelzahl-Gittern, allgemein Swordfish und Jellyfish genannt. Diese Verallgemeinerung des Urtyps X-Wing (2*2-Einzelzahl-Gitter) ermöglicht es, gleich mehrere Kandidaten (13 wurden häufig beobachtet) streichen zu können, was sie so interessant macht - sie werden nun alle vor den Einzelzahl-Ketten bestimmt; sie sind aber leider nicht sehr häufig anzutreffen. (Februar/März 2015).
- Einbau von Einfachen und Erweiterten bzw. Setzenden Widerspruchs-Ketten (Discontinuous Nice Loops/Alternating Inference Chains). Dadurch können etwa 61 % der bisher nicht lösbaren Sudokus gelöst werden (von den hier vorhandenen 319000 nicht-trivialen Standard-Sudokus können nun 83 % gelöst werden). Die Suche erfolgt erst, wenn keine anderen Lösungsschritte gefunden wurden (Januar/Februar 2015).
- Die Webseite zum Drucken von jeweils 4 neu zufällig ausgewählten Sudokus eines angebbaren Schwierigkeitsgrades wurde für alle drei Sudoku-Arten (Standard-Sudoku, Diagonal-Sudoku, Farb-Sudoku) verbessert bzw. neu eingeführt. Dabei kann man den Typ der Sudokus (entsprechend der Typen bei der Optionsangabe) und die minimale und maximale Punktzahl (beim nicht-synchronen Verfahren berechnet) angeben (Dez. 2014).
- Mehr durch Zufall wurden etwa 7000 (von etwa 1 Million) erstaunliche Sudokus gefunden, die sowohl als Standard-Sudokus und auch als Diagonal-Sudokus bzw. Farb-Sudokus bzw. Farbdiagonal-Sudokus lösbar waren; etwa 5500 davon waren in zwei Varianten, etwa 300 davon in den drei Varianten Diagonal-, Farb-, Farbdiagonal-Sudokus lösbar, und etwa 1200 in allen 4 Varianten. In den meisten Fällen ergab es die gleiche Lösung, nur in der Variante mit Diagonal- und Farb-Sudokus gab es auch jeweils unterschiedliche Lösungen (Dez. 2014). Näheres siehe "Lösbare Sudokus in verschiedenen Varianten".
Sechs direkte Sudoku-Lösungsmethoden - Standard-Sudokus (A bis F)
- Einfachste Methode: Einzige Position einer Zahl: Direkte Dreier-Methode oder eindeutige Stelle (Hidden Single): Bestimme die fehlende dritte Zahl in einem Block, also drei zusammen (nebeneinander oder untereinander) liegenden Boxen. D.h.: Findet man in zwei von drei zusammen liegenden Boxen eine bestimmte Zahl (die dann in zwei verschiedenen Zeilen bzw. Spalten liegen), sucht man in der dritten Box in der bisher nicht betrachteten Zeile bzw. Spalte nach einem eindeutigen Ort, an dem diese Zahl nur stehen kann (einfachster Typ A3). In vielen Fällen findet man auch beim Durchsuchen von ganzen (über alle Boxen gehenden) Zeilen bzw. Spalten (A1 bzw. A2) eine einzige Stelle, an der eine bestimmte Zahl nur stehen kann; da man dabei aber mehr Zellen ansehen muss, hat dieser Fall (A3) eine höhere Punktzahl.
Bewertung A1/A2: 0 bis 2 Punkte (bei 1-3, 4-6, 7-9 noch fehlenden Zahlen) innerhalb Zeilen/Spalten, A3: 0 bis 1 Punkt (1 Punkt nur bei jeweils 2 zu betrachtenden Zeilen und Spalten) innerhalb Boxen; Farbmarkierung: Grün
Beispiel für den einfachen Fall (A3):
In der dritten Box (OR) kann die Zahl 7 nur in der dritten Zeile sein; damit bleibt die letzte Spalte als einzig möglicher Ort übrig (mit kleinem x markiert).
PS: Der Übersichtlichkeit wegen wurden viele Zellen nicht ausgefüllt, da deren Inhalt ohne Bedeutung ist; ebenso fehlen im Allgemeinen die letzten Zeilen der Beispiel-Sudokus.
Beispiel für den komplexeren Fall (A1/A2):
Es kann auch in den Zeilen (A1) bzw. Spalten (A2) nachgesehen werden, ob eine Stelle für eine bestimmte Zahl frei ist. In diesem Beispiel kann in der fünften Zeile die Zahl 5 nur in Spalte 4 liegen. Denn in allen anderen Spalten im Bereich Spalte 2 bis 6 steht schon eine 5, und in der mittleren rechten Box (MR) kann eine 5 wegen der Zahl 5 in Zeile 6 und Spalte 9 nicht liegen (A1).
Beispiele mit vielen A-Fällen
- Einzig mögliche Zahl: Einzige noch fehlende Zahl an einem bestimmtem Ort (Naked Single): Man untersucht für einen Ort, welche der 9 Zahlen dort stehen könnten, wobei die Sudoku-Regeln berücksichtigt werden müssen. Bleibt nur eine Zahl übrig, hat man die Lösung für diese Stelle gefunden (B0). Das klingt zwar einfach, ist aber nicht so leicht zu erkennen (wenn man nicht alle Kandidaten schon aufgeschrieben hat) und man daher sehr viele Nachbarzellen ansehen muss (was eine hohe Punktzahl rechtfertigt).
Bewertung B0: 3 bis 0 Punkte (bei 8-12, 13-14, 15-16, 17-20 sichtbaren Zahlen); Farbmarkierung: Blau
Beispiel: Die einzige Zahl an der Position Zeile 3 und Spalte 4 (mit kleinem x markiert) kann nur die Zahl 7 sein, weil alle anderen Zahlen schon in gleicher Zeile (1, 4, 8, 9), in gleicher Spalte (2, 5), bzw. in gleicher Box (1, 2, 3, 6) vorhanden sind.
Beispiele mit vielen B-Fällen
- Offensichtlicher Zeilen-/Spalten-Test (Direct Pointing): Abwandlung der einfachsten Methode (A): Bestimme den Ort einer bestimmten Zahl z ohne genaue Kenntnis des Ortes dieser Zahl an den anderen Stellen: Hier nutzt man aus, dass dort die Position dieser Zahl zwar noch nicht genau bekannt ist, aber auf eine Zeile oder Spalte einer Box beschränkt werden kann (Darstellung mit "(z)"). Dann folgt der Ort für diese Zahl analog der oben beschriebenen Methode A (Kennung C1/C2/C3 analog A1/A2/A3). Die Methode C3 ist oft schneller (einfacher) zu sehen als die A1- und A2-Methoden (einzige Position in einer Zeile oder Spalte), wenn es nur eine einzige Begründung gibt.
Bewertung C1/C2: 0 bis 2 Punkte (bei 1-3, 4-6, 7-9 noch fehlenden Zahlen abzgl. Anzahl Begründungen - genauer: abzgl. aller mit den notwendigen Begründungen belegten Zellen) innerhalb Zeilen/Spalten, C3: 0 Punkte innerhalb Boxen. Dazu: Plus 1 + 2 * Anzahl der notwendigen Begründungen (hier nur bis zu 2 Begründungen) + 2 * Anzahl der "UND FOLGEND"-Fälle. Dabei mit 8 Punkten höchste erreichbare Punktzahl der direkten Lösungsmethoden; Farbmarkierung: Rot
Beispiel für den einfachen Fall (C3):
Im einfachen Fall weiß man, dass in der rechten Box (OR) die Zahl 6 nur in der zweiten Zeile sein kann, da die erste Zeile nicht in Frage kommt (wegen der 6 in Spalte 9) - die genaue Position der Zahl 6 in der mittleren Zeile dieser Box ist aber noch unbekannt. Hier ist sogar auch die Position dieser Zahl in der mittleren Box OM noch unbekannt. Trotzdem kann man daraus schließen, dass in der ersten Box (OL) die 6 nur in der dritten Zeile sein kann; in dieser Zeile bleibt dann nur die zweite Spalte als einzig möglicher Ort übrig (mit kleinem x markiert).
Beispiel mit 4 folgernden Begründungen (C3):
Offensichtlich gilt für Zahl 4: In Box 3#2 (UM) kann sie nur in Spalte 5 sein => Daraus folgt, dass sie in Box 2#2 (MM) nur in Zeile 5 möglich und deshalb in Box 2#3 (MR) nur in Spalte 9 möglich ist => Daraus folgt dann, dass Zahl 4 in Box 1#3 (OR) nur in Spalte 7 möglich ist. Damit bleibt als einzig möglicher Ort für die Zahl 4 in Box 3#3 (UR) nur Spalte 8 und somit nur Zeile 8 übrig (mit kleinem x markiert).
Beispiel für den komplexeren Fall (C1/C2):
Wegen der Zahl 7 in der rechten mittleren Box (MR) kann in der davor liegenden Box (MM) die 7 nicht in Zeile 5 stehen. Damit bleiben als mögliche Orte für die 7 in dieser Box nur die beiden Positionen in der Spalte 5 übrig (mit (7) angezeigt).
Nun kann man ähnlich wie im einfachen Fall folgern, dass die Zahl 7 in der 3. Zeile nicht in Box OL stehen kann (in dieser Box ist schon eine 7), auch nicht in Box OM wegen der 7 irgendwo in Spalte 5 von Box MM (mit (7) markiert), aber auch nicht in Spalte 8 der Box OR (wegen der 7 in Box MR), und somit bleibt in Zeile 3 nur die Spalte 9 (mit kleinem x markiert) als Zielort übrig (C1).
Variante C0:
Die einzig mögliche Zahl entsprechend der B0-Methode kann manchmal gefunden werden ohne genaue Ortskenntnis von anderen Zahlen entsprechend offensichtlichen Zeilen-/Spalten-Tests.
Bewertung C0: 3 bis 0 Punkte (bei 8-12, 13-14, 15-16, 17-20 sichtbaren Zahlen abzgl. Anzahl Begründungen); Dazu: 1 + Plus 2 * Anzahl der offensichtlichen Zeilen-/Spalten-Tests + 2 * Anzahl der "UND FOLGEND"-Fälle.
Beispiel für diese Variante:
In Box 1#2 (OM) muss die Zahl 6 in Zeile 1 liegen; daher kann in Zeile 1 und Spalte 3 (mit kleinem x markiert) nur die Zahl 2 sein.
Variante C7:
Ist in einer Box eine Zahl nur innerhalb einer Zeile und einer Spalte möglich, so muss diese am Kreuzungspunkt liegen.
Bewertung C7: 5 Punkte, da 2 Offensichtliche Zeilen-/Spalten-Tests
Beispiel für diese Variante:
In Box 1#3 (OM) muss die Zahl 9 in Zeile 3 und Spalte 7 liegen (mit kleinem x markiert); denn die Zahl 9 kann in Zeile 3 nur in dieser Box sein (denn Spalte 4 ist durch die 9 in Zeile 7 belegt) und in Spalte 7 auch nur in dieser Box sein (denn in Zeile 9 kann in Spalte 7 keine 9 liegen - wegen der 9 dort in Spalte 2).
Beispiele mit vielen C-Fällen
- Offensichtliche 2-Tupel (Doppel) (Direct Hidden Pair): In vielen Fällen sieht man zwei Zellen innerhalb einer Zeile, Spalte oder Box, in denen genau zwei bestimmte Kandidaten vorkommen müssen, weil sie in allen anderen Zellen dieser Zeile, Spalte bzw. Box nicht vorkommen können. Diese werden hier offensichtliche 2-Tupel (Doppel) genannt und entsprechen häufig Versteckten 2-Tupeln. Da diese beiden Zellen nicht mit anderen Zahlen belegt werden können, ermöglicht dies dadurch das Auffinden anderer Zahlen, ohne dass die Kandidaten in allen Zellen aufgeschrieben werden müssen. Dabei gibt es zuerst die drei Methoden D1/D2/D3 analog A1/A2/A3, und drei Varianten D0, D7 und D8.
Bewertung D1/D2: 0 bis 2 Punkte (bei 1-3, 4-6, 7-20 noch fehlenden Zahlen abzgl. 2* Anzahl Doppel - genauer: abzgl. aller mit den notwendigen Doppeln belegten Zellen) innerhalb Zeilen/Spalten, D3: 0 Punkte innerhalb Boxen. Dazu: Plus 1 + 2 * Anzahl der notwendigen Doppel; Farbmarkierung: Gelbgrün
Beispiel für den einfachen Fall (D3):
Wegen des offensichtlichen 2-Tupels 15 in der Box OM (1 und 5 gehen nicht in der mittleren Zeile und auch nicht in der mittleren Spalte) kann die einzige Zahl an der Position Zeile 2 und Spalte 6 (mit kleinem x markiert) nur die Zahl 7 sein bzw. die Zahl 7 dieser Box kann nur in Zeile 2 und Spalte 6 stehen (da sie nicht in Spalte 5 und nicht in Zeile 3 der Box OM sein kann).
Variante D0:
Die einzig mögliche Zahl entsprechend der B0-Methode kann manchmal gefunden werden ohne genaue Ortskenntnis von zwei anderen Zahlen, die ein offensichtliches 2-Tupel (Doppel) bilden.
Bewertung D0: 3 bis 0 Punkte (bei 8-12, 13-14, 15-16, 17-20 sichtbaren Zahlen abzgl. 2 * Anzahl Doppel - genauer: abzgl. aller mit den notwendigen Doppeln belegten Zellen); Dazu: Plus 1 + 2 * Anzahl der notwendigen Doppel
Beispiel für diese Variante:
Durch das offensichtliche 2-Tupel 48 kann ausgeschlossen werden, dass die Zahlen von diesem 2-Tupel (4 und 8) an der betrachteten Stelle (mit kleinem x markiert) liegen; daher kann dort nur die Zahl 9 sein.
Variante D7:
Kreuzen sich zwei offensichtliche, aber verschiedenen 2-Tupeln in einer einzigen Zelle, kann diese Zelle nur den gemeinsamen (in beiden Paaren der 2-Tupel vorkommenden) Kandidaten haben. Diese Variante tritt nur im synchronen Fall auf.
Bewertung D7: 5 Punkte, da 2 Doppel
Beispiel für diese Variante:
In der mittleren Zeile der linken Box (OL) können 1 und 7 nicht vorkommen; in der dritten Zeile können 4 und 7 nicht in der rechten Box (OR) liegen: Die einzige Zahl an der mit kleinem x markierten Stelle kann also nur die den beiden Doppeln gemeinsame Zahl 7 sein.
Variante D8:
Beim Auftreten von zwei offensichtlichen und gleichen 2-Tupeln in drei Ecken eines Ausschluss-Rechtecks (in zwei Zeilen, zwei Spalten und zwei Boxen) kann die nicht besetzte Ecke eventuell einen einzigen möglichen Kandidaten haben, wobei die Kandidaten des 2-Tupels als sichtbar angesehen werden (ähnlich D0).
Bewertung D8: 5 Punkte, da 2 Doppel
Beispiel für diese Variante:
Es gibt fast ein offensichtliches Ausschluss-Rechteck mit den Resten 29 in Zeile 1 und 6, und in Spalte 2 und 3, und in BOX OL und ML, wobei in Zeile 1 und Spalte 3 (mit kleinem x markiert) der Rest 239 möglich ist, d.h. von dieser Zelle aus können alle Zahlen außer 2, 3 und 9 gesehen werden. Wäre aber in dieser Zelle eine 2 oder eine 9, läge wegen der eindeutigen Lösbarkeit eines Sudokus ein Ausschluss-Problem vom einfachen Typ 1 vor (siehe unter Ausschluss-Rechtecke). Also kann nur die Zahl 3 der Wert für diese Zelle sein.
Beispiele mit vielen D-Fällen
- Vollständige Ausdünnung mit einem alleine auftretendem Kandidaten: Hat man nach einem oder mehreren Ausdünnschritten mehrere Reste (Kandidatenliste) so weit verkleinert, dass ein bestimmter Kandidat nur noch an einer einzigen Stelle innerhalb der Reste einer Zeile, einer Spalte oder einer Box vorkommt, ist diese Zahl Lösung für diese Stelle (Kennung E1/E2/E3 analog A1/A2/A3).
Bewertung E1/E2: 0 bis 1 Punkt (bei 1-3, 4-9 mit Resten belegten Zellen) innerhalb Zeilen/Spalten, E3: 0 bis 1 Punkt (bei 1-6, 7-9 mit Resten belegten Zellen) innerhalb Boxen; Farbmarkierung: Lila
Ausdünnung:
Hier wird davon ausgegangen, dass zuerst versucht wird, das Sudoku ohne Anschreiben der Reste (das sind die Kandidaten, also die möglichen Zahlen für die jeweilige Stelle) zu lösen (Methoden A, B, C und D). Kommt man damit nicht weiter, muss man für jede freie Stelle alle Zahlen aufschreiben, die für diese Stelle in Frage kommen (also die dafür überhaupt noch möglichen Zahlen): Das sind die Kandidaten für die jeweilige Stelle, die hier als Ganzes "Rest" genannt und auch der Einfachheit halber als eine mehrstellige Zahl (ohne Komma oder andere Trennzeichen, unterhalb der Eingabefelder) geschrieben werden.
Danach versucht man, diese Reste so lange "auszudünnen", also zu verkürzen, bis man zu einer eindeutigen Lösung für eine Stelle kommt (Methoden E und F). Die Ausdünn-Methoden I bis VI werden im nächsten Abschnitt ausführlich beschrieben.
Beispiel für den Fall (E1):
Nach der Ausdünn-Methode II (N-Tupel, siehe weiter unten im nächsten Abschnitt) hat man z.B. in der oberen rechten Box (OR) in Spalte 9 das Reste-Paar 79 zwei Mal (hier ohne genaue Begründung) gefunden. Die Zahlen 7 und 9 müssen also an diesen beiden Stellen auftreten. Damit können in allen anderen Resten (Kandidatenlisten) dieser Box die Zahlen 7 und 9 gestrichen werden (mit [zahl] markiert). Da nun in Zeile 1 nur noch an einer einzigen Stelle der Kandidat 7 (Zeile 1 und Spalte 4 - mit kleinem x markiert) auftritt, kann er dort gesetzt werden.
- Vollständige Ausdünnung mit einem einzig möglichen Kandidaten (einstelliger Rest): Hat man nach einem oder mehreren Ausdünnschritten einen Rest so weit verkleinert, dass er nur noch aus einer Zahl besteht, ist diese Zahl die Lösung für die betrachtete Stelle (Kennung F0 analog B0).
Bewertung F0: 0 Punkte bei letzter Möglichkeit, 0 Punkte bei einziger Möglichkeit; Farbmarkierung: Braun
Beispiel für F0:
Nach der Ausdünn-Methode I (Box-Test, siehe weiter unten im nächsten Abschnitt) kommt die Zahl 9 innerhalb der zweiten Zeile nur in der ersten Box (OL) vor: Daher muss die 9 dort sein (auch wenn man die Position innerhalb der zweiten Zeile noch nicht weiß) - sie kann also nicht in der dritten Zeile dieser Box noch einmal vorkommen. Daher kann man aus den Resten dieser Zeile in der Box OL den Kandidaten 9 streichen.
Damit bleibt an der Position Zeile 3 und Spalte 3 (mit kleinem x markiert) nur noch die 3 als Kandidat übrig. Also hat man einen eindeutigen Rest an dieser Stelle gefunden und kann die Zahl 3 dort setzen.
Sechs Methoden zur Ausdünnung der Reste (Kandidatenliste) (I bis VI)
Der Begriff der Ausdünnung zur Verkürzung der Reste (Kandidatenliste) wurde im vorherigen Abschnitt unter Methode E schon kurz erläutert (Verkleinerung der Liste der für eine Zelle nur noch möglichen Kandidaten durch verschiedene Ausdünn-Methoden). Im Allgemeinen sind, um eine Lösung zu finden, immer mehrere Ausdünnschritte notwendig (im nicht-synchronen Fall oft 5 bis 20 Ausdünnschritte, aber es wurden auch schon 30 Ausdünnschritte direkt nacheinander, ehe eine Zahl gesetzt werden konnte, beobachtet!). Manche Schritte helfen dabei nicht zur Lösungsfindung, aber das weiß man vorher nicht.
Beispiele für Sudokus, bei denen sehr viele verschiedene Ausdünn-Methoden benutzt werden: Siehe Sudokus mit möglichst allen Ausdünn-Methoden.
Das Aufschreiben der möglichen Kandidaten von Hand (!) ist aufwändig und fehleranfällig; dafür werden 25 % der Anzahl der Kandidaten als Extra-Punkte angerechnet.
In den folgenden Beispielen werden oft nur Teile eines Sudokus mit entsprechenden Resten dargestellt, um das Ganze übersichtlicher zu machen; es sind Ausschnitte aus aktuellen Sudokus.
- Test der Kandidaten jeder Zelle (Reste) innerhalb einer Box und innerhalb einer Zeile/Spalte: Kommt innerhalb einer Zeile bzw. Spalte einer Box ein Kandidat in mehreren Feldern vor, kann man eventuell diesen Kandidaten in anderen Feldern streichen, entweder wenn dieser Kandidat in den anderen Feldern der betrachteten Box nicht vorkommt (dann kann er aus den anderen Feldern der Zeile bzw. Spalte gestrichen werden: Zeilen-/Spalten-Test) oder wenn dieser Kandidat in den anderen Feldern der betrachteten Zeile bzw. Spalte nicht mehr vorkommt (dann kann er aus den anderen Feldern der Box gestrichen werden: Box-Test).
- Zeilen-/Spalten-Test der Reste innerhalb einer Box (Block/Line Interaction, Pointing): Man sieht in den Resten nach, ob innerhalb einer Box eine Zahl vorkommt, die nur genau in einer Zeile bzw. Spalte dieser Box auftaucht - diese Zahl muss dann in dieser Zeile bzw. Spalte dieser Box stehen (wobei die genaue Position noch unbekannt ist). Dann kann man in den anderen Resten dieser Zeile bzw. Spalte außerhalb der Box diese Zahl streichen.
Bewertung: 3 Punkte.
Beispiel:
Hier findet man z.B. die Zahl 1: Sie ist in den Resten der Box OL nur in der zweiten Zeile vorhanden (rot gefärbter Rest), nicht in den anderen Zeilen dieser Box. Also kann man in den anderen Resten dieser Zeile in den anderen beiden Boxen diese Zahl streichen (durch die Darstellung in eckigen Klammern hervorgehoben). Damit bleibt übrig:
Beispiele mit vielen Zeilen-/Spalten-Tests
- Box-Test der Reste in einer Zeile oder Spalte (Line/Block Interaction, Claiming): Man sieht in den Resten einer Box nach, ob innerhalb einer Zeile bzw. Spalte eine Zahl vorkommt, die nur genau in dieser Box auftaucht. Diese Zahl muss also innerhalb dieser Box in der gefundenen Zeile bzw. Spalte stehen (wobei die genaue Position noch unbekannt ist), sie kann dann aber aus den Kandidaten der anderen Zeilen bzw. Spalten innerhalb dieser Box gestrichen werden.
Bewertung: 3 Punkte.
Beispiel:
Hier findet man z.B. die Zahl 1: Sie ist innerhalb der ersten Zeile nur in den Resten der rechten Box OR vorhanden (rot gefärbter Rest). Also kann man in den anderen Zeilen dieser Box diese Zahl aus den Resten streichen - das wird auch hier durch die Darstellung in eckigen Klammern hervorgehoben. Damit bleibt übrig:
Beispiele mit vielen Box-Tests
- N-Tupel (Naked Pair, Hidden Pair, Naked Triple, Hidden Triple, Naked Quadruple, Hidden Quadruple): Man sucht in einer Zeile, Spalte oder Box nach N-Tupel, also danach, dass bestimmte Kandidaten an nur wenigen Stellen auftreten: Genauer heißt das, dass man N verschiedene Zahlen und dazu N Felder innerhalb einer Zeile, Spalte oder Box sucht, in denen diese N Kandidaten auftreten, diese Kandidaten aber nicht in den anderen Feldern der untersuchten Zeile, Spalte oder Box stehen. Wenn an den N Stellen alle oder ein Teil der N betrachteten Kandidaten stehen, können diese Kandidaten nur an diesen N Stellen auftreten (wobei die Verteilung noch unbekannt ist); diese Kandidaten können dann aber aus den anderen Feldern gestrichen werden. Sind an diesen N Stellen keine anderen Zahlen zu finden, ist das ein direktes N-Tupel.
Liegen in den N Feldern nicht nur die N verschiedenen Kandidaten, sondern auch noch andere Zahlen, wobei die N Kandidaten aber nicht außerhalb dieser N Feldern (der gleichen Zeile, Spalte oder Box) sein dürfen, so hat man ein "Verstecktes N-Tupel".
Es gibt 2-Tupel (Doppel), 3-Tupel (Tripel), 4-Tupel (Quadrupel), 5-Tupel (Pentupel), 6-Tupel (Sextupel) und 7-Tupel (Septupel) - 8-Tupel machen keinen Sinn, da dann die neunte Zahl eindeutig ist und somit direkt gefunden werden kann. Zu jedem gefundenen N-Tupel gehört ein entsprechendes Verstecktes M-Tupel (mit den M anderen Kandidaten), wobei N+M gleich der Anzahl der freien Felder innerhalb einer Zeile, Spalte oder Box ist. Sind die N Kandidaten aus den anderen Resten gestrichen worden, wird aus dem Versteckten M-Tupel ein normales M-Tupel (im ersten Beispiel gibt es zu dem Doppel 79 das Versteckte Tripel 345).
Bewertung: 2, 5, 8, 11 (und theoretisch 14 und 17) Punkte, also 3*N-4 Punkte (N ist die Länge des direktes N-Tupels), für ein Verstecktes M-Tupel gibt es 8, 11 (und theoretisch 14, 17 u.s.w.), also 3*M+2 Punkte - insgesamt zählt aber die kleinere Punktzahl.
PS: Ein 2-Tupel (Doppel) - in der Sudoku-Literatur fälschlicherweise "Paar" geannt - besteht also aus 2 Paaren, ein 3-Tupel (Tripel) aus 3 Paaren oder Trios (Zelle mit 3 Kandidaten), u.s.w..
Einfaches Beispiel mit 2-Tupel (Doppel):
Hier findet man z.B. in der ersten Zeile das 2-Tupel 79 (Doppel: 79, 79), als rot gefärbte Reste markiert - bzw. das Versteckte 3-Tupel 345 (Tripel: 34, 345, 345); die beiden Kandidaten 7 und 9 müssen also an den beiden Stellen des Doppels sein. Also kann man in den anderen Resten dieser Zeile diese beiden Zahlen streichen (wieder durch die Darstellung in eckigen Klammern hervorgehoben). Damit bleibt übrig:
Kurzes Beispiel mit 3-Tupel (Tripel):
Hier findet man in der Box OM (und in der 5. Spalte) das 3-Tupel 235 (Tripel: 235, 23, 25). Damit können in allen anderen Resten dieser Box (und in der 5. Spalte) die Kandidaten 2, 3 und 5 gestrichen werden.
Beispiel mit einem Versteckten 3-Tupel (Tripel):
Hier findet man in Zeile 1 in den Spalten 1, 2 und 9 das Versteckte 3-Tupel 349 (Tripel: 34789,3489,23689). Damit können in diesen Zellen die zusätzlichen Kandidaten 2, 6, 7 und 8 gestrichen werden. Dazu gehört das 6-Tupel (Sextupel) 125678 (58,5678,167,158,28,268). Da das 6-Tupel 14 Punkte wert ist, das Versteckte 3-Tupel aber 11 Punkte, wird der kleinere Wert 11 als Punktzahl benutzt. Daher sind Versteckte N-Tupel nur bis N = 3 sinnvoll.
Beispiel mit 4-Tupel (Quadrupel):
Relativ häufig (in etwa 10% aller N-Tupel-Fälle) findet man noch 4-Tupel, aber 5-Tupel, 6-Tupel und 7-Tupel sind sowohl noch seltener (1-2 %) als auch schwieriger zu erkennen. Dann kann man aber eventuell leichter ein Verstecktes M-Tupel sehen. Liegt in einer Zeile, Spalte oder Box mit N+M Kandidaten ein N-Tupel vor, so gibt es immer auch ein Verstecktes M-Tupel. So gibt es im obigen Beispiel in der Box OM das (triviale) Versteckte 3-Tupel 147 (in 2357, 12457, 12457). Bei der Bewertung werden aber im Allgemeinen die direkten N-Tupel vorgezogen, da sie einfacher zu erkennen sind.
In diesem Beispiel findet man in der 3. Zeile das 4-Tupel 3568 (Quadrupel: 3568, 3568, 568, 368). Damit können in allen anderen Resten dieser Zeile die Kandidaten 3, 5, 6 und 8 gestrichen werden.
NEU: Entferntes Doppel im Block (Chute Remote Pairs von Andy Potvin). Man sucht in einem waagrechten (bzw. senkrechten) Block nach zwei Paaren (Zellen mit zwei gleichen Kandidaten) in zwei verschiedenen Zeilen (bzw. Spalten), die sich also nicht gegenseitig sehen.
Dann betrachtet man die nicht benutzte Zeile (bzw. Spalte) in der nicht benutzten Box. Liegt dort nur einer der Kandidaten vor, kann er in den von den beiden Paar-Zellen aus sichtbaren Zellen gestrichen werden (Begründung siehe Beispiel).
Sind dort aber beide Kandidaten vorhanden, kann nichts gestrichen werden.
Ist keiner der Kandidaten dort vorhanden, können beide Kandidaten in den sichtbaren Zellen gestrichen werden; in diesem Fall können auch noch die entsprechenden Kandidaten in den Zeilen (bzw. Spalten), in denen die Paar-Zellen liegen, gestrichen werden (außer den Paar-Zellen selbst); siehe unten stehendes Beispiel.
Bewertung: 3 Punkte.
Quelle: SudokuWiki von Andrew Stuart: Chute_Remote_Pairs
Einfaches Beispiel:
Hier findet man das Doppel 59 in Zeile 1/Box 3 (1:8)59 und in Zeile 3/Box 1 (3:3)59. In der nicht betrachteten Zeile 2 liegt in der nicht betrachteten (mittleren) Box 2 der Kandidat 9, aber nicht die 5, die also in dieser Zeile entweder in Box 1 oder Box 3 liegen muss. Wäre nun aber in der Zeile 1/Box 1 eine 9 wie in (1:1)359, dann kann in beiden entfernten Paaren keine 9 sein, dort muss dann eine 5 stehen. Da aber in der mittleren Zeile entweder in Box 1 oder in Box 3 eine 5 sein muss (hier in den Zellen (2:1)58 oder (2:7)58), führt das zum Widerspruch - das Gleiche gilt, wenn man annimmt, dass in Zeile 3/Box 3 eine 9 liegt wie in (3:7)29 oder (3:8)2589. Somit kann man die 9 in den von beiden entfernten Paaren aus sichtbaren Zellen in Zeile 1 (1:1)[9] und in Zeile 3 in (3:7)[9] und (3:8)[9] streichen. Damit bleibt übrig:
Beispiel mit Bonus-Streichungen:
Das Entfernte Doppel im Block wird hier den möglichen Doppeln und Tripeln vorgezogen, da dadurch 7 Kandidaten auf einmal gestrichen werden können. Man findet im zweiten senkrechten Block das entfernte Doppel 13 in Spalte 4 bei (3:4)13 und in Spalte 5 bei (8:5)13. In der nicht betrachteten 6. Spalte liegt in der mittleren nicht betrachteten Box keiner der beiden Kandidaten. Damit kann man beide Kandidaten in den von den Paar-Zellen aus sichtbaren Zellen in Zeile 1 und Spalte 5 und in Zeile 7 und Spalte 4 streichen (blau markiert).Bonus-Streichungen: Darüber hinaus können diese Kandidaten auch in Zeile 1 und Spalte 4 gestrichen werden (grün markiert), obwohl diese Zelle (1:4) nicht von (8:5) aus gesehen wird: Denn wenn z.B. der Kandidat 1 in (1:4)[1] wäre - also in Spalte 4, muss die 1 in Spalte 5 in der mittleren Box liegen, da sie dort nicht in Spalte 6 ist. Daraus folgt wegen der jeweils gesetzten 1 insgesamt: Es muss der Kandidat 3 in beiden Paaren des Entfernten Doppels gesetzt sein, d.h., in der mittleren Box gibt es dann keine Zelle mit einer 3, was ein Widerspruch ist.
Das gilt analog auch für den Kandidaten 3 in (1:4), aber auch für die 3 in (9:5)[3], die nicht von (1:4) aus gesehen wird: Denn ist dort die 3 gesetzt, muss in der mittleren Box die 3 in Spalte 4 liegen, was bedeutet, weil dann in allen Paaren des Entfernten Doppels eine 1 stehen muss, weshalb in dieser Box keine 1 sein kann, was also wieder ein Widerspruch ist.
Allgemein heißt das: Alle in den (hier) Spalten liegenden Kandidaten des Entfernten Doppels können in den (hier) Spalten, in denen das betrachtete Doppel liegt, gestrichen werden - außer natürlich die des Doppels selbst; damit sind maximal 8 zusätzliche Streichungen möglich.
Beispiele mit vielen N-Tupeln
- Goldene Kette (Golden Chain, XY-Chain, Double Implication Chain): Hier betrachtet man alle Zellen mit Paaren, und zwar sucht man jeweils zwei Paare, die in der gleichen Zeile, Spalte oder Box liegen und genau einen gemeinsamen Kandidaten haben. Eine Goldene Kette ist dann eine zusammenhängende Folge von solchen Paaren, also von der Form ab, bc, cd, ..., xy, yz, za. Wenn die Zahl des ersten Paares, die nicht im zweiten Paar vorkommt (hier also a) mit der Zahl des letzten Paares, die nicht im vorletzten Paar vorkommt (hier also auch a), übereinstimmt, dann kann man alle Kandidaten a streichen, die sowohl von dem ersten als auch dem letzten Paar aus "gesehen" werden, also in der jeweils gleichen Zeile, Spalte oder Box liegen.
Eine Goldene Kette der Länge 2 ist identisch mit einem 2-Tupel (Doppel): ab, ba. Goldene Ketten länger als 12 sind sehr selten (weit unter 0.1 %).
Eine Goldene Kette kann geschlossen sein, wenn jede der betroffenen Zellen als Ausgangspunkt dienen kann - dadurch kann man mehr Kandidaten streichen.
Eine Erweiterung der Goldenen Kette der Länge 3 ist der XYZ-Wing, bei dem die mittlere Zelle 3 Kandidaten besitzt. Man kann diese Methode auch als ein 3-Tupel (Tripel) mit einem Knick auffassen. Man betrachtet dabei die Zahl, die in allen Zellen des XYZ-Wings vorkommt, und die dann in von allen vom XYZ-Wing aus sichtbaren Zellen gestrichen werden kann. Nähere Beschreibung siehe weiter unten.
Eine Verallgemeinerung des XYZ-Wings ist der WXYZ-Wing, bei dem 4 Zellen insgesamt 4 verschiedene Kandidaten besitzen. Man kann diese Methode auch als ein 4-Tupel (Quadrupel) mit einem Knick auffassen. Der Standard-WXYZ-Wing ist ähnlich dem XYZ-Wing; der Erweiterte WXYZ-Wing hat aber etwas andere Regeln. Nähere Beschreibung ebenso siehe weiter unten.
Bewertung: 6, 7, 8, 9, usw. bis 17 Punkte, also N+3 Punkte entsprechend der Länge N der gefundenen Kette (N = 3 bis 14; längere Goldene Ketten sind zwar möglich, aber wenig sinnvoll, weil sie extrem selten auch wirkend sein wären). Der XYZ-Wing erhält 7 Punkte (statt 6 bei der 3er-Goldenen Kette); der WXYZ-Wing 10 Punkte (3 Punkte mehr als der XYZ-Wing), aber 11 Punkte, wenn es die erweiterte Form ist.
Literatur:
Download des Artikels von Eduyng Castan: http://www.coverpop.com/sfiles/Sudoku-GoldenChains.pdf (nicht mehr erreichbar)
Ähnlicher Artikel von Mihail Iusut: http://www.scanraid.com/sudoku/Remote_Pairs_and_XY_Chains.pdf
Beschreibung des WXYZ-Wings von Andrew Stuart: https://www.sudokuwiki.org/WXYZ_Wing
Beispiel einer Goldenen Kette:
Die gefundene Goldene Kette für die Zahl 2 ist: (1:2)27 - (1:7)73 - (4:7)31 - (4:1)12.
Beachte, dass hier die Reihenfolge der Zahlen innerhalb eines Doppels dem Verkettungs-Prinzip angepasst ist: Also 73 statt der sonst aufsteigenden Reihenfolge 37 und 31 statt sonst 13. Das jeweilige Ende der Goldenen Kette ist also die Zahl 2, die daher in Zelle (2:1), also Zeile 2 und Spalte 1, und in Zelle (5:2), also Zeile 5 und Spalte 2, gestrichen werden kann.
Identisch mit der gefundenen Goldenen Kette ist auch die in umgekehrter Reihenfolge: (4:1)21 - (4:7)13 - (1:7)37 - (1:2)72.
Beispiel eines XYZ-Wings:
Wenn in der mittleren Zelle ("Knickstelle") des XYZ-Wings (Zeile 1, Spalte 1) die 9 auftritt, kann sie in Zeile 1 und Spalte 3 (in der Box) gestrichen werden. Hat die mittlere Zelle aber den Wert 2, muss die 9 in der ersten Zelle des XYZ-Wings (Zeile 1, Spalte 4) stehen; umgekehrt gilt, wenn die mittlere Zelle den Wert 8 hat, muss die 9 in der dritten Zelle des XYZ-Wings (Zeile 2, Spalte 3) stehen. Auch in diesen beiden Fällen kann die 9 in von allen drei Stellen aus sichtbaren Zellen, hier nur Zeile 1 und Spalte 3, gestrichen werden. Ohne der 9 in Zeile 1 und Spalte 1 hätte man die 3er-Goldene Kette (1:4)92 - (1:1)28 - (2:3)89 mit der gleichen Folge, dass die 9 in Zeile 1 und Spalte 3 gestrichen werden kann.
Hier sieht man auch, dass diese Methode auch auf 4 (dann WXYZ-Wing genannt) oder mehr Kandidaten ausgeweitet werden kann. Die WXYZ-Methode ist - insbesondere durch die erweiterte Version - 4 Mal häufiger als die XYZ-Methode, bei der die Erweiterung nichts bringt.
Beispiel eines Standard-WXYZ-Wings, wobei diese aber relativ selten sind (3 % aller WXYZ-Wings):
Die Kandidaten in der "Knickstelle" sind 4567; wäre 4 richtig, folgt daraus eine 6 in Zeile 3 und Spalte 5; wäre 5 richtig, folgt aber eine 6 in Zeile 1 und Spalte 1; wäre 7 richtig, folgt eine 6 in Zeile 1 und Spalte 3. Und wäre 6 richtig, kann sowieso keine 6 in Zeile 1 und Spalte 5 sein. In allen Fällen ist eine 6 in Zeile 1 und Spalte 5 nicht möglich.
Beispiel eines erweiterten WXYZ-Wings:
Die Definition des erweiterten WXYZ-Wings besagt, dass genau einer der 4 Kandidaten des Wings nicht alle Vorkommen dieses Kandidaten im WXYZ-Wing sehen darf, während die anderen 3 Kandidaten sich alle gegenseitig sehen sollen.
Die Kandidaten 2, 6 und 9 sehen sich alle gegenseitig (gleiche Zeile oder gleiche Box), Kandidat 3 liegt aber in verschiedenen Boxen in verschiedenen Zeilen. Damit können alle Kandidaten 3 der anderen Zellen, die von diesen (beiden) Kandidaten 3 aus gesehen werden, gelöscht werden. Bei dieser Variante können oft viele Kandidaten gestrichen werden.
Beispiele mit vielen Goldenen Ketten/XYZ-Wings/WXYZ-Wings
- Einzelzahl-Gitter (X-Wing, Swordfish, Jellyfish), Einzelzahl-Ketten (Single Digit Pattern, Forcing X-Chain, X-Chain Nice Loop) und die ganz neuen Einzelzahl-Widerspruchs-Ketten: Erweiterung der einfachen X-Wing-Methode (4 Zellen in den Ecken eines Rechtecks mit einem gemeinsamen Kandidaten, 2*2-Einzelzahl-Gitter) in zwei Richtungen: Ermittlung von 3*3- und 4*4-Einzelzahl-Gittern, und Ausbau auf fast beliebige Formen: Eine Kette aus Resten, bei denen überall ein gemeinsamer Kandidat vorkommt (das verbindendes Element).
Holger Schrader hat auch die neue Methode der Einzelzahl-Widerspruchs-Kette gefunden. Dabei nimmt man entlang einer Kette an, dass dort eine bestimmte Zahl abwechselnd gesetzt bzw. nicht gesetzt ist und leitet daraus einen Widerspruch ab. Diese Methode ist erstaunlicherweise etwa 10 Mal häufiger einsetzbar als normale Einzelzahl-Ketten; und wegen ihrer Kürze sind sie auch gut zu erkennen.
Einzelzahl-Kette: Man sieht für eine bestimmte Zahl in den Kandidaten nach, ob in Zeilen oder Spalten oder Boxen diese Zahl genau zwei Mal vorkommt (interessant ist hierbei, dass die anderen Kandidaten der jeweiligen Reste keine Rolle spielen, egal welche und wie viele es sind). Hat man mehrere solcher sogenannten starken Verbindungen (strong link) gefunden, lassen sich diese eventuell dadurch so zu einer Einzelzahl-Kette verbinden, dass jeweils ein Anfang oder Ende in der gleichen Zeile, Spalte oder Box wie eine andere starke Verbindung liegen; außerdem können jeweils zwei starke Verbindungen auch über nicht-starke Verbindungen (mehr als zwei Mal Auftreten der betrachteten Zahl) verbunden werden. Wenn sowohl vom Anfang einer so konstruierten Kette als auch vom Ende dieser Kette ein oder mehrere Felder "gesehen" werden, die also in der jeweils gleichen Zeile, Spalte oder Box liegen, kann die bestimmte Zahl aus diesen Feldern gestrichen werden. Es gilt: Entweder liegt die bestimmte Zahl am Anfang der Kette; ist das nicht der Fall, gilt folgender Schluss: Liegt diese Zahl nicht im ersten Feld der Kette, muss sie aber im zweiten Feld liegen, da dieses eine starke Verbindung ist; dann kann sie jedoch nicht im dritten Feld sein, muss somit im vierten Feld liegen, usw. - d.h. in jedem 2*K-ten Feld der Kette muss dann die bestimmte Zahl liegen, also auch - wegen der Geradzahligkeit der Kettenglieder - im letzten Feld am Ende der Kette.
Eine Einzelzahl-Kette kann geschlossen sein, wenn jede der betroffenen Zellen als Ausgangspunkt dienen kann - dadurch kann man mehr Kandidaten streichen.
NEU: Einzelzahl-Widerspruchs-Kette: Hier sieht man ebenfalls für eine bestimmte Zahl in den Kandidaten nach, ob in Zeilen oder Spalten oder Boxen diese Zahl genau zwei Mal vorkommt (starke Verbindung) oder auch mehr als zwei Mal vorkommt (schwache Verbindung). Hat man mehrere solcher Fälle gefunden, lassen sich diese eventuell zu einer Kette verbinden. Nach einer schwachen Verbindung muss aber direkt eine starke Verbindung folgen. Dann nimmt man an, dass im ersten Glied und den anderen ungeraden Stellen der Kette die Zahl gesetzt ist, in den anderen aber nicht. Das führt dann oft zu Widersprüchen, etwa dass in einer Zeile, Spalte oder Box keine solche Zahl auftreten kann oder diese Zahl mehr als einmal auftritt, weshalb daher die Zahl in allen ungeraden Kettengliedern gestrichen werden kann. Sind alle Verbindungen stark, ist es eine Kette vom Typ 1, sonst vom Typ 2, der dafür aber auch viel häufiger auftritt. Der Typ 2 bekommt als zusätzliche Information eine Folge von O und X angehägt, wobei das O für eine starke, das X für eine schwache Verbindung steht; Beispiel Typ 2OOXO. Bei Typ 2 können nur die gesetzten Zahlen der Ketten gestrichen werden, die vor dem X-Fall liegen.
Bei Einzelzahl-Widerspruchs-Ketten vom Typ 1 ist oft durch Verlängerung der Kette um ein Glied eine (echte) Einzelzahl-Kette möglich - dadurch können mehr Kandidaten gestrichen werden. Dann werden beide Ketten angegeben und die streichbaren Kandidaten aus beiden Ketten angezeigt.
Häufigkeiten der Einzelzahl-Widerspruchs-Ketten: Typ 1 wird zu etwa 3 % gefunden; Typ 2XO ist mit etwa 74 % am häufigsten, etwa 22 % entfallen auf die 5er-Typen 2XOOO, 2XOXO und 2OOXO; die Längen 7 und 9 werden nur zu etwa 2 % gefunden; die Länge 11 ist extrem selten.
Bewertung Einzelzahl-Gitter: 6, 9, 12, also 3*N Punkte entsprechend der Länge N des gefundenen N*N-Gitters.
Bewertung Einzelzahl-Ketten: 7, 9, 11, 13, 15 Punkte, also N+3 Punkte entsprechend der Länge N der gefundenen Kette (N = 4 bis 12, immer geradzahlig).
Bewertung Einzelzahl-Widerspruchs-Ketten: Ebenfalls 7 bis 15 Punkte, also N+4 Punkte entsprechend der Länge N der gefundenen Kette (N = 3 bis 11)
Sonderfälle der Einzelzahl-Verfahren: Skyscraper, Turbot Fish, Two-String Kite (Long String Kite und Empty Rectangle sind Erweiterungen), hier aber nicht eingebaut.
Beispiel eines 2*2-Einzelzahl-Gitters (X-Wing):
X-Wing ist der Basistyp der Einzelzahl-Gitter- und Einzelzahl-Ketten-Methoden: Ein Rechteck von Zellen, die alle den gleichen Kandidaten haben - entweder alleine in den Zeilen oder alleine in den Spalten. Dann kann der Kandidat in den nicht im Rechteck liegenden Zellen der betroffenen Spalten bzw. Zeilen gelöscht werden, weil in 2 diagonal gegenüberliegenden Zellen des Rechtecks der Kandidat 5 vorkommen muss. Das folgende Beispiel zeigt das Zeilen-Gitter der Zahl 5: 56-56-157-157 (in Zeile 1 und Zeile 5): die Zahl 5 kann daher überall außerhalb dieses Gitters in der Spalte 2 bzw. Spalte 5 gestrichen werden:
Erweiterung der 2*2-Gitter-Methode X-Wing auf 3*3- bzw. 4*4-Gitter (mehr ist nicht notwendig, da zu einem höheren Gitter auch immer ein entsprechend kleineres gehört - ähnlich wie bei den N-Tupeln). Ein großer Vorteil dieser Gitter liegt darin, dass oft sehr viele Kandidaten gestrichen werden können.
Beispiel eines 3*3-Einzelzahl-Gitters (Swordfish):
In den drei Spalten 2, 7 und 8 ist der Kandidat 8 nur in den drei Zeilen 1, 5 und 7 vorhanden. Daher muss in jeder dieser Zeilen die 8 in einer der erwähnten Spalten vorkommen, kann also aus den anderen Spalten dieser drei Zeilen gestrichen werden. Ohne der 8 in den Zellen Nr. 3 (Zeile 1, Spalte 7) und Nr. 7 (Zeile 5, Spalte 8) hätte man eine (geschlossene) 6er-Einzelzahl-Kette (Nr. 1, 2, 4, 5, 8, 6).
Beispiel einer Einzelzahl-Kette (Länge 6):
Hier untersucht man z.B. die Zahl 2: Man findet die 2 genau zwei Mal in Zeile 1 (2389-28), in Spalte 5 oder in Box MM (27-27) und in Spalte 7 (24-24), und in Box OR (28-24). Startet man zum Beispiel mit dem Doppel 27-27 in Spalte 5, kann man dieses mit dem zweiten Spaltendoppel (24-24) über Zeile 4 verbinden (die dritte 2 in dieser Zeile stört bei der Verknüpfung von starken Verbindungen nicht). Das Zeilendoppel kann man als letzten Teil der Kette in der rechten oberen Box anschließen (die starke Verbindung 28-24 ist hierbei keine Notwendigkeit) und erhält somit die Kette: (6:5)27 - (4:5)27 - (4:7)24 - (3:7)24 - (1:9)28 - (1:1)2389.
Die Kette kann natürlich auch andersherum geschrieben werde: (1:1)2389 - (1:9)28 - (3:7)24 - (4:7)24 - (4:5)27 - (6:5)27.
Nun gilt: In Zeile 6/Spalte 1 kann die Zahl 2 nicht stehen, denn entweder liegt wegen der gefundenen Kette die 2 in Zeile 6/Spalte 5 (Anfang der Kette) oder in Zeile 1/Spalte 1 (Ende der Kette). D.h.: Ist die 2 in Zeile 6/Spalte 5, ist alles klar; ist die 2 aber nicht in Zeile 6/Spalte 5, muss sie in Zeile 4/Spalte 5 sein (da 27-27 eine sogenannte starke Verbindung ist), kann somit nicht in Zeile 4/Spalte 7 sein, muss also in Zeile 3/Spalte 7 sein (starke Verbindung 24-24), also nicht in Zeile 1/Spalte 9, und muss daher in Zeile 1/Spalte 1 (starke Verbindung 2389-28) sein. Damit erhält man:
Beispiel einer Einzelzahl-Widerspruchs-Kette (Typ 1):
Hier findet man sogar 12 (!) Einzelzahl-Widerspruchs-Ketten mit der Zahl 3 und der Länge 3: Zum Beispiel: (hier rot markiert) (6:5)3 - (5:6)[3] - (5:7)3 und auch (6:5)3 - (1:5)[3] - (3:6)3. Bei der ersten Kette gibt es in Zeile 1 keine Möglichkeit für eine 3, da in (6:5) und (5:7) eine 3 steht; bei der zweiten Kette kann in Spalte 9 keine 3 stehen. Andere Beispiele sind z.B. auch (5:7)3 - (5:6)[3] - (3:6)3 oder (hier grün markiert) (6:9)3 - (3:9)[3] - (3:6)3 mit dem Widerspruch "Keine Möglichkeit für eine 3 in Box 2#2 (MM)".
Beispiel einer Einzelzahl-Widerspruchs-Kette (Typ 2XO):
Startet man hier in der 3. Zeile und 2. Spalte mit der Zahl 4, kann an keiner anderen Stelle dieser Zeile eine 4 stehen, also auch nicht in Spalte 6. Diese Spalte hat aber eine starke Verbindung, so dass die 4 in Zeile 5 dieser Spalte stehen muss. Damit ist an keiner Stelle der Box 2#1 (ML) eine 4 möglich, was ein Widerspruch zu der Annahme einer 4 in (3:2) ist. Weg: (3:2)4 - (3:6)[4] - (5:6)4. Der umgekehrte Weg wie bei Typ 1 ist hier nicht möglich.
Beispiele mit vielen Einzelzahl-Gittern/Einzelzahl-Ketten/Einzelzahl-Widerspruchs-Ketten
- Ausschluss-Ketten: Ausschluss-Rechtecke (Unique Rectangles) und Ausschluss-Schleifen (Unique Loops):
- Übersicht Ausschluss-Rechtecke (Unique Rectangles): Das sind 4 Zellen, die in zwei verschiedenen Zeilen, zwei verschiedenen Spalten und zwei (!) verschiedenen Boxen liegen und in allen diesen Zellen neben anderen Kandidaten zwei gleiche Kandidaten haben. Wegen der eindeutigen Lösbarkeit eines Sudokus kann man dann bestimmte Kandidaten ausschließen; dabei werden (hier) 8 Typen mit einigen Untertypen unterschieden - daher wird hier die eindeutige Lösbarkeit vorausgesetzt und man sollte dann aber am Ende der Rechnung die Eindeutigkeit überprüfen ("Teste Loesbarkeit vom Original aus").
Liegen in 4 Zellen, die in zwei verschiedenen Zeilen, zwei verschiedenen Spalten und zwei verschiedenen Boxen liegen, nur genau 2 Zahlen (je zwei Mal), kann man diese Zahlen in diesen vier Zellen vertauschen und erhält ein zweites Sudoku, das sich nur in diesen Zellen unterscheidet. Ein gutes Sudoku ist daher immer so konstruiert, dass - in diesem Fall - mindestens eine dieser vier Zellen vorgegeben ist, wodurch es eindeutig lösbar wird. Beispiel mit den vertauschbaren Zahlen 6 und 9:
| 2 |
6 |
8 |
|
1 |
9 |
3 |
|
4 |
5 |
7 |
| 3 |
9 |
7 |
|
5 |
6 |
4 |
|
8 |
1 |
2 |
| 5 |
4 |
1 |
|
7 |
2 |
8 |
|
9 |
3 |
6 |
|
| ... |
... |
... |
|
... |
... |
... |
|
... |
... |
... |
|
|
| 2 |
9 |
8 |
|
1 |
6 |
3 |
|
4 |
5 |
7 |
| 3 |
6 |
7 |
|
5 |
9 |
4 |
|
8 |
1 |
2 |
| 5 |
4 |
1 |
|
7 |
2 |
8 |
|
9 |
3 |
6 |
|
| ... |
... |
... |
|
... |
... |
... |
|
... |
... |
... |
|
|
Das folgende Sudoku hat KEIN Ausschluss-Rechteck: Durch Vertauschen der 6 und 9 in den 4 Boxen entsteht kein Sudoku - das funktioniert nur bei 2 betroffenen Boxen:
| 9 |
7 |
3 |
|
6 |
4 |
5 |
|
1 |
2 |
8 |
| 5 |
4 |
1 |
|
7 |
2 |
8 |
|
9 |
3 |
6 |
| 2 |
6 |
8 |
|
1 |
9 |
3 |
|
4 |
5 |
7 |
|
| 3 |
9 |
7 |
|
5 |
6 |
4 |
|
8 |
1 |
2 |
| ... |
... |
... |
|
... |
... |
... |
|
... |
... |
... |
|
|
| 9 |
7 |
3 |
|
6 |
4 |
5 |
|
1 |
2 |
8 |
| 5 |
4 |
1 |
|
7 |
2 |
8 |
|
9 |
3 |
6 |
| 2 |
9 |
8 |
|
1 |
6 |
3 |
|
4 |
5 |
7 |
|
| 3 |
6 |
7 |
|
5 |
9 |
4 |
|
8 |
1 |
2 |
| ... |
... |
... |
|
... |
... |
... |
|
... |
... |
... |
|
|
WICHTIG: Da ein Sudoku eindeutig lösbar sein muss, sollte man, wenn die Eindeutigkeit unklar, ist am Ende der Rechnung - wie bei Trial&Error - die Eindeutigkeit überprüfen ("Teste Lösbarkeit vom Original aus").
Viele Beispiele mit ausführlichen Erklärungen findet man bei Bernhard Hobigers Webseite http://hodoku.sourceforge.net/de/tech_ur.php (die Typen 7 und 8 heißen dort Hidden Rectangles - Versteckte Rechtecke) und bei Rudi Lars' Webseite http://home.arcor.de/r.sudogu/r_tec/UniqueRectangle.html (wobei die Typen 7 und 8 dort Unique Rectangle VII [1/6] bis [6/6] genannt werden, Typ 7B wird nicht erwähnt), und auch bei Andrew Stuart's Webseite https://www.sudokuwiki.org/Unique_Rectangles und https://www.sudokuwiki.org/Hidden_Unique_Rectangles (der Typ 4A heißt dort Hidden Typ 2/2b); Stuart hat sogar eine Erweiterung auf ein 2 x 3 Pattern mit Tripeln statt Paaren beschrieben, siehe https://www.sudokuwiki.org/Extended_Unique_Rectangles.
Bewertung (Ausschluss-Rechtecke): 4 Punkte für die einfachen Typen 1, 2 und 5, und 5 Punkte für den einfachen Typ 3A (mit Quasi-2-Tupel - bei Typ 3 allgemein: 5, 8, 11, 14, 17, 20 - je nach der Länge des Quasi-N-Tupels), für die schwierigeren Typen (mit 1 Regel) 4A, 4B und 4C gibt es 3 Punkte mehr (also 7 Punkte), für die komplexeren Typen (mit 2 Regeln) 6, 7A, 7B, 7C, 8A, 8B und 8C gibt es 4 Punkte mehr (also 8 Punkte).
Achtung: Da das Ausdünnen die Eindeutigkeit eines Sudokus erfordert, sollte man diese im Zweifelsfall prüfen - das wird am Ende des Programms automatisch angeboten. Bei mehrdeutigen Sudokus wird eventuell eine angeblich eindeutige Lösung gefunden, obwohl es auch andere Lösungen gibt (es wurden schon über 1000 solcher Fälle gefunden).
Beispiel (dabei auch auf die hier nach dem Sudoku folgende Zeile klicken): Sudoku mit 3 Lösungen, davon zwei gleichartige an den Stellen (3:8 - 3:9 - 8:9 - 8:8): 000000089406009200000630000000000050000004000001720030010000008075000000032070060
Einer der gefundenen Ausdünnschritte ist:
Ausschluss-Rechteck Typ 4C für (3:8 - 3:9 - 8:9 - 8:8)14 gefunden: Wegen Kandidat 4 alleine in Spalte 8 ist Kandidat 4 in nicht betrachteter Zelle mit Zusatzkandidaten streichbar
Unter der falschen Annahme, dass das Sudoku eindeutig lösbar ist, werden in einem Ausschluss-Rechteck Kandidaten eliminiert, die aber zu zwei anderen Lösungen gehören mit der Zahl 5 (statt 4) in Zeile 1 und Spalte 4, aber den vertauschbaren Zahlen 1 - 4 - 1 - 4 und 4 - 1 - 4 - 1 im Rechteck 3:8 - 3:9 - 8:9 - 8:8.
Weiteres Beispiel: Das Sudoku hat 127 Lösungen, ist aber mit 4 einfachen Ausschluss-Rechtecken "angeblich" lösbar: 000000003007000009063007000000026800400000000000009200000240010180000040070100060
Es ist schon erstaunlich, dass genau ein Sudoku gelöst wird, aber über 100 andere Lösungen auch noch existieren!
- Ausführliche Typen-Übersicht, geordnet nach Anzahl der Paare (Abkürzungen: HK = Hauptkandidat, ZK = Zusatzkandidat, Z = Zeile, S = Spalte) mit 8 Haupttypen bzw. 20 (23 bei Schleifen) Untertypen:
| Typ | Häufigkeit | ZK | Analyse | Streichbar | Ort |
| 1 Zelle mit 1 bis N ZK bzw. 2 oder mehr Zellen mit identischem ZK |
| Typ 1 | 9-10 % | 1 bis N | ZK in 1 Zelle | Beide HK | ZK |
| Typ 2 | 4-6 % | 1 gleicher | in 2 Zellen | ZK | Alle von ZK aus sichtbaren Zellen |
| Typ 5A | < 0.01 % | 1 gleicher | in 2 Zellen
(Paare diagonal) | ZK | Alle von ZK aus sichtbaren Zellen |
| Typ 5B | 0.05 % | 1 gleicher | in 3 Zellen | ZK | Alle von ZK aus sichtbaren Zellen |
| Typ 5C (ab 6er-Ausschluss-Schleifen) | < 0.01 % | 1 gleicher | in 4 Zellen | ZK | Alle von ZK aus sichtbaren Zellen |
| Typ 5D (ab 8er-Ausschluss-Schleifen) | < 0.01 % | 1 gleicher | in 5 Zellen | ZK | Alle von ZK aus sichtbaren Zellen |
| Typ 5E (ab 10er-Ausschluss-Schleifen) | < 0.0001 % | 1 gleicher | in 6 Zellen | ZK | Alle von ZK aus sichtbaren Zellen |
| Quasi-N-Tupel |
| Typ 3A | < 1 % | 2 | Quasi-2-Tupel | Quasi-2-Tupel-Zahlen | Alle von ZK + N-Tupel aus sichtbaren Zellen |
| Typ 3B | < 1 % | 2 bis 3 | Quasi-3-Tupel | Quasi-3-Tupel-Zahlen | Alle von ZK + N-Tupel aus sichtbaren Zellen |
| Typ 3C | < 1 % | 2 bis 4 | Quasi-4-Tupel | Quasi-4-Tupel-Zahlen | Alle von ZK + N-Tupel aus sichtbaren Zellen |
| Typ 3D | < 1 % | 2 bis 5 | Quasi-5-Tupel | Quasi-5-Tupel-Zahlen | Alle von ZK + N-Tupel aus sichtbaren Zellen |
| Typ 3E | < 1 % | 2 bis 6 | Quasi-6-Tupel | Quasi-6-Tupel-Zahlen | Alle von ZK + N-Tupel aus sichtbaren Zellen |
| Typ 3F | < 1 % | 2 bis 7 | Quasi-7-Tupel | Quasi-7-Tupel-Zahlen | Alle von ZK + N-Tupel aus sichtbaren Zellen |
| Mit 1 HK-Regel (Ein HK nur in den beiden AR-Zellen einer Zeile oder Spalte bzw. in allen 4 AR-Zellen) |
| Typ 4A | 21-25 % | 1 bis N | HK in HK+ZK-Zellen | Anderer HK | AR-Zelle mit nicht betrachtetem ZK |
| Typ 4B | 10-13 % | 1 bis N | HK in ZK+ZK-Zellen | Anderer HK | 2 AR-Zellen mit ZK |
| Typ 4C | 10-11 % | 1 bis N | HK in HK+ZK-Zellen
(Paare diagonal) | HK | AR-Zelle mit nicht betrachtetem ZK |
| Mit 2 HK-Regeln (Ein HK nur in den beiden AR-Zellen einer Zeile oder Spalte, anderer HK nur in beiden AR-Zellen anderer Zeile oder Spalte) |
| Typ 6 | 1-2 % | 1 bis N | HK in Z/S, HK in Z/S
(Paare diagonal) | HK | 2 AR-Zellen mit ZK |
| Typ 7A | 5-6 % | 1 bis N | HK in Z/S, HK in S/Z | Anderer HK | Zelle gegenüber Paar-Zelle |
| Typ 7B (NEU) | 16-18 % | 1 bis N | HK in Z/S, HK in Z/S | Anderer HK | Zelle gegenüber Paar-Zelle |
| Typ 7C | 3-4 % | 1 bis N | HK in Z/S, HK in S/Z
(Paare diagonal) | Anderer HK | Betrachtete Paar-Zelle |
| Typ 8A | 10-11 % | 1 bis N | HK1 in Z/S, HK2 in Z/S | HK | Neben Paar-Zelle liegende Zelle |
| Typ 8B | 2-3 % | 1 bis N | HK1 in Z/S, HK2 in S/Z | HK | Nicht betrachtete Zelle |
| Typ 8C | 0.5-1 % | 1 bis N | HK1 in Z/S, HK2 in S/Z | ZK | Zelle gegenüber Paar-Zelle |
Die Prozentangaben sind ungefähre Werte aus Rechnungen mit 420000 Sudokus (mit Ausdünnen), von denen in etwa 35 % der Sudokus Ausschluss-Rechtecke gefunden wurden (Option 2001 und 1012). Die Abarbeitungsreihenfolge ist dabei Typ 1, 2, 5A-B, 3A-3F, 4B, 4A, 6, 7C, 4C, 7B, 7A, 8A, 8B, 8C, so dass alle Typen auch auftreten können. Bei einer anderen Reihenfolge treten insbesondere die Typen 4B, 6, 7B und 7C im nicht-synchronen Fall selten auf.
Bemerkung: Mit Paar-Zelle ist jeweils eine Zelle des Ausschluss-Rechtecks bezeichnet, die nur aus den beiden Hauptkandidaten (die zwei Kandidaten, die in allen 4 Zellen vorkommen) des Ausschluss-Rechtecks besteht.
Bemerkung: Ändert man die Reihenfolge der Ausdünnschritte, kann ein vorher lösbares Sudoku eventuell nicht mehr gelöst werden. Oft helfen dann aber die Quasi-Ausschluss-Rechtecke und -Schleifen, wobei alle Fälle der Ausschluss-Rechtecke und die der 6er-Ausschluss-Schleifen programmiert wurden. Interessanterweise wurde das Phänomen aber nie bei Goldenen und Einzelzahl-Ketten beobachtet (also keine eventuell notwendigen Quasi-Goldenen und Quasi-Einzelzahl-Ketten).
- Ausschluss-Rechtecke (Unique Rectangles):
Typ 1: Ausschluss-Rechteck vom einfachsten und relativ häufigem Typ (etwa 9-10 %): Es gibt drei Zellen mit drei gleichen Paaren, und in der vierten Zelle gibt es zusätzliche Kandidaten, von denen einer gültig sein muss - andernfalls wäre die eindeutige Lösbarkeit nicht gegeben. Beispiel:
Würde man die Zahl 1 in Zeile 3 und Spalte 5 streichen, hätte man ein Ausschluss-Rechteck: In allen vier betrachteten Zellen gibt es dann nur die Zahlen 2 und 5 als Kandidaten; dann wären prinzipiell zwei Lösungen möglich (2 - 5 - 2 - 5 und 5 - 2 - 5 - 2). Das ist aber ein Widerspruch zu der Voraussetzung, dass ein Sudoku eindeutig lösbar sein muss. Also muss in dieser Zelle die 1 stehen bzw. die Kandidaten 2 und 5 können gestrichen werden (falls mehrere zusätzliche Kandidaten vorliegen).
Typ 2: Ausschluss-Rechteck vom einfachen, jedoch wenig häufigen (außer bei Ausschluss-Schleifen) Typ: Es gibt zwei nicht-diagonale Zellen mit zwei gleichen Paaren, und in den anderen neben- oder übereinander liegenden Zellen gibt es einen zusätzlichen (gleichen) Kandidaten, der wegen der eindeutigen Lösbarkeit in einer der beiden Zellen gültig sein muss - aus den anderen, von diesen beiden Zellen aus sichtbaren Zellen kann dann dieser zusätzliche Kandidat gestrichen werden. Beispiel:
Würde man die Zahl 3 in Spalte 8 der Zeilen 2 und 3 streichen, hätte man ein Ausschluss-Rechteck: In allen vier betrachteten Zellen gibt es dann nur die Zahlen 4 und 7 als Kandidaten; dann wären prinzipiell zwei Lösungen möglich (4 - 7 - 4 - 7 und 7 - 4 - 7 - 4). Das ist aber ein Widerspruch zu der Voraussetzung, dass ein Sudoku eindeutig lösbar sein muss. Also muss in einer der erwähnten Zellen die Zahl 3 stehen - d.h. alle von diesen beiden Zellen aus sichtbaren Kandidaten 3 können gestrichen werden.
Typ 3A bis 3F: Ausschluss-Rechteck vom relativ einfachen und auch wenig häufigen Typ: Es gibt zwei Zellen mit zwei gleichen Paaren, und in den anderen neben- oder übereinander liegenden Zellen gibt es zusätzliche Kandidaten, die als Kandidaten einer Zelle aufgefasst werden können. Zusammen mit anderen Kandidaten der entsprechenden Zeile, Spalte oder Box können diese ein Quasi-N-Tupel bilden. 3A steht für ein Ausschluss-Rechteck mit einem Quasi-2-Tupel, usw. bis 3F für eines mit einem Quasi-7-Tupel. Beispiel des sehr einfachen Typs 3A mit einem 2-Tupel, dessen zwei Zahlen direkt ablesbar sind - es muss nur noch eine andere Zelle mit genau diesem Paar gefunden werden:
Hier liegen in Spalte 8 der Zeilen 1 und 3 die Zusatzkandidaten 1 und 7. Zusammen mit dem Rest 17 in der gleichen Box bilden sie das Quasi-2-Tupel 17. Da einer der Zusatzkandidaten gesetzt sein muss, können die von diesem N-Tupel aus sichtbaren Kandidaten der anderen Zellen somit gestrichen werden.
Typ 4A: Ausschluss-Rechteck vom häufigsten Typ (etwa 21-25 %): Es gibt wieder zwei Zellen in einer Zeile oder Spalte mit zwei gleichen Paaren, und in den anderen Zellen gibt es zusätzliche Kandidaten. Hier interessieren die Zusatzkandidaten nicht direkt - sie legen nur zwei der vier zu betrachteten Zellen des Ausschluss-Rechtecks fest. Jetzt wird eine Zeile oder Spalte mit beiden Zellen-Typen untersucht: Ist einer der Hauptkandidaten in einer Zeile oder Spalte mit einer Paar-Zelle und einer Zelle mit zusätzlichen Kandidaten nur in diesen beiden Zellen vorhanden, kann der andere Hauptkandidat aus der anderen Zelle mit zusätzlichen Kandidaten gestrichen werden. Beispiel:
Der Hauptkandidat 9 ist in Zeile 1 nur in den beiden Zellen des Ausschluss-Rechtecks vorhanden. Daher muss der andere Hauptkandidat 3 aus der Zelle in Zeile 2 und Spalte 4 gestrichen werden; denn wäre die 3 in dieser Zelle, müsste die 9 in der links davon stehenden Paar-Zelle sein, daher die 3 in der darüber stehenden Paar-Zelle und wegen der obigen Bedingung hätte die Zelle in Zeile 1 und Spalte 4 eine 9, was zu der nicht erlaubten Möglichkeit zweier Sudokus (mit 3 - 9 - 3 - 9 und damit auch 9 - 3 - 9 - 3) führen würde.
Typ 4B: Ausschluss-Rechteck ähnlich 4A, aber nicht so häufigem (10-13 %) Typ (dafür können aber immer 2 Kandidaten gestrichen werden): Es gibt zwei Zellen mit zwei gleichen Paaren, und in den anderen neben- oder übereinander liegenden Zellen gibt es zusätzliche Kandidaten. Ist einer der Hauptkandidaten in einer Zeile, Spalte oder Box nur in diesen beiden Zellen vorhanden (also rechtwinklig zum Typ 4A), kann der andere Kandidat aus diesen Zellen mit den Zusatzkandidaten gestrichen werden. Beispiel für Typ 4B:
Einer der beiden Hauptkandidaten dieser Zellen mit den Zusatzkandidaten, hier die 7, ist in Zeile 2 aber nur in den beiden Zellen des Ausschluss-Rechtecks vorhanden. Daher muss dieser Kandidat an einer der beiden Stellen auftreten - damit das Sudoku aber eindeutig lösbar sein soll, muss der andere Hauptkandidat, hier die 8, aus diesen Zellen (mit den Zusatzkandidaten) gestrichen werden.
Typ 4C: Ausschluss-Rechteck vom ähnlich häufigen Typ (etwa 10-11 %): Es gibt zwei diagonal gegenüberliegende Zellen mit nur den Kandidaten des Ausschluss-Rechtecks; in den anderen beiden Zellen gibt es zusätzliche Kandidaten. Ist einer der beiden Kandidaten nur in einer Zelle ohne zusätzliche Kandidaten und einer daneben bzw. darunter liegenden Zelle mit zusätzlichen Kandidaten vorhanden, so kann er aus der nicht betrachteten Zelle mit den zusätzlichen Kandidaten gestrichen werden. Beispiel:
Die Zahl 8 kommt in Zeile 1 (mit einer Paar-Zelle und eine Zelle mit zusätzlichen Kandidaten) nur in den Zellen des Ausschluss-Rechtecks vor. Dieser Kandidat muss also aus der anderen Zelle mit zusätzlichen Kandidaten in Zeile 2 und Spalte 5 gestrichen werden. Denn wenn die Zahl 8 dort wäre, müsste in der Zelle darüber die 4 stehen und damit in Zeile 1 und Spalte 2 die 8 und in der Zelle darunter die 4; dies widerspricht der Eindeutigkeit eines Sudokus.
Typ 5A bis 5B bzw. 5E: Ausschluss-Rechteck vom seltenen (außer bei Ausschluss-Schleifen) und dem Typ 2 sehr ähnlichen Typ, der aber unterschieden wird: Liegen sich die beiden Zellen mit den Zusatzkandidaten diagonal gegenüber, gilt die gleiche Folgerung: Aus allen Zellen, die von den beiden Zellen mit dem Zusatzkandidaten gesehen werden können, kann dieser gestrichen werden: das ist der Typ 5A der Ausschluss-Rechtecke, der bei den 138000 gerechneten Sudokus mit Ausdünnung in nur einem einzigen Fall und bei den Quasi-Ausschluss-Rechtecken dort nur 12 Mal gefunden wurde. Nur wenig häufiger ist der Typ 5B, bei dem drei Zellen den gleichen Zusatzkandidaten haben; hier kann der Zusatzkandidat aus allen Zellen gestrichen werden, die von diesen drei Zellen aus gesehen werden. Bei Ausschluss-Schleifen gibt es noch den Typ 5C, wenn vier Zellen den gleichen Zusatzkandidaten haben, ab den 10er-Ausschluss-Schleifen auch die Typen 5D und 5E, wenn fünf bzw. sechs Zellen den gleichen Zusatzkandidaten haben. Beispiel für Typ 5B:
Die Zahl 3 kommt nur in drei Zellen des Ausschluss-Rechtecks vor. Damit das Sudoku aber eindeutig lösbar sein soll, muss eine dieser Zellen die Zusatzzahl 3 enthalten. Daher kann man die Zahl 3 aus allen Zellen, hier der einen Zelle in Zeile 3 und Spalte 1, streichen.
Typ 6: Ausschluss-Rechteck vom sehr seltenen Typ (außer bei Quasi-Ausschluss-Rechtecken und Ausschluss-Schleifen), der ähnlich dem Typ 4C ist: Es gibt zwei diagonal gegenüber liegende Zellen mit nur den Kandidaten des Ausschluss-Rechtecks; in den anderen beiden Zellen gibt es zusätzliche Kandidaten. Ist ein Hauptkandidat nur in den 4 Zellen des Ausschluss-Rechtecks vorhanden, kann dieser (im Gegensatz zu Typ 4 also nicht der andere Hauptkandidat) aus den Zellen mit den Zusatzkandidaten gestrichen werden. Typ 6 entspricht dem Typ 4C zwei Mal angewendet. Tritt meistens nur in den Alternativ-Fällen ("ODER" bzw. "neben") auf. Beispiel:
Die Zahl 7 kommt nur in den 4 Zellen des Ausschluss-Rechtecks (Sudoku hier nicht ganz dargestellt) vor. Damit das Sudoku aber eindeutig lösbar sein soll, muss die 7 in den Zellen mit den Zusatzkandidaten gestrichen werden. Denn wäre die 7 an diesen Stellen gesetzt, müsste in den Paar-Zellen die Zahl 5 stehen; das wäre aber eine Situation 5 - 7 - 5 - 7 oder 7 - 5 - 7 - 5, was zu einem nicht-eindeutigen Sudoku führen würde.
Typ 7A: Ausschluss-Rechteck vom relativ häufigen Typ: Es gibt eine Zelle mit nur den Kandidaten des Ausschluss-Rechtecks; in den anderen drei Zellen gibt es zusätzliche Kandidaten (dieser Typ hat zwar nur eine Paar-Zelle wie die Typen 8, gehört aber auf Grund aller anderen Eigenschaften zu den Typen 7). Man betrachtet nun die Zeile und die Spalte durch die Zelle, die der Paar-Zelle diagonal gegenüber liegt: Taucht einer der Kandidaten in dieser Zeile und Spalte nur in den zum Ausschluss-Rechteck gehörenden Zellen auf, kann der andere Kandidat in der der Paar-Zelle gegenüber liegenden Zelle gestrichen werden. Beispiel:
Man betrachtet die Zeilen 1 und 3 und die Spalten 3 und 4: Die Paar-Zelle hat die Kandidaten 29; die diagonal gegenüber liegende Zelle in Zeile 3 und Spalte 4 hat die Kandidaten 289; die Zahl 2 kommt in Zeile 3 und auch in Spalte 4 (Sudoku hier nicht ganz dargestellt) nur in dem Ausschluss-Rechteck vor. Damit das Sudoku aber eindeutig lösbar sein soll, muss der andere Hauptkandidat, also die 9, dort (in Zeile 3 und Spalte 4) gestrichen werden.
Typ 7B (NEU): Ausschluss-Rechteck vom zweit-häufigsten Typ (etwa 16-18 %): Es gibt eine Zelle mit nur den Kandidaten des Ausschluss-Rechtecks; in den anderen drei Zellen gibt es zusätzliche Kandidaten (dieser Typ hat zwar nur eine Paar-Zelle wie die Typen 8, gehört aber auf Grund aller anderen Eigenschaften zu den Typen 7). Ist ein Hauptkandidat nur in den 4 Zellen des Ausschluss-Rechtecks vorhanden, kann der andere Kandidat in der der Paar-Zelle diagonal gegenüber liegenden Zelle gestrichen werden. Beispiel:
Die Paar-Zelle hat die Kandidaten 58; die diagonal gegenüber liegende Zelle in Zeile 4 und Spalte 1 hat die Kandidaten 158; die Zahl 8 kommt aber in Zeile 1 und auch in Zeile 4 nur in dem Ausschluss-Rechteck vor. Damit das Sudoku aber eindeutig lösbar sein soll, muss der andere Hauptkandidat, hier die 5, dort (also in Zeile 4 und Spalte 1) gestrichen werden.
Der Typ 7B ist dem Typ 7A sehr ähnlich, aber die Bedingungen sind unterschiedlich: Bei Typ 7A werden eine Zeile und eine Spalte untersucht, bei Typ 7B jeweils zwei Zeilen bzw. zwei Spalten.
Typ 7C: Ausschluss-Rechteck vom wenig häufigen Typ: Es gibt zwei diagonal gegenüberliegende Zellen mit nur den Kandidaten des Ausschluss-Rechtecks; in den anderen beiden Zellen gibt es zusätzliche Kandidaten. Man betrachtet nun die Zeile und die Spalte durch eine der beiden Paar-Zellen: Taucht einer der Kandidaten in dieser Zeile und Spalte nur in den zum Ausschluss-Rechteck gehörenden Zellen auf, kann der andere Kandidat in dieser Paar-Zelle gestrichen werden. Beispiel:
Die Zahl 5 kommt in Zeile 2 und in Spalte 7 (Sudoku hier nicht ganz dargestellt) nur in den Zellen des Ausschluss-Rechtecks vor. Der andere Hauptkandidat 2 muss aus dieser Zelle in Zeile 2 und Spalte 7 gestrichen werden. Denn wenn die Zahl 2 in dieser Zelle wäre, müsste in den Zellen mit Zusatzzahl die Zahl 5 stehen; dann wäre aber in der anderen Paar-Zelle die Zahl 2 und damit hätte man ein zweideutiges Sudoku mit den beiden Lösungen 2 - 5 - 2 - 5 und 5 - 2 - 5 - 2.
Der Typ 7C entspricht im Prinzip dem Typ 7A, bei dem das gleiche Ergebnis erreicht wird, wobei bei Typ 7C aber gleich eine Paar-Zelle eindeutig besetzt werden kann.
Typ 8A: Ausschluss-Rechteck vom relativ häufigen Typ (etwa 10-11 %): Es gibt nur eine Paar-Zelle, in den anderen drei Zellen gibt es zusätzliche Kandidaten. Es werden jeweils zwei Zeilen bzw. zwei Spalten betrachtet. Ist ein Hauptkandidat in einer Zeile bzw. Spalte nur in den Zellen des Ausschluss-Rechtecks vorhanden, und ist der andere Hauptkandidat in der anderen Zeile bzw. Spalte auch nur in den Zellen des Ausschluss-Rechtecks vorhanden, so kann der Hauptkandidat, der in der Zeile bzw. Spalte mit der Paar-Zelle betroffen war, aus der darunter/darüber bzw. rechts/links daneben liegenden Zelle mit den zusätzlichen Kandidaten gestrichen werden. Beispiel:
Die Zahl 5 kommt in Zeile 3 nur in den Zellen des Ausschluss-Rechtecks vor, die Zahl 4 kommt in Zeile 4 nur in den Zellen des Ausschluss-Rechtecks vor. Der Hauptkandidat 5, der in der Zeile mit der Paar-Zelle ist, muss aus der Zelle unterhalb der Paar-Zelle in Zeile 4 und Spalte 4 gestrichen werden. Die Argumentation ist ähnlich denen der vorhergehenden Beispiele.
Die Typen 8A bis 8C haben die Besonderheit, dass dazu beide Hauptkandidaten in bestimmten Zeilen und Spalten untersucht werden, ob sie nur in den Zellen des Ausschluss-Rechtecks auftreten. Daher werden sie hier von den Typen 7A bis 7C unterschieden, bei denen nur ein Hauptkandidat betrachtet wird.
Typ 8B: Ausschluss-Rechteck vom wenig häufigen Typ: Es gibt nur eine Paar-Zelle mit den Kandidaten des Ausschluss-Rechtecks; in den anderen drei Zellen gibt es zusätzliche Kandidaten. Betrachtet man eine Zeile bzw. Spalte, in der die Paar-Zelle vorkommt, und kommt einer der Hauptkandidaten nur in diesen beiden Zellen vor und der andere Hauptkandidat nur in der Spalte bzw. Zeile, die die gerade betrachtete Zelle mit Zusatzkandidaten enthält, so kann der erste Hauptkandidat aus der nicht betrachteten Zelle mit den zusätzlichen Kandidaten gestrichen werden. Beispiel:
Die Zahl 1 kommt in Spalte 2 (mit einer Paar-Zelle und einer Zelle mit zusätzlichen Kandidaten) nur in den Zellen des Ausschluss-Rechtecks vor (Sudoku hier nicht ganz dargestellt). Der zweite Hauptkandidat 4 kommt in der Zeile 1 nur in den beiden Zellen des Ausschluss-Rechtecks vor. Der erste Hauptkandidat 1 muss also aus der dritten Zelle mit zusätzlichen Kandidaten in Zeile 2 und Spalte 7 gestrichen werden. Denn hätte diese Zelle den Wert 1, wäre in der Paar-Zelle eine 4 und damit in der darüber liegenden Zelle eine 1 und daher auch in der Zelle in Zeile 1 und Spalte 7 eine 4; das ergäbe aber prinzipiell zwei Lösungen 1 - 4 - 1 - 4 und 4 - 1 - 4 - 1 vor, was nicht sein darf.
Typ 8C: Ausschluss-Rechteck vom seltenen Typ: Es gibt nur eine Paar-Zelle mit den Kandidaten des Ausschluss-Rechtecks; in den anderen drei Zellen gibt es zusätzliche Kandidaten. Man betrachtet die Zeilen und Spalten, in denen die Paar-Zelle nicht vorkommt: Kommt in einer Zeile bzw. Spalte einer der Hauptkandidaten nur in den beiden Zellen des Ausschluss-Rechtecks vor und der andere Hauptkandidat analog nur in der entsprechenden Spalte bzw. Zeile, so können die Zusatzkandidaten (!) der der Paar-Zelle gegenüberliegenden Zelle gestrichen werden. Beispiel:
Der eine Hauptkandidat 6 kommt in Zeile 1 (Zeile ohne Paar-Zelle) nur in den Zellen des Ausschluss-Rechtecks vor. Der zweite Hauptkandidat 2 kommt in der Spalte 6 (Spalte ohne Paar-Zelle) nur in den beiden Zellen des Ausschluss-Rechtecks vor (Sudoku hier nicht ganz dargestellt). Der Zusatzkandidat 4 in der Zelle in Zeile 1 und Spalte 6 muss gestrichen werden; denn wäre er dort, so müsste in der Zelle darunter (Zeile 2 und Spalte 6) die 2 stehen, in der Zelle in Zeile 1 und Spalte 7 die 6. Das geht aber nicht, weil dann in der Paar-Zelle kein Kandidat möglich ist. Interessanterweise geht der Beweis nicht über die Vermeidung von zwei Lösungen, sondern über einen Widerspruch bei der möglichen Setzung; insofern muss man den Typ 8C eigentlich als Pseudo-Ausschluss-Rechteck auffassen. Das Ergebnis dieser Streichungen führt aber direkt zu einem Ausschluss-Rechteck vom Typ 4C!
Bei 136000 gerechneten Sudokus traten bei der voll-synchronen Rechnung direkte Ausschluss-Rechtecke insgesamt fast 280000 Mal auf, Quasi-Ausschluss-Rechtecke etwa 18500 Mal; die 6er-Ausschluss-Schleifen inklusive der 6er-Quasi-Ausschluss-Schleifen wurden etwa 7600 Mal gefunden, die 8er-Ausschluss-Schleifen 680 Mal, 10er-Ausschluss-Schleifen etwa 30 Mal.
posteo.de, Homepage: