Sudoku Solver

Auflistung aller Einzelschritte inklusive genauer Erklärungen und Punkte-Bewertung - mit Einzelzahl-Ketten, Goldenen Ketten und Ausschluss-Ketten (-Rechtecken und -Schleifen); und mit offensichtlichen 2-Tupeln und mit Anzeigen aller Alternativen auch beim Ausdünnen

Stand: 3. Juni 2012   Vorheriger Stand der Software (Februar/März 2012)

Geben Sie die Ausgangszahlen ein (1..9)

Prinzipen zur Lösung von Sudokus

Die Zeilen und Spalten werden hier von oben links an mit 1 bis 9 durchnummeriert, die Boxen werden mit OL (oben links), OM (oben Mitte), OR (oben rechts), ML (Mitte links), MM (Mitte Mitte), ..., bis UR (unten rechts) bezeichnet. Die benutzten Lösungsverfahren werden oft kurz mit mit A bis F bezeichnet, die zusätzliche Ziffer danach bezeichnet eine Untergruppe, dabei steht z.B. 1 für Zeile oder 3 für Box.

Dieses Programm benutzt 6 Lösungsmethoden mit verschiedener Punkte-Gewichtung, und ebenfalls 6 Gruppen von Analysemethoden für die Ausdünnung (ebenfalls mit unterschiedlichen Punkten gewichtet). Dabei wird beim Ausdünnen im nicht-synchronen Verfahren nach einem Treffer immer wieder bei der einfachsten Methode begonnen. Im synchronen Fall werden alle möglichen Treffer gesucht und dargestellt, was den Vorteil hat, dass man alle Möglichkeiten auf einmal sieht und auch erkennt, wie viele es davon gibt (wobei es bei sehr wenigen Treffern Extra-Punkte gibt); allerdings liegt die Punkte-Bewertung im synchronen Fall oft um einiges höher als im nicht-synchronen Fall, weil viele der gefundenen Ausdünnschritte eventuell gar nicht notwendig sind.

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, muss man für jede Zelle alle Zahlen aufschreiben, 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 so lange auszudünnen, also zu verkürzen, bis man zu einer eindeutigen Lösung für eine Zelle kommt (Methoden E und F). Dieses Ausdünnen (Kandidaten-Reduzierung) wird hier mit den wichtigsten 6 Methoden versucht, die weiter unten erklärt werden.

Es gibt noch vielleicht 30 bis 40 weitere Ausdünn-Methoden, die aber im Allgemeinen wenig zusätzliche Lösungen bringen und auch oft ziemlich kompliziert sind (z.B. Long String Kite oder 3D-Medusa) bzw. nahe einem Trial&Error-Verfahren liegen (Almost Locked Sets Chain, Forcing Chain, Forcing Net). Alle Sudokus können mit den hier programmierten (und wohl wichtigsten) Verfahren - die eigentlich auch gut nachvollziehbar und erlernbar sind - nicht gelöst werden, aber das ist sowieso nur etwas für Spezialisten. Dieses Programm soll nicht ein Sudoku einfach lösen, sondern alle Lösungsschritte zum Nachvollziehen aufzeigen.

Bemerkungen zur Bewertung: 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 1 oder 2 oder 3 Möglichkeiten gibt: Das wird dann mit Extra-Punkten bewertet. Gibt es nur genau einen (mit diesem Programm gefundenen) Schritt, sind das 20 Extra-Punkte, bei zwei Schritten 10 und bei drei Schritten 5 Extra-Punkte. Beispiele für sehr schwierige Sudokus mit vielen Extra-Punkten findet man am Ende diese Seite unter "Sehr schwierige Sudokus".

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 (bei N-Tupeln kann ein Tripel sowohl aus Zellen mit Paaren als auch Trios bestehen).

Programm-Neuigkeiten

• Nach längeren Rechnungen mit den 120000 vorhandenen nicht-trivialen Sudokus wurde nach einigen statistischen Untersuchungen (über die Häufigkeit der verschiedenen Ausdünnmethoden mit unterschiedlichen Optionen) die Reihenfolge und die Gruppenzuordnung bei den synchronen Methoden geändert (zum Beispiel wurden 10er-Einzelzahl-Ketten als wirkender Ausdünnschritt nie beobachtet). Außerdem wurde die Übergabe der Sudokus und deren Reste, wenn das Sudoku nicht direkt gelöst werden kann, verbessert. Zuletzt wurden auch 6er-Quasi-Ausschluss-Schleifen programmiert, auch um zu zeigen, dass es diese geben kann (Mai/Juni 2012).

Liste der Häufigkeiten der aufgetretenen Ausdünnmethoden bei den 85574 schwierigeren Sudokus beim nicht-synchronen Verfahren (in Klammern beim synchronen Verfahren) - diese 20 häufigsten Methoden waren bei 98.6 % der Ausdünnschritte aufgetreten - diese solte man also beherrschen:-).
Hierbei muss natürlich berücksichtigt werden, dass beim nicht-synchronen Verfahren eine bestimmte Reihenfolge (2-Tupel, 3-Tupel, Zeilen-/Spalten-Tests, Box-Tests, 3er-Goldene Ketten, 4er-Einzelzahl-Ketten, 4er-Goldene Ketten, 5er-Goldene Ketten, 6er-Einzelzahl-Ketten, 6er-Goldene Ketten, Ausschluss-Rechtecke Typ 1, Typ 2, Typ 3, Typ 4A, Typ 4B, 4-Tupel, 5-Tupel, 7er-Goldene Ketten, 8er-Einzelzahl-Ketten, 8er-Goldene Ketten, usw.) eingehalten wird, weswegen die Zahlen beim synchronen Verfahren etwas anders ausfallen:

1.  137629  (202237) Zeilen-/Spalten-Tests
2.  132991  (105136) 2-Tupel
3.    88768  (503708) 4er-Einzelzahl-Ketten
4.    58036    (83028) 3-Tupel
5.    45433    (94619) 3er-Goldene Ketten
6.    39695  (189050) 4er-Goldene Ketten
7.    35611  (208952) Box-Tests
8.    27575  (181527) 5er-Goldene Ketten
9.    14655  (182539) 6er-Goldene Ketten
10.    10431  (180788) 6er-Einzelzahl-Ketten
11.      7451    (61588) Ausschluss-Rechtecke Typ 4B
12.      6011    (52481) 4-Tupel
13.      5701  (136437) 7er-Goldene Ketten
14.      4821    (12909) Ausschluss-Rechtecke Typ 1
15.      3173    (33958) Ausschluss-Rechtecke Typ 7B
16.      3061    (21045) Ausschluss-Rechtecke Typ 4A
17.      2801    (12066) Ausschluss-Rechtecke Typ 3
18.      1921    (94727) 8er-Goldene Ketten
19.      1471      (5115) Ausschluss-Rechtecke Typ 2
20.      1323    (13709) Ausschluss-Rechtecke Typ 7G
• Nach einer Verbesserung des Programmteils für die Ausschluss-Schleifen, die dadurch mehr Treffer fanden und schneller wurden, wurde nun auch nach 10er-, 12er-, 14er- und 16er-Ausschluss-Schleifen gesucht - und tatsächlich über 130 Sudokus gefunden! Allerdings ist der Rechenaufwand dadurch etwas höher, weswegen diese Methode nur bei der "allerweitestgehenden" Option angeboten wird; da alle diese Sudokus auch ohne diesen langen Ketten gerechnet werden können, sind sie rein akademischer Natur. Bei den vorhandenen 85574 Sudokus, die nur mit echten Ausdünnschritten lösbar sind (33534 Sudokus waren mit den offensichtlichen Zeilen-/Spalten-Tests und offensichtlichen 2-Tupeln lösbar), waren bei der synchronen Methode 411000 Zeilen-/Spalten-/Box-Tests, 272000 N-Tupel, 723000 Einzelzahl_Ketten, 1003000 Goldene Ketten (also die absolut häufigste Methode) und 283000 Ausschluss-Ketten (davon 258000 Ausschluss-Rechtecke) dabei - ermittelt in 4 1/2 Tagen Rechenzeit (April/Mai 2012).
• Die Bestimmung der 2- und 3-Tupel wurde an den Anfang der Ausdünnschritte gesetzt, weil diese einfacher zu sehen sind und damit auch unnötige Zeilen-/Spalten-Test- bzw. Box-Test-Aussagen erspart werden. Zusätzlich wurden die Ketten in 4 Gruppen je nach ihrer Länge aufgeteilt, wodurch es möglich wurde, die Berechnung der Reihenfolge der Schwierigkeit anzupassen (Idee nach Edgar Kiefhaber). Die Optionen wurden neu definiert und verfeinert: Um die Bewertung der Schwierigkeit eines Sudokus mit einbeziehen zu können, werden bei der optionalen pseudo-synchronen Version bis zu 4 Ausdünnschritte gesucht, aber nur der erste Schritt wird angezeigt und eingesetzt; dadurch können Extra-Punkte vergeben werden (dies ist dadurch aber einiges aufwändiger). Bei den echten synchronen Methoden werden - optional - nur noch die Ausdünnschritte gesucht, die einer bestimmten Schwierigkeit zugeordnet werden können, falls das möglich ist - andernfalls werden die der nächsthöheren Schwierigkeitsstufe (in nun insgesamt 5 Stufen) versucht. Außerdem kann man festlegen, ob man keine, einfache (also kurze) oder komplexe (also alle) offensichtliche Zeilen-/Spalten-Tests und 2-Tupel berechnet haben will, ob man keine oder alle Alternativen angezeigt haben will und ob die Ausdünnschritte ohne oder mit Kandidaten-Angabe angezeigt werden sollen. Weiterhin kann nun das eingegebene Sudoku mit anderen Optionen und/oder veränderten Zahlen noch einmal gerechnet werden - dazu gibt es am Ende der Lösung einen entsprechenden Link (Februar/März 2012).
• Neben mehreren Verbesserungen, Korrekturen und Erweiterungen (insbesondere bei den offensichtlichen 2-Tupeln und den Quasi-Ausschluss-Rechtecken - dort auch bei der Darstellung) wurde auch die Auto-Tab-Möglichkeit eingebaut, wodurch das explizite Weitergehen zum nachfolgenden Feld entfällt. Insgesamt konnten nun fast 994000 einfache Sudokus und über 119000 komplexe Sudokus gelöst werden; nur noch 101500 Sudokus können - aus der vorliegenden Sudoku-Liste - nicht berechnet werden (Januar/Februar 2012).
• Die 6 Untertypen bei den Ausschluss-Rechtecken Typ 7 (7B bis 7G) laut http://home.arcor.de/r.sudogu/r_tec/UniqueRectangle.html wurden eingebaut. Die Programmierung der Quasi-Ausschluss-Rechtecke wurde erweitert; dabei wurden auch die bisher getrennt behandelten Vermeidbaren Ausschluss-Rechtecke mit einbezogen. Insgesamt werden nun mehr Quasi-Ausschluss-Rechtecke gefunden als vorher (insbesondere die drei im nachfolgenden Punkt erwähnten Sudokus) - und dabei auch etwas schneller. N-Tupel und der Typ 3 mit den Quasi-N-Tupeln wurde allgemein verbessert. Die offensichtlichen Zeilen-/Spalten-Tests (Methode C) wurden verbessert. Außerdem wurden Fehler bei der Bewertungs-Berechnung korrigiert (Oktober/November 2011).
• Das Programm wurde so umgestellt, dass zu einem gegebenen Sudoku nun auch alle gleichzeitig auffindbaren Ausdünnschritte ermittelt werden (durch Radio-Button aber abwählbar). Damit ist man unabhängig von einer bestimmten Reihenfolge und sieht gleichzeitig auch, wie viele verschiedene Ausdünnschritte es gibt, um bestimmte Kandidaten streichen zu können; das erlaubt zusätzlich auch eine bessere Analyse, welche Arten von Ausdünnschritten wie häufig benutzt werden. Die Punkte-Bewertung ist dann aber etwas anders, da sie pro gestrichenem Kandidaten und nicht pro Ausdünn-Methode gerechnet wird.

  Der Vorteil der synchronen Berechnung liegt auch darin, dass man die Schwierigkeit eines Sudokus auch daran erkennen kann, dass an einer bestimmten Stelle oft nur ein einziger oder sehr wenige Einsetzschritte (Lösungsmethoden A bis D) bzw. nur ein einziger oder sehr wenige Ausdünnschritte gefunden werden - was durch bis zu 20 Extra-Punkte belohnt wird. Beispiele:
  Mit 12 Fällen - ohne Ausdünnen: 000000000000001002034000050000006300005000040200017000000800090100050000600000000
  Mit 10 Fällen - ohne Ausdünnen, dabei 1 Mal 20 Punkte beim Einsetzen: 000000089050780000080003004030805600001000000070034200000200050002067000000000300
  Mit 6+3 Fällen - dabei 3 Mal 20 Punkte beim Einsetzen und 1 Mal beim Ausdünnen: 000470000080020005007006900042700000010090070000000830209600100800040060000052000
  Mit 4 Fällen - dabei 2 Mal 20 Punkte beim Ausdünnen: 000000000000001002003040050000000006000000207005030000000087090020900000160000000

  Da alle gleichzeitig gefundenen Ausdünnschritte in einer einzigen Sudoku-Tabelle dargestellt werden, musste auf die direkte Einzelinformationen verzichtet werden; diese bekommt man aber genauestens dargestellt, wenn man auf den Methoden-Text klickt (als Link hier nicht unterstrichen, da sonst alles unterstrichen und unlesbar geworden wäre). Es kann durch Radio-Buttons vorgegeben werden, ob man ohne oder mit offensichtlichen Zeilen-/Spalten-Tests und 2-Tupeln, ohne oder mit synchroner Ausdünnschritt-Bestimmung, und ohne oder mit langen Einzelzahl- (ohne: max. Länge 12), Goldenen (ohne: max. Länge 13), Ausschluss-Ketten (ohne: max. Länge 6) rechnen will - die kurzen Ketten reichen zur Lösung im Allgemeinen aus und verringern aber die Rechenzeit erheblich (August 2011).

• In etwa 12 Tagen wurden etwa 113700 nicht-triviale Sudokus (mit im Allgemeinen 17 bzw. 22-36 Zahlen) nach den aktuellen synchronen Ausdünn-Methoden und mit langen Ketten berechnet und statistisch analysiert (26 Millionen Zeilen Gesamtausgabe). Einige Ergebnisse (Juli 2011):
  
  • Etwa die Hälfte (49%) der Gesamtrechenzeit entfiel auf die 8er-Ausschluss-Schleifen, 28% auf die Goldenen Ketten, 11% auf die 6er-Ausschluss-Schleifen und 7.5% auf die Einzelzahl-Ketten.
  • Die dazu gehörenden gefundenen Ausdünnschritte lagen aber in einem ganz anderen Verhältnis: 207 Sudokus mit 352 8er-Ausschluss-Schleifen (0.01%), 71500 Sudokus mit 1423000 Goldenen Ketten (37%), 2650 Sudokus mit 5910 6er-Ausschluss-Schleifen (0.15%) und 72300 Sudokus mit 789000 Einzelzahl-Ketten (20.5%) - bei insgesamt 3840000 Ausdünnschritten, bei denen 2298000 Kandidaten gestrichen werden konnten.
  • Aus den geringen Anzahlen der 6er- und 8er-Ausschluss-Schleifen kann man abschätzen, dass es bei diesen 113700 Sudokus vielleicht 15 10er-Ausschluss-Schleifen geben könnte. D.h., ob längere als 6er-Ausschluss-Schleifen sich lohnen, ist fraglich. Denn ob die längeren Ketten auch für eine Lösung gebraucht werden, ist eine andere Frage: Alle hier berechneten Sudokus mit 8er-Ausschluss-Schleifen konnten auch ohne diese gelöst werden, während die 6er-Ausschluss-Schleifen zur Lösung von etwa 600 Sudokus notwendig waren!
  • Erstaunlicherweise sind die Goldenen Ketten die häufigsten Ausdünnschritte, danach die Einzelzahl-Ketten, dann die Zeilen-/Spalten-Tests und Box-Tests mit jeweils etwa 8-9% Anzahl-Anteil und N-Tupel mit etwa 20% Anzahl-Anteil (und weniger als 1% Rechenzeit-Anteil), und auf die Ausschluss-Ketten entfielen 5.5% Anzahl-Anteil.
  • Bei den etwa 80000 Sudokus. die nur mit Ausdünnung gelöst werden konnten, traten die Zeilen-/Spalten-Tests, Box-Tests, N-Tupel und Ausschluss-Ketten bei etwa 75% aller Sudokus auf; die Einzelzahl-Ketten und Goldenen Ketten traten bei etwa 90% aller dieser Sudokus auf.
  • Bei den N-Tupeln konnten im Durchschnitt 3.3 Kandidaten gestrichen werden, bei den Zeilen-/Spalten- und Box-Tests etwa 1.7 Kandidaten, und sonst etwa 1.4 Kandidaten.
  • Es wurde ein Sudoku mit zwei Einzelzahl-Ketten der Länge 16 und zwei Sudokus mit fünf Goldene Ketten der Länge 19 und 14 Sudokus mit 56 Goldenen Ketten der Länge 18 gefunden (Beispiele weiter unten).
  • Bei den Lösungsmethoden war beim synchronen Bestimmen (bei insgesamt 13306000 Fällen, die dann zu 6432000 Zahlen führten) die A-Methode mit 32% sehr häufig, die B-Methode trat nur in 7% der Fälle auf, die C-Methode (offensichtliche Zeilen-/Spalten-Tests) in 6%, die D-Methoden (offensichtliche 2-Tupel) führten sogar zu 10% der Fälle; die zu A und B analogen Methoden E und F traten (nach dem Ausdünnen) in ähnlicher Häufigkeit in etwa 34% bzw. 11% der Fälle auf.
• Die Ausschluss-Verfahren wurden überarbeitet und erweitert; damit konnten weitere etwa 3000 der bisher nicht lösbaren Sudokus gelöst werden. Außerdem werden nun alle Ergebnisse eines Sudoku-Ausdünnschrittes aufgeführt, die gleichzeitig gefunden werden können - dabei werden ähnliche Einzelzahl- und Goldene Ketten aber nicht gewertet, wenn sie bei gleichen Anfangs- und Endpunkten für die gleiche Zahl gleich lang oder länger sind (Juni 2011). Es gibt mehrere Sudokus mit weit über 20 verschiedenen Ausdünnschritten, um nur einen Kandidaten zu streichen - zum Beispiel bei:
  Mit 32 Fällen für Kandidat 6 in Zeile 8 und Spalte 8: 020400000006000307000000015094010000007208000800003004300005102000090000070800000

  Bei den Standard-Methoden A bis D gibt es oft 4 und mehr Methoden (theoretisch maximal 12), die zur Setzung einer Zahl führen, zum Beispiel bei:
  Mit 8 Methoden für Zahl 7 in Zeile 1 und Spalte 9: 280030050000076800000000000000000680090008045540090030000005000004002006050003124

• Das Programm wurde in größerem Maße umgestellt: Es wurde verschiedene Methoden (D) programmiert, die darauf beruhen, dass man oft 2-Tupel (zwei Paare) direkt sieht, ohne dass man alle Kandidaten explizit anschreiben muss. Das betrifft sowohl das Auffinden einer Zahl an einer eindeutigen Stelle als auch als einzige Zahl an einer bestimmten Stelle. Außerdem werden nun alle Ergebnisse eines Sudoku-Standes aufgeführt, die gleichzeitig gefunden werden können. Darüber hinaus wurden auch die wichtigsten Fälle der Ausschluss-Schleifen (Verallgemeinerung der Ausschluss-Rechtecke auf 6 und 8 Zellen) programmiert (April/Mai 2011).
• Die Aussagen der bisherigen B-Methode (offensichtliche Zeilen-/Spalten-Tests, jetzt umbenannt in C-Methode) wurde stark verbessert (in den meisten Fällen werden jetzt nur noch die zur Lösung notwendigen Begründungen angezeigt) und dazu auch die Reihenfolge der ersten Methoden geändert: Zuerst A3, dann die bisherige B-Methoden (jetzt mit 2 Punkten pro aussagefähigen Begründungen; und falls es auch gleichzeitig eine A-Methode gibt, wird diese auch genannt, aber bei der Bewertung wird der kleinste Punktwert benutzt), dann erst A1 und A2, und am Ende die bisherige C-Methode (einzig mögliche Zahl, jetzt umbenannt in B-Methode), weil dies der natürlichen Reihenfolge entspricht, wenn man - wie das Ziel dieser Software ist - möglichst ohne Anschreiben der Reste/Kandidaten auskommen will (März 2011).
• Ohne ausführliche Beschreibung wird als letztes die Ausdünn-Methode Ausschluss-Rechteck (Unique Rectangle) eingeführt, die aber darauf basiert, dass das Sudoku eindeutig lösbar sein muss und insofern eine umstrittene Methode ist. Sie soll hier trotzdem angeboten werden. Genaueres siehe bei http://hodoku.sourceforge.net/de/tech_ur.php oder bei http://home.arcor.de/r.sudogu/r_tec/UniqueRectangle.html.
  Dazu etwas Statistik:
  Von insgesamt 1210923 zur Verfügung stehenden Sudokus können
  • 993056 nur mit den einfachen Methoden A (eindeutige Stelle) und C (einzig mögliche Zahl) gelöst werden
  • 110589 weitere Sudokus können mit den hier programmierten Ausdünn-Methoden gelöst werden
  • 107278 Sudokus können mit diesem Programm nicht gelöst werden; sie benötigen in der Trial&Error-Version bis zu 338 Versuche in bis zu 16 Feldern, um gelöst werden zu können. Mit einer abgewandelten Forcing-Chain-Methode konnten davon aber 100554 Sudokus gelöst werden, aber 6724 Sudokus bleiben weiterhin ungelöst, darunter AI Escargo, Easter Monster und Golden Nugget.
  
  Bei den 110589 mit Ausdünnen lösbaren Sudokus werden folgende Methoden benutzt:
  • 53.5 % Box- und Zeilen-/Spalten-Tests
  • 16.5 % N-Tupel
  • 12.0 % Einzelzahl-Ketten
  • 16.5 % Goldene Ketten
  •   1.5 % Ausschluss-Rechtecke (dabei 75 % für Typ 1, 4 und 7)
  
  Man sieht weiterhin die Bedeutung der Goldenen Ketten, aber auch, dass spezielle Methoden wie die der Ausschluss-Rechtecke nicht so sehr viel bringen (8300 vorher nicht lösbare Sudokus wurden damit gelöst); analoges würde auch für andere Methoden gelten wie Fast Gesperrte Mengen (Almost Locked Sets) oder Zwangsketten (Forcing Chains) (Februar 2011).
• Da die X-Wing-Methode keine bedeutende Ausdünn-Methode war, wurde ein Verfahren, das diese Methode als Sonderfall enthält, eingebaut: die Einzelzahl-Ketten-Methode (Single Digit Pattern). Damit konnten etwa 13400 der bisher knapp 129000 nicht lösbaren Sudokus erfolgreich berechnet werden. Erstaunlicherweise wurden bisher keine Ketten mit mehr als 8 Gliedern gefunden, wenn sie auch gleichzeitig zu einer Lösung führen sollte - nur bei 6 Sudokus wurden Ketten der Länge 10 gesehen (Dezember 2010/Januar 2011).
• Inzwischen wurden über 1210000 Sudokus gerechnet, von denen 1081000 (90 %) lösbar waren; d.h. 129000 sind mit dieser Software bisher nicht lösbar - darunter auch die bisher bekannten schwierigsten Sudokus überhaupt (AI Escargo, Easter Monster und Golden Nugget - Dank an Peter Frei). Dazu müssten mehr Verfahren implementiert werden, es ist aber schwierig zu sagen, welche von den etwa 50 bekannten Verfahren sinnvoll sind, da sie ja auch mit Hand durchführbar sein sollen (November 2010).
• Die bei http://sourceforge.net/projects/php-sudoku/ gefundenen 1 Million Sudokus (Dank an Michael Jentsch) wurden durchgerechnet. Sie sind aber etwas einfacher als die hier bisher gesammelten mehr als 22000 Sudokus, denn 965351 Sudokus konnte ohne Ausdünnung gerechnet werden, 30420 Sudokus (3 %) konnten nur mit Ausdünnung gelöst werden, und nur 4229 (0.4 %) Sudokus konnten mit diesem Programm nicht gelöst werden, hatten aber eine eindeutige Lösung, die sich durch Trial&Error aber im Allgemeinen auch sehr einfach finden ließ. Interessant wieder: X-Wings waren 4483 dabei, aber Goldene Ketten 47581, fast 11 Mal so viel (August 2010).
• Die jeweils neu gefundene Zahl wird mit spitzen Klammern, also z.B. >7< markiert (Juli 2010).
• Die Beispiele wurden in ihrem Aufbau verändert und auf eine extra Webseite gebracht, damit die eigentliche Seite nicht zu lang ist (Juni 2010).
• Jetzt gibt es die Möglichkeit, ein Sudoku, das mit den hier programmierten Methoden nicht gelöst werden kann, auf eindeutige Lösbarkeit testen zu lassen. Von 3400 untersuchten hier nicht lösbaren Sudokus waren etwa 630 eindeutig lösbar, über 2500 hatten mehr als eine Lösung - mit bis zu 52000 verschiedenen Lösungen - und etwa 230 waren prinzipiell nicht lösbar (Mai/Juni 2010).
• Die Punkte-Bewertung wurde geändert, insbesondere wurden die A-Methoden getrennt, da man eine fehlende Zahl in Boxen viel einfacher (1 Punkt) sieht als in Zeilen oder Spalten (NEU: 3 Punkte); und eine jeweils 9. fehlende Zahl wird gar nicht bewertet. Außerdem werden die Felder gezählt und mit je 1 Punkt bewertet, in denen zur Ausdünnung Reste/Kandidaten eingetragen werden müssen (April/Mai 2010).
• Jetzt wurden die Erklärungen und Beispiele zum Verständnis der Lösungsstrategien vollkommen überarbeitet und dabei auch Fehler behoben (Sorry!). Vielleicht kann man das Ganze nun besser verstehen... (März 2010).
• Es wurden auch schon über 200 Stunden für die Analyse der über 20000 Beispiele aufgewendet, z.B. für die verschiedenen Beispiel-Listen (höchste Punktzahl, längste Goldene Kette, lösbar nur durch Quadrupel, usw.), - insbesondere ein paar Dutzend Prozeduren geschrieben, um das Ganze einigermaßen automatisch zu erzeugen, da es immer wieder aktualisiert wird. Auch die beiden Reduzierungsläufe kosteten einiges an Zeit... (Februar 2010).
• Endlich wurde auch die Ausdünn-Methode X-Wing programmiert (in 5 Stunden von nun insgesamt etwa 300 Stunden Programmierarbeit). Leider erbrachte das aber auch nur knapp 1% mehr Lösungen (gegenüber 15% bei der Goldenen Kette!)... Aber immerhin hat die X-Wing-Methode den Vorteil, auch bei Zellen mit mehr als 2 Kandidaten zu funktionieren (gegenüber der Goldenen Ketten) - weswegen die Programmierung doch sinnvoll ist (Januar 2010).
• Dem entsprechend wurde auch die Reihenfolge der Ausdünn-Methoden umgestellt: Zuerst kommen nun die einfachen Zeilen-/Spalten- und Box-Test-Methoden, danach erst die N-Tupel, dann X-Wing und am Ende die Goldenen Ketten (Januar 2010).
• Es wurde die Goldene Kette in einer zweiten Version programmiert: Kürzere Kette werden zuerst gefunden (Maximallänge 14 - gegenüber vorher 23). Erstaunlichstes Ergebnis überhaupt aber war, dass durch die Programmierung der Goldenen Ketten 15% mehr Lösungen gefunden werden konnten als vorher - und zwar auch noch fast genau so viele wie durch die Methode der 2-Tupel (Doppel) gefunden werden! Das Verfahren ist damit eine sehr wichtige Methode, aber auch aufwändiger: Es wurden schon Sudokus mit einer Rechenzeit von über 20 Sekunden (auf dem aktuellen Webserver) gelöst (bei der ersten Version aber wesentlich länger) - 30 Sekunden stehen bei Web-Anwendungen im Allgemeinen nur zur Verfügung (Dezember 2009; erste Version mit Rekursion: November 2009).
• Die Programmierung der N-Tupel wurde verbessert, so dass nun auch N-Tupel gefunden werden, deren einzelne Mitglieder alle aus weniger als N Zahlen bestehen. Die gewählte Methode erkennt nun etwa 99.9% dieser Fälle - eine nochmals erweiterte Programmierung brachte nur ein Beispiel aus 10000 Sudokus, kostet aber 15 % mehr an Laufzeit und wird deswegen weggelassen (die Programmteile sind auskommentiert und könnten auf dem eigenen Rechner aktiviert werden)... Versteckte N-Tupel müssen nicht extra programmiert werden, da sie immer mit direkten N-Tupel korrespondieren (Oktober 2009).
• Es fehlt die Programmierung von weiteren Ausdünn-Methoden wie z.B.: Swordfish (Erweiterung von X-Wing), und Colouring und Multicolouring, die aber nicht so viel zusätzliche Sudokus lösen werden können wie die bisherigen Methoden (auch X-Wing hatte ja nicht so viel gebracht...). Die verschiedenen Forcing Chain-Verfahren sind im Prinzip Trial&Error-Methoden und werden daher nicht implementiert.

Sechs direkte Sudoku-Lösungsmethoden (A bis F)

1. Einfachste Methode: Direkte Dreier-Methode oder eindeutige Stelle (Hidden Single): Bestimme die fehlende dritte Zahl in drei zusammen liegenden (nebeneinander oder untereinander) Boxen. D.h.: Findet man in zwei von drei zusammen liegenden Boxen eine bestimmte Zahl, sucht man in der dritten Box nach einem eindeutigen Ort, an dem diese Zahl stehen kann. In vielen Fällen ist es auch einfach die einzige Stelle, an der eine bestimmte Zahl nur stehen kann, insbesondere beim Durchsuchen von Zeilen und Spalten.

   Bewertung: 1 Punkt innerhalb Boxen, 3 Punkte innerhalb Zeilen/Spalten, 0 Punkte bei der 9. fehlenden Zahl; Farbmarkierung: Grün

   Einfacher Fall:
   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 Felder nicht ausgefüllt, da deren Inhalt ohne Bedeutung ist; ebenso fehlen im Allgemeinen die letzten Zeilen der Beispiel-Sudokus.

   | | 7 | | 7 | | | | | | 1 | | 4 5 ... ... ... | | ... ... ... | | ... ... ...

   Komplexerer Fall:
   Es kann auch in den Zeilen und Spalten nachgesehen werden, ob eine Stelle für die bestimmte Zahl frei ist. In diesem Beispiel kann die Zahl 7 wieder nur in der dritten Zeile der rechten Box (OR) liegen. Da aber in der 8. Spalte in der darunter liegenden Box (MR) schon eine 7 steht, bleibt wieder nur die letzte Spalte (mit kleinem x markiert) als Zielort übrig.

   | | 7 | | 7 | | | | | | 1 | | 4 | | | | 7 ... ... ... | | ... ... ... | | ... ... ...

   Beispiele mit vielen A-Fällen und hohen Punktzahlen:

   55 wirkende von 97 A-Fällen (mit 99 Punkten): 000000000000001002034000050000000630000007400700085000000300040000800000270000000

   56 wirkende von 93 A-Fällen (mit 105 Punkten): 000000001000002000034000000000000350000006040600078000000300400000700800280000000

   57 wirkende von 97 A-Fällen (mit 120 Punkten): 000000001000000023000045000000000004002010000060000500000006000103000000700502800

2. 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. Das klingt zwar einfach, ist aber nicht so leicht zu erkennen.

Bewertung: 5 Punkte, 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.

| | 2 6 | | | | 3 | | 8 | | 1 | | 4 9 | | 5 | | 7 ... ... ... | | ... ... ... | | ... ... ...

Beispiele mit vielen B-Fällen:

15 wirkende von 28 B-Fällen (mit 132 Punkten): 006100700020500900080400100900000002700030005500060000000700060000009030000010400

17 wirkende von 29 B-Fällen (mit 149 Punkten): 000000000000001023045060000000000407000010000300008000000040500000900000200003080

18 wirkende von 26 B-Fällen (mit 138 Punkten): 000000001000000230004056000000000040000203700051000000000010007300000800900000000

Beispiele ohne offensichtliche Zeilen-/Spalten-Tests und 2-Tupel:

27 wirkende von 32 B-Fällen (mit 158 Punkten): 003805900000000080200007006600020503000301000009000007700600000030000000008509100

28 wirkende von 35 B-Fällen (mit 170 Punkten): 005800700000200000400001009670000940000000000028000015800700002000509000001004600

3. Offensichtlicher Zeilen-/Spalten-Test: Bestimme den Ort der dritten Zahl ohne genaue Kenntnis des Ortes der zweiten Zahl: Hier nutzt man aus, dass die Position der zweiten Zahl zwar noch nicht genau bekannt ist, aber auf eine Zeile oder Spalte einer Box beschränkt werden kann. Dann folgt der Ort für die dritte Zahl analog der oben beschriebenen Methode A. Dieses Verfahren kann in bestimmten Fällen auch ohne Kenntnis der ersten Zahl funktionieren. Diese Methode ist oft einfacher zu sehen als die A1- und A2-Methoden (einzige Position in einer Zeile oder Spalte), wenn es nur eine Begründung gibt.

Bewertung: 2 Punkte mal Anzahl der Begründungen, Farbmarkierung: Rot

Einfacher Fall:
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 von Box OR ist aber 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).

5 4 7 | | | | 2 8 8 | | 2 | | 2 3 | | | | 5 4 9 | | | | 6 ... ... ... | | ... ... ... | | ... ... ...

Komplexerer Fall:
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öglicher Ort für die 7 in dieser Box nur die beiden Positionen in der Spalte 5 übrig (mit kleinem a markiert).
Nun kann man ähnlich wie im einfachen Fall folgern, dass in der darüber liegenden Box (OM) die Zahl 7 nur in der oberen Zeile sein kann (Spalte 4 oder 6), wobei die genaue Position aber noch unbekannt ist. Also muss in der rechts davon liegenden Box (OR) die 7 wieder in der 3. Zeile sein. Da aber in der 8. Spalte in der darunter liegenden Box (MR) schon eine 7 steht, bleibt wieder nur die letzte Spalte (mit kleinem x markiert) als Zielort übrig.

Alternativ kann man auch argumentieren, 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 (siehe oben, mit kleinem a markiert), aber auch nicht in Spalte 8 der Box OR (siehe oben), und somit bleibt dort nur die Spalte 9 (mit kleinem x markiert) als Zielort übrig.

| | | | 7 | | | | | | 2 1 | | 4 | | 3 2 | | | | | | 7 ... ... ... | | 5 8 | | ... ... ...

Beispiele mit vielen C-Fällen:

19 wirkende von 23 C-Fällen (2 Mal "und folgend", 1 Mal "und ... und folgend"): 000080010500000200600000000017000008000200600000000000030000087200406000000500000

24 wirkende von 30 C-Fällen (4 Mal "und"): 000000000000000012003045000000000000000100067045000080000003500100000200600700000

3 wirkende von 8 C-Fällen (1 Mal "und", 1 Mal "und ... und folgend", 1 Mal "und ... und ... und folgend", 2 Mal "und ... und folgend ... und folgend") : 760900050001200760402000010000024100100000500050000090020015080000060371010700000

7 wirkende von 14 C-Fällen (2 Mal "und", 1 Mal "... und folgend ... und folgend") : 900600078852000900000008000009802103003090007200001009008030006090207000001000390

Schwierigste einfache Sudokus (ohne offensichtliche Zeilen-/Spalten-Tests und 2-Tupel):

37 A-Fälle und 24 B-Fälle und 10 Mal Extra-Punkte mit 265 Punkten: 000010000000234000005000600010000040780000021030000090007000500000381000000020000

52 A-Fälle und 12 B-Fälle und 15 Mal Extra-Punkte mit 298 Punkten: 000000001000002003045000000000006000000370080028000100000050040000800000100000006

4. Offensichtliche 2-Tupel (Doppel): In vielen Fällen sieht man zwei zusammengehörende Zellen, in denen zwei bestimmte Kandidaten nicht vorkommen können, weil sie in den anderen Zellen der Zeile, Spalte oder Box schon vorkommen. Diese werden hier offensichtliche 2-Tupel genannt und ermöglichen das Auffinden von Zahlen, ohne dass alle Kandidaten aufgeschrieben werden müssen. Dabei gibt es drei Arten:

Bewertung: 5 Punkte, Farbmarkierung: Gelbgrün

Methode D1/D2/D3 analog A1/A2/A3 - Beispiel: Wegen des offensichtlichen 2-Tupels 15 kann die einzige Zahl an der Position Zeile 2 und Spalte 6 (mit kleinem x markiert) nur die Zahl 7 sein.

| | 8 6 | | 2 5 1 | | 2 | |       | | 15   15 | |       | | 7 | | 4 | | 5 | | | | 1 | | ... ... ... | | ... ... ... | | ... ... ...

Methode D0 analog B0 - Beispiel: Durch das offensichtliche 2-Tupel 48 kann ausgeschlossen werden, dass die Zahlen dieser 2-Tupel 4 und 8 an der betrachteten Stelle (mit kleinem x markiert) liegen; daher kann dort nur die Zahl 9 sein.

6   7   1   | | 2   48 48 | |       | | 7 5 1 | | 8 2 5 | | | | 4 7 | | | | 5 | | | | 3 ... ... ... | | ... ... ... | | ... ... ...

Methode D4 - Beispiel: Die zwei offensichtlichen, aber verschiedenen 2-Tupel 17 und 47 haben eine gemeinsame Zelle (mit kleinem x markiert): Dann kann diese Zelle nur den gemeinsamen Kandidaten haben.

8   3   17 | |       | | 6   4     2 | | 1 6 | | 7 6   5   17+47 | | 3   8   47 | |   2     ... ... ... | | ... ... ... | | ... ... ...


In der mittleren Reihe der linken Box können 1 und 7 nicht vorkommen; in der letzten Reihe können 4 und 7 nicht in der rechten Box liegen: Die einzige Zahl an der mit kleinem x markierten Stelle kann also nur die den beiden Paaren gemeinsame Zahl 7 sein.

Beispiele mit vielen D-Fällen:

24 wirkende von 48 D-Fällen (mit 34 Mal D1-3 und 12 Mal D0 und 2 Mal D4, dabei eine 3-fach-Begründung bei D1): 000000000000001002003000040000000000000050360070002000000000007005630000020807001

18 wirkende von 56 D-Fällen (mit 39 Mal D1-3 und 17 Mal D0, dabei zwei 3-fach-Begründungen): 000000001000002000003000045000000600000078900051000000000410003800000200900000000

7 wirkende von 13 D-Fällen (mit 10 Mal D1-3 und 3 Mal D0, dabei eine 4-fach-Begründung): 001300054000902000000000300400570000508000640200000100700000090802006500003008070

7 wirkende von 14 D-Fällen (mit 11 Mal D1-3 und 3 Mal D0, dabei eine 5-fache Begründung): 003406000050000000000001504010000603000008900090020007500070002807000056000010070

5. Vollständige Ausdünnung mit einzig auftretender Restzahl (alleine auftretender Kandidat): Hat man nach einem oder mehreren Ausdünnschritten mehrere Reste so weit verkleinert, dass eine bestimmte Zahl 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.

Bewertung: 4 Basis-Punkte, 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:
Nach der Ausdünn-Methode III (siehe weiter unten im nächsten Abschnitt) findet man in der Box OR das Reste-Paar 79 zwei Mal. Die Zahlen 7 und 9 müssen also an diesen beiden Stellen auftreten. Damit können in allen anderen Resten dieser Box die Zahlen 7 und 9 gestrichen werden. Daraus folgt, dass an der Position Zeile 1 und Spalte 4 (mit kleinem x markiert) die Zahl 7 stehen muss.

2   6   4   | | 157 9   15 | | 157 8   3   1579 1579 1579 | | 2   3578 1358 | | 6   4   79 3   8   1579 | | 1357 6   4   | | 1579 2   79 | | 6 2 | | 8 1 | | 8 1 7 | | 5 ... ... ... | | ... ... ... | | ... ... ...

6. Vollständige Ausdünnung mit einstelliger Restzahl bzw. einziger Kandidatenzahl: 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.

Bewertung: 1 Basis-Punkt, Farbmarkierung: Braun

Beispiel:
Nach der Ausdünn-Methode I (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 (d.h.: 249 wird zu 24, 39 wird zu 3).
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.

5   246 36 | | 9   8   7   | | 1234 1234 1234 1   279 379 | | 23 23 4   | | 8   6   5   8   249 39 | | 1   6   5   | | 7   2349 2349 4 | | | | 3 2 | | | | ... ... ... | | ... ... ... | | ... ... ...

Sechs Methoden zur Ausdünnung der Reste (I bis VI)

1. 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: Für jedes Vorkommen gibt es 3 Punkte.

Beispiel:

3   789 5   | | 12789 12489 124789 | | 1479 1479 6   178 4   1789 | | 5   1389 6   | | 1379 2   1379 6   79 2   | | 1379 1349 13479 | | 8   134579 134579 9 1 | | 4 7 2 | | ... ... ... | | ... ... ... | | ... ... ...


Hier findet man z.B. die Zahl 1: Sie ist in den Resten der Box OL nur in der zweiten Zeile vorhanden (rot gefärbte Reste), 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:

3   789 5   | | 12789 12489 124789 | | 1479 1479 6   178 4   1789 | | 5   [1]389 6   | | [1]379 2   [1]379 6   79 2   | | 1379 1349 13479 | | 8   134579 134579 9 1 | | 4 7 2 | | ... ... ... | | ... ... ... | | ... ... ...

2. 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 anderen Zeilen bzw. Spalten innerhalb dieser Box gestrichen werden. Dies ist die am häufigsten auftretende Methode, um die Reste auszudünnen: 48 %!

Bewertung: Für jedes Vorkommen gibt es 3 Punkte.

Beispiel:

28 5   3   | | 4   7   9   | | 12 6   128 7   1289 12689 | | 136 136 5   | | 1239 12389 4   4   19 169 | | 8   136 2   | | 1359 7   1359 1 6 | | | | 8 ... ... ... | | ... ... ... | | ... ... ...


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ärbte Reste). Also kann man in den anderen Zeilen dieser Box diese Zahl aus den Resten streichen - das wird hier durch die Darstellung in eckigen Klammern hervorgehoben. Damit bleibt übrig:

28 5   3   | | 4   7   9   | | 12 6   128 7   1289 12689 | | 136 136 5   | | [1]239 [1]2389 4   4   19 169 | | 8   136 2   | | [1]359 7   [1]359 1 6 | | | | 8 ... ... ... | | ... ... ... | | ... ... ...

3. 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 Stellen innerhalb einer Zeile, Spalte oder Box sucht, in denen genau N verschiedene Kandidaten auftreten, also keine anderen Kandidaten. Wenn an 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 Resten gestrichen werden.

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 M anderen Kandidaten), wobei N+M gleich der Anzahl der freien Zellen 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: Für jedes N-Tupel gibt es 2*N Punkte (es gilt nur die Länge des direktes N-Tupels, nicht des versteckten N-Tupels).

Einfaches Beispiel mit 2-Tupel (Doppel):

6   79 2   | | 79 1   3479 | | 8   34579 34579 189 4   179 | | 5   3789 6   | | 1379 2   1379 3   1789 5   | | 2789 24789 2479 | | 1479 1479 6   7 8 | | 4 | | | | 3 8 | | ... ... ... | | ... ... ... | | ... ... ...


Hier findet man z.B. in der ersten Zeile das 2-Tupel 79 (Doppel: 79, 79) - bzw. das versteckte 3-Tupel (Tripel) 345 -, als rot gefärbte Reste markiert; die beiden Kandidaten 7 und 9 müssen also an diesen beiden Stellen sein. Also kann man in den anderen Resten dieser Zeile diese beiden Zahlen streichen (durch die Darstellung in eckigen Klammern hervorgehoben). Damit bleibt übrig:

6   79 2   | | 79 1   34[7][9] | | 8   345[7][9] 345[7][9] 189 4   179 | | 5   3789 6   | | 1379 2   1379 3   1789 5   | | 2789 24789 2479 | | 1479 1479 6   7 8 | | 4 | | | | 3 8 | | ... ... ... | | ... ... ... | | ... ... ...

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.

4     | | 2357 235 9   | |   1       1     | | 6   23 8   | |     5       3   | | 12457 25 12457 | |       | | 7 | | | | 4 | | ... ... ... | | ... 1 ... | | ... ... ...

Relativ häufig (in etwa 10% aller N-Tupel-Fälle) findet man noch 4-Tupel (z.B. das Quadrupel 1479 mit: 147, 17, 79, 49), aber 5-Tupel, 6-Tupel und 7-Tupel sind sowohl noch seltener (2 %) als auch schwieriger zu erkennen...

Beispiele mit 2-Tupeln:

5 Mal 2-Tupel: 000000000000000012003045000000003006020700000400000500000600000005000000800210007

7 Mal 2-Tupel: 004080700070030050000107006006000400090604000003020090100002009080010030002000008

Beispiele mit 3-Tupeln:

4 Mal 3-Tupel: 000057000006100000089000040200710300300800092000000000042030008000900060031000000

5 Mal 3-Tupel: 103006009400000031000000065005910000000020000007040020040000800600005000900800000

Beispiele mit 4-Tupeln:

5 Mal 4-Tupel: 020400000050000003009600100200000000000906001030008507004000002000000806008010035

6 Mal 4-Tupel: 000040009869237451040005200730000000980000010000000094602350000418679523503082000

Beispiele mit 5-Tupeln:

5 Mal 5-Tupel: 100407080006009030700200050231000900005000401000000000000010000000008002890700000

13 wirkende von 24 N-Tupel (bei 2 Mal 5-Tupel): 003450009000109700080060000000090000014000000005320000000006908040000100000005062

Beispiele mit 6-Tupeln:

3 Mal 6-Tupel: 100007009050100000000260000007000400314000000800000030000002040040900270070005360

14 wirkende von 22 N-Tupel (bei 3 Mal 6-Tupel): 100007009050100000080260000007000400314020000800000030000000040040900270000005360

Beispiele mit 7-Tupeln:

1 Mal 7-Tupel: 100050600000080207009030000030000000500900008008204000004000000600000701070000306

11 wirkende von 23 N-Tupel (bei 1 Mal 7-Tupel): 100407080006009030700200050231000900005000401000000000000010000000008002890700000

4. Einzelzahl-Ketten (Single Digit Pattern, Forcing X-Chain): Kette aus Resten, bei denen überall eine bestimmte Zahl vorkommt (das verbindendes Element). Man sieht für eine bestimmte Zahl in den Resten nach, ob in Zeilen oder Spalten oder Boxen diese Zahl genau zwei Mal vorkommt. Hat man mehrere solcher sogenannten starken Doppel (Paar wird hier nur für eine Zelle mit genau zwei Kandidaten benutzt) gefunden, lassen sich diese eventuell dadurch zu einer Einzelzahl-Kette verbinden, dass jeweils ein Anfang oder Ende in der gleichen Zeile, Spalte oder Box wie ein anderes starkes Doppel liegen; interessant ist hierbei, dass die anderen Kandidaten der jeweiligen Reste keine Rolle spielen, egal welche und wie viele es sind. Wenn sowohl vom Anfang einer so konstruierten Kette als auch vom Ende dieser Kette ein oder mehrere Zellen "gesehen" werden, also in der jeweils gleichen Zeile, Spalte oder Box liegen, kann die bestimmte Zahl aus diesen Zellen 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 ein starkes Doppel 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.

Bewertung: Für jedes Vorkommen gibt es 2*N Punkte entsprechend der Länge N der gefundenen Kette (N = 4 bis - theoretisch - 18, immer geradzahlig, mit 16 als einmal größte bisher gefundene Kettenlänge und 12 als bisher ausreichende Kettenlänge).

Literatur:
Sonderfälle dieses Verfahrens: X-Wing, Swordfish (Minimum-Version), Jellyfish (Minimum-Version), Skyscraper, Turbot Fish, Two-String Kite (Long String Kite und Empty Rectangle sind Erweiterungen).
AHR Software: Single Digit Pattern, z.B. Skyscraper http://www.ahr-sudoku.de/solving.php/technic/Skyscraper
HoDoKu: http://hodoku.sourceforge.net/de/tech_sdp.php

Beispiel:

2389 1   89 | | 7   34 5   | | 6   489 28 568 568 4   | | 2   9   1   | | 58 7   3   2359 2359 7   | | 6   34 8   | | 24 459 1   1   278 3   | | 5   27 9   | | 24 48 6   2459 2459 59 | | 8   6   3   | | 7   1   29 2789 2789 6   | | 1   27 4   | | 35 35 289 ...     ...     ...     | | ...     ...     ...     | | ...     ...     ...


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 mit dem zweiten Spaltendoppel (24-24) über Zeile 4 verbinden (die dritte 2 in dieser Zeile stört bei der Verbindung von starken Doppeln nicht). Das Zeilendoppel kann man als letzten Teil der Kette in der rechten oberen Box anschließen (das starke Doppel 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 ein sogenanntes starkes Doppel ist), kann somit nicht in Zeile 4/Spalte 7 sein, muss also in Zeile 3/Spalte 7 sein (starkes Doppel 24-24), also nicht in Zeile 1/Spalte 9, und muss daher in Zeile 1/Spalte 1 (starkes Doppel 2389-28) sein. Damit erhält man:

23896 1   89 | | 7   34 5   | | 6   489 285 568 568 4   | | 2   9   1   | | 58 7   3   2359 2359 7   | | 6   34 8   | | 244 459 1   1   278 3   | | 5   272 9   | | 243 48 6   2459 2459 59 | | 8   6   3   | | 7   1   29 [2]789 2789 6   | | 1   271 4   | | 35 35 289 ...     ...     ...     | | ...     ...     ...     | | ...     ...     ...


Bisher wurde hier die X-Wing-Methode benutzt. Diese ist aber nur ein Sonderfall der Einzelzahl-Ketten-Methode, im folgenden Beispiel also die Ketten mit der Zahl 5: 56-56-157-157 (ab Spalte 2) und 56-56-157-157 (ab Spalte 5): es können alle Auftreten der Zahl 5 außerhalb dieser Kette bzw. des X-Wings in der Spalte 2 bzw. Spalte 5 gestrichen werden:

8   56 3   | | 9   56 2   | | 1   4   7   567 2[5]67 9   | | 56 4   1   | | 8   3   25 45 24[5] 1   | | 7   3   8   | | 6   9   25 1457 14[5]7 8   | | 56 2   9   | | 3   167 146 3   157 6   | | 8   157 4   | | 2   17 9   2 ... ... | | ... ... ... | | ... 5 ...

Beispiele mit Einzelzahl-Ketten der Länge 4:

Beispiel mit 10 Einzelzahl-Ketten: 103000000000109000780000500200000008004000903000200100000900800600004005092300041

Beispiel mit 11 Einzelzahl-Ketten: 103007009006100000080000400008000050000002007030500900040060000000900001005800702

Beispiel mit 12 Einzelzahl-Ketten: 000400600000089030700236000210000090030005400000310000040060500500000070000073000

Beispiel mit 13 Einzelzahl-Ketten: 020400080400090130709003040200007005000900300005030070007000001000800600090002000

Beispiel mit 14 Einzelzahl-Ketten: 000007009456000000080000000001640005005003000900000460060905800000004900000710023

Beispiele mit Einzelzahl-Ketten bis Länge 6:

Beispiel mit 12 Einzelzahl-Ketten: 190200400802001000406800010910000604507000001624700053085604007040100200261009000

Beispiel mit 14 Einzelzahl-Ketten: 003000609056180000000002040200806004070905200000000000030200000000004002000000760

Beispiel mit 16 Einzelzahl-Ketten: 000523604036040200000600008000000300452300000070000002700402000000790085004030100

Beispiel mit 18 Einzelzahl-Ketten: 000600049000000850923004000000900706300000000070508090502080000006090030019700005

Beispiele mit Einzelzahl-Ketten bis Länge 8:

Beispiel mit 16 Einzelzahl-Ketten: 000000000000000012003045000000006405010000006700800000000120030000700000005000000

Beispiel mit 18 Einzelzahl-Ketten: 008073002001009030700000810007000020023058000590312070070834000109027003000600207

Beispiel mit 20 Einzelzahl-Ketten: 000000000000001023004050600000000002000703001006000400000040800010000000730000000

Beispiel mit 22 Einzelzahl-Ketten: 100007000056080003080060014000000007010200090030040020300001000000020006902000040

Beispiele mit Einzelzahl-Ketten bis Länge 10:

Beispiel mit 15 Einzelzahl-Ketten: 070009000300800007108005000090007030000403008080900040000300604400002005000700090

Beispiel mit 17 Einzelzahl-Ketten: 100407000006000203000000400270000008000024050000030006010008000600000001008070062

Beispiel mit 19 Einzelzahl-Ketten: 300409010000020300079010008000700000014203760700001030400000970090060000020008001

Beispiel mit 21 Einzelzahl-Ketten: 000000001000002003004050000000040060010300000200000000000700400080000050690001000

Beispiele mit Einzelzahl-Ketten bis Länge 12:

Beispiel mit 12 Einzelzahl-Ketten: 000000000000000012003004000000005004010000067080030000000810000005000300060200000

Beispiel mit 13 Einzelzahl-Ketten: 000000001000000020003004000000003400050006000120000070000050600000720000008000300

Beispiel mit 14 Einzelzahl-Ketten: 000000000000001002034000050000000006007340000280000001000500030100002000600000000

Beispiele mit Einzelzahl-Ketten bis Länge 14 bzw. nicht-wirkend auch 16:

Beispiel mit 14 Einzelzahl-Ketten: 000000000000000012003045000000006400010000000270000008000100000004000530020070000

Beispiele mit vielen und langen Einzelzahl-Ketten:

19 wirkende von 66 Einzelzahl-Ketten (maximal 10 lang): 300409010000020300079010008000700000014203760700001030400000970090060000020008001

16 wirkende von 63 Einzelzahl-Ketten (maximal 12 lang): 070608040006702300200000006012000487600070000057080960500000001709815604060407050

4 wirkende von 45 Einzelzahl-Ketten (maximal 14 lang): 000000000000000012003045000000006500070000000120000080000271000000400000006000300

5. Goldene Kette (Golden Chain, XY-Chain, Double Implication Chain): Das ist eine Reihe von Paaren vom Typ ab, bc, cd, de, ef, ..., xy, yz, za, von denen jeweils zwei aufeinanderfolgende Paare in der gleichen Zeile, Spalte oder Box liegen und die eine gemeinsame Zahl besitzen, die aber - im Gegensatz zur Einzelzahl-Kette - von Kettenglied zu Kettenglied anders sein kann. Wenn die Zahl des ersten Paars, die nicht im zweiten Paar vorkommt (hier bei ab also a) mit der Zahl des letzten Paars, die nicht im vorletzten Paar vorkommt (bei za also auch a), übereinstimmt, dann kann man alle Zahlen 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, weil die Zahl a auf jeden Fall entweder am Anfang der Kette oder am Ende der Kette vorkommen muss (wenn a an der Stelle des ersten Paares vorkommt, ist das offensichtlich; kommt dort aber b vor, so muss an der Stelle des zweiten Paares c sein, daher an der des dritten Paares d usw., bis zu z an der Stelle des vorletzten Paares, also a an der Stelle des letzten Paares, was behauptet wurde).

   Bewertung: Hierbei gibt es 2*N Punkte entsprechend der Länge N der gefundenen Kette (N = 3 bis etwa 20, mit 19 als zweimal größte bisher gefundene Kettenlänge und 13 als bisher ausreichende Kettenlänge).

   Literatur:
   Download des Artikels von Eduyng Castan: http://www.coverpop.com/sfiles/Sudoku-GoldenChains.pdf
   Ähnlicher Artikel von Mihail Iusut: http://www.scanraid.com/sudoku/Remote_Pairs_and_XY_Chains.pdf

   Beispiel einer Goldenen Kette:

   8   271 6   | | 4   9   5   | | 372 23 1   1[2] 3   124 | | 8   7   6   | | 5   9   24 5   9   47 | | 23 123 12 | | 8   6   47 124 6   9   | | 237 4   27 | | 133 5   8   7   1[2] 8   | | 5   23 9   | | 4   13 6   ... ... ... | | ... ... ... | | ... ... ...

   
   Die gefundene Goldene Kette 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 im Feld (2:1), also Zeile 2 und Spalte 1, und im Feld (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.

   Beispiele mit Goldenen Ketten der Länge 3:

   Beispiel mit 4 Goldenen Ketten: 001800705900250003200300000060003009302000040780402630010000000007000080009000100

   Beispiel mit 5 Goldenen Ketten: 679080041000900308302004079030006000000002900804009610200305406000640100000000005

   Beispiele mit Goldenen Ketten bis Länge 4:

   Beispiel mit 8 Goldenen Ketten: 023000000000100007709060050000605000390000060018000000000801700000004390000300020

   Beispiel mit 11 Goldenen Ketten: 003000000400709001080100000030008000005060002960000050004000806000027043600000090

   Beispiele mit Goldenen Ketten bis Länge 5:

   Beispiel mit 17 Goldenen Ketten: 000057680000180000009000040240000050300010000000540170502000300010000400000900700

   Beispiel mit 18 Goldenen Ketten: 020104083000000012000508400006000305503070840007300600000000000004051030632087050

   Beispiele mit Goldenen Ketten bis Länge 6:

   Beispiel mit 21 Goldenen Ketten: 600009142070000006000100700806000405000040000100503060408006000700008200090070000

   Beispiel mit 23 Goldenen Ketten: 003000600400089200080602100000568003000000006090004002005000900000010070004700000

   Beispiele mit Goldenen Ketten bis Länge 7:

   Beispiel mit 27 Goldenen Ketten: 023050000050780102780000000240301060000060000090000040000090206000000093007000008

   Beispiel mit 28 Goldenen Ketten: 023050000050780102700000000240301060000060000090000040000090200800000093007000008

   Beispiele mit Goldenen Ketten bis Länge 8:

   Beispiel mit 23 Goldenen Ketten: 650000030000000900008029010000007086500080000200600300700100000060000243400000005

   Beispiel mit 29 Goldenen Ketten: 006510700040076800000040060000000009032090400100708300400000000307000508021000600

   Beispiele mit Goldenen Ketten bis Länge 9:

   Beispiel mit 24 Goldenen Ketten: 000901005000630000060050040000080000000500980670000500500040096803000100000002000

   Beispiel mit 25 Goldenen Ketten: 100000680000000000009260504200940006005000000040800007000700090800000201060010700

   Beispiele mit Goldenen Ketten bis Länge 10:

   Beispiel mit 24 Goldenen Ketten: 000000000000000012003045000000000000010602000500000340000107006004000000800200000

   Beispiel mit 25 Goldenen Ketten: 020400000450080030709100004030007408600500000095000000000600200000094807900000000

   Beispiele mit Goldenen Ketten bis Länge 11:

   Beispiel mit 29 Goldenen Ketten: 900030500810060047050004010000009075009300106075640030100200053020400000090000000

   Beispiel mit 30 Goldenen Ketten: 003400000050009000700020000204000517800000090000001004007000608008307040602000300

   Beispiele mit Goldenen Ketten bis Länge 12:

   Beispiel mit 27 Goldenen Ketten: 820501004000600001000040000100706902007010003200050070703900008000000349060030000

   Beispiel mit 30 Goldenen Ketten: 000740300900200400040100052036080700050002000800073260060000020500000180028300004

   Beispiele mit Goldenen Ketten bis Länge 13:

   Beispiel mit 23 Goldenen Ketten: 000090006300010400000300109900761002010000045000504701050009800460050927208000510

   Beispiel mit 24 Goldenen Ketten: 020000009000000123700003000000900430607000200000205001002040900000600000041030806

   Beispiele mit Goldenen Ketten bis Länge 14:

   Beispiel mit 22 Goldenen Ketten: 530700006400008739906300581000005000001000025254000000840000970127003050069400810

   Beispiel mit 24 Goldenen Ketten: 900080000400009701000100930200000010008010500000076000007000003002057109569430080

   Beispiele mit Goldenen Ketten bis Länge 15:

   Beispiel mit 21 Goldenen Ketten: 210000038000000000600314007003407600080000040006109200300576001000000000970000064

   Beispiel mit 23 Goldenen Ketten: 040012086050070000800000017023009001700020005000040030015200600006900050000051304

   Beispiele mit Goldenen Ketten bis Länge 16:

   Beispiel mit 13 Goldenen Ketten: 000004600900002003340000072005400200006800000700305840074918300093000100050200090

   Beispiel mit 14 Goldenen Ketten: 000390670000000800260007005000050140000608000095070000700900084003000000086031000

   Beispiele mit Goldenen Ketten bis Länge 17:

   Beispiel mit 18 Goldenen Ketten: 980004600240039085073001040000070010000005300008040002002507090360000000400002800

   Beispiel mit 20 Goldenen Ketten: 846009070020000096900720004010000300000000082005000007700900620000130000000087030

   Beispiele mit Goldenen Ketten bis Länge 18:

   Beispiel mit 14 Goldenen Ketten: 049020000500040000060010089035060948006000231020003005007006000000005190350070804

   Beispiel mit 26 Goldenen Ketten: 000005640005000390600000780103050000259604003000010000004208010300090204000000007

   Beispiele mit vielen aber lange rechnenden Goldenen Ketten:

   49 wirkende von 103 Goldenen Ketten (maximal 12 lang): 120406000006780003000000005018090500070205018000000007030000800040901602060000000

   55 wirkende von 84 Goldenen Ketten (maximal 15 lang): 103050000050009000080000004000060008008000072000290310004072000000004050030000800

   38 wirkende von 62 Goldenen Ketten (maximal 18 lang) - davon 32 in einem Ausdünnschritt: 023056000406009100000000000004600800010000006900370040002041005070000030000000902

   20 wirkende von 46 Goldenen Ketten (maximal 19 lang): 050072000000000004009086025020000081600000050007205063300090008081004500040803070

   31 wirkende von 60 Goldenen Ketten (maximal 19 lang): 581000000076400059040000060060000910050870003000004000098700000700961080004580000

   Die beiden Sudokus mit Goldenen Ketten der Länge 19 können auf diesem Webserver nicht gerechnet werden, da sie zu viel Rechenzeit benötigen. Hier daher nur die Einzelergebnisse:
   Im Sudoku 050072000000000004009086025020000081600000050007205063300090008081004500040803070 eine Goldene Kette der Länge 19:
   Goldene Kette für Zahl 4 gefunden: (1:1)14 - (1:8)19 - (2:8)19 - (2:6)19 - (4:6)79 - (7:6)17 - (7:7)16 - (7:2)67 - (3:2)37 - (3:7)37 - (2:7)78 - (2:3)68 - (9:3)56 - (9:1)59 - (9:9)29 - (9:5)12 - (6:5)14 - (6:7)49 - (4:7)49
   Im Sudoku 581000000076400059040000060060000910050870003000004000098700000700961080004580000 je zwei Goldene Ketten der Länge 19:
   Goldene Kette für Zahl 6 gefunden: (1:6)69 - (1:5)29 - (4:5)23 - (2:5)13 - (2:7)12 - (2:1)23 - (9:1)23 - (9:6)23 - (7:6)23 - (7:8)23 - (1:8)34 - (1:9)47 - (9:9)67 - (6:9)56 - (7:9)15 - (3:9)12 - (3:3)23 - (3:4)13 - (6:4)16
   und
   Goldene Kette für Zahl 9 gefunden: (1:5)29 - (4:5)23 - (2:5)13 - (2:7)12 - (2:1)23 - (9:1)23 - (9:6)23 - (7:6)23 - (7:8)23 - (1:8)34 - (1:9)47 - (9:9)67 - (6:9)56 - (7:9)15 - (3:9)12 - (3:3)23 - (3:4)13 - (6:4)16 - (5:6)69

   Lange Goldene Ketten der Länge 20 und 21 (!) aus früherer Software (ohne Einzelzahl- und Ausschluss-Ketten):
   Goldene Kette für Zahl 7 gefunden: (2:1)72 - (1:1)21 - (1:7)12 - (3:9)24 - (2:9)46 - (2:8)68 - (2:2)84 - (3:2)48 - (3:8)81 - (3:3)17 - (3:5)72 - (9:5)21 - (9:9)12 - (7:7)26 - (5:7)61 - (4:8)16 - (4:1)65 - (4:2)51 - (8:2)12 - (8:4)27
   Goldene Kette für Zahl 2 gefunden: (2:4)21 - (2:6)17 - (2:1)72 - (1:1)21 - (1:7)12 - (3:9)24 - (2:9)46 - (2:8)68 - (2:2)84 - (3:2)48 - (3:8)81 - (3:3)17 - (3:5)72 - (9:5)21 - (9:9)12 - (7:7)26 - (5:7)61 - (4:8)16 - (4:1)65 - (4:2)51 - (8:2)12

6. Ausschluss-Ketten: Ausschluss-Rechtecke und Ausschluss-Schleifen:

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) 7 Typen unterschieden. Genaueres siehe bei http://hodoku.sourceforge.net/de/tech_ur.php und bei http://home.arcor.de/r.sudogu/r_tec/UniqueRectangle.html, und auch bei http://www.sudokuwiki.org/Unique_Rectangles und http://www.sudokuwiki.org/Hidden_Unique_Rectangles. Die Typen 1-6 haben im Allgemeinen zwei oder drei gleiche Kandidatenpaare, die Typen 7A-7G meistens nur ein, weswegen sie auch oft als Versteckte Rechtecke - Hidden Unique Rectangles - bezeichnet werden; sie sind schwieriger zu sehen und zu lösen.

Bewertung: Hierbei gibt es 4, 6, 8+N, 12, 8, 12, 12 Punkte entsprechend dem Typ des Ausschluss-Rechtecks (N vom Quasi-N-Tupel).

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. Beispiel (dabei auch auf die 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

Ausschluss-Rechteck Typ 7 für (3:8 - 3:9 - 8:9 - 8:8)14 gefunden: Wegen Kandidat 1 alleine in einer Zeile und Spalte des Rechtecks ist Kandidat 4 und wegen Kandidat 4 alleine in einer Zeile und Spalte des Rechtecks ist Kandidat 1 dort im Ausschluss-Rechteck 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.

Ähnliches gilt für 020000043050307600006020000003040090000060000090150200000010300008506010710000050 mit 8 Lösungen, aber genau eine wird gefunden!

Beispiel eines Ausschluss-Rechtecks vom einfachen, aber recht häufigen Typ 1: Es gibt drei Zellen mit drei gleichen Paaren, und in der vierten Zelle gibt es zusätzliche Kandidaten, von denen deshalb einer gültig sein muss:

7   3   251 | | 246 252 9   | | 68 1   248 1249 19 8   | | 123467 1237 1467 | | 5   2469 249 1249 6   254 | | 8   1[2][5]3 145 | | 7   249 3   ... ... ... | | ... ... ... | | ... ... ...

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).

Beispiel eines Ausschluss-Rechtecks vom einfachen, jedoch weniger häufigen (außer bei Ausschluss-Schleifen) Typ 2: Es gibt zwei Zellen mit zwei gleichen Paaren, und in den anderen neben- oder übereinander liegenden Zellen gibt es einen zusätzlichen Kandidaten, der daher in einer der beiden Zellen gültig sein muss:

1   29 2359 | | 23467 3567 269 | | 79 [3]478 2[3]89 471 259 6   | | 23457 8   29 | | 1   3472 2[3]9 474 8   239 | | 12347 137 129 | | 5   3473 6   ... ... ... | | ... ... ... | | ... ... ...

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.

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 Ausschluss-Typ 5, der aber ziemlich selten vorkommt (55 Mal in etwa 250000 Fällen).

Beispiel eines Ausschluss-Rechtecks vom einfachen und auch relativ häufigen Typ 3: 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:

1237 8   5   | | 17 231 4   | | 6   12372 9   1237 9   137 | | 17 8   6   | | 5   [1]234[7] [1]4[7] 4   1267 1367 | | 9   234 5   | | 8   12373 17 ... ... ... | | ... ... ... | | ... ... ...

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.

Beispiel eines Ausschluss-Rechtecks vom einfachen und auch sehr häufigen Typ 4A: 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 nicht-zusätzlichen Kandidaten in einer Zeile, Spalte oder Box nur in diesen beiden Zellen vorhanden, kann der andere Kandidat dort gestrichen werden:

23689 1   689 | | 4589 79 3589 | | 367 2368 48 237[8]91 237[8]92 4   | | 89 6   389 | | 5   238 1   3568 3568 568 | | 2   47 1   | | 47 368 9   784 783 3   | | 569 1   569 | | 2   4   56 ... ... ... | | ... ... ... | | ... ... ...

Hier interessieren die Zusatzkandidaten nicht direkt - sie legen nur zwei der vier zu betrachteten Zellen des Ausschluss-Rechtecks fest. 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.

Übersicht der Ausschluss-Rechtecke-Typen (mit "ab" als die zwei gleichen Kandidaten):

• Typ 1:   ab - ab - ab - abc(de)   =>   ab streichbar bzw. c setzbar - [Recht häufig]
• Typ 2:   ab - ab - abc - abc   =>   Alle anderen c in betroffener Zeile bzw. Spalte und auch Box (wenn beide c in gleicher Box) streichbar
• Typ 3:   ab - ab - abcd - abe - cde - cde   =>   Quasi-N-Tupel, z.B. cde: Alle anderen cde in betroffener Zeile bzw. Spalte und/oder Box streichbar
• Typ 4:   ab - ab - abcd - abef, a sonst nirgendwo in der Zeile bzw. Spalte und/oder Box   =>   b in Zeile/Spalte/Box streichbar - [Sehr häufig]
• Typ 5:   ab - abc - abc - ab(c) mit c diagonal   =>   Alle anderen c in sichtbarer Zeile/Spalte/Box streichbar (Erweiterung von Typ 2) - [Extrem selten]
• Typ 6:   ab - abc - abd - ab mit c und d diagonal, a nur im Rechteck   =>   a streichbar aus Zellen mit Zusatzkandidat (Erweiterung von Typ 4) [Sehr selten]
• Typ 7:   ab - abc - abd - ab(e), a nur im Rechteck   =>   b streichbar aus gegenüber liegender Zelle mit Zusatzkandidat (offiziell: Verstecktes Rechteck) - [Am häufigsten]

Bei den 119100 gerechneten Sudokus traten Ausschluss-Rechtecke insgesamt fast 250000 Mal auf; Typ 1 und Typ 3 waren etwa 12000 Mal zu finden, Typ 2 etwa 5000 Mal (aber relativ viel häufiger bei den Ausschluss-Schleifen), Typ 4 (A+B) war mit 80000 Mal sehr häufig (davon Typ 4B 60000 Mal), Typ 5B mit 55 Mal am seltensten (Typ 5A wurde gar nicht gefunden), Typ 6 war mit knapp 1900 Mal im Gegensatz zu Hodokus Aussage doch relativ selten, und Typ 7 mit fast 140000 Mal am häufigsten; dabei ragten Typ 7F mit 61000 Mal und Typ 7B mit 33000 Mal stark heraus, danach kamen die Typen 7E und 7G.
Die Ausschluss-Rechtecke waren insgesamt mit 250000 Mal am häufigsten, die Quasi-Ausschluss-Rechtecke traten 20000 Mal auf, die 6er-Ausschluss-Schleifen 3300 Mal und die 8er-Ausschluss-Schleifen 250 Mal, 10er- und 12er-Ausschluss-Schleifen jeweils etwa 55 Mal, 14er-Ausschluss-Schleifen noch 24 Mal.

Beispiel mit Typ 1: 180074000000800900500090100870105203020907080000408700200000000090003005001740000

Beispiel mit Typ 2: 003407600000000200709263000010000060005070400000000800500630100000008030800001000

Beispiel mit Typ 3 mit 2-Tupel: 000000000000001023045060000000000047000000560800009000000000700000540000200000009

Beispiel mit Typ 3 mit 3-Tupel: 097000060000004050840200007000040390015000040000000000700485000000000405200730000

Beispiel mit Typ 3 mit 4-Tupel: 000600000037091406040000900003002040450000060060010007296000800000080700500020004

Beispiel mit Typ 3 mit 5-Tupel: 020400000000009120080000060208507000070004000900060310004005002007200000800030500

Beispiel mit Typ 3 mit 6-Tupel: 000005000020004010030080020000008400800600000090010705006000000950003060003000001

Beispiel mit Typ 4A: 100007860007008010800200009000000002400010000009005000608000000000050900000009304

Beispiel mit Typ 4B: 000000000000001002003004050000000460010007000080000030000080005006300000070000001

Beispiel mit Typ 5B: 103400000050709000000020004000005007600000090000007258092000000501090300000060900

Beispiel mit Typ 6: 000009000408300060175400200042100005007090000500020100600900002000080450001200003

Beispiel mit Typ 7A: 000000000000001002003040050000000600000000730250008000000600000100370000900000004

Beispiel mit Typ 7B: 000000000000000012003045000000000600004010300070280000000003040000006000010000007

Beispiel mit Typ 7C: 000008200070309010800000007040000081007000400190000065300090004010806050005203000

Beispiel mit Typ 7D: 000000000000005790285060003001000006400010009900430200300070061029300000000000000

Beispiel mit Typ 7E: 000000000000000001002034000000015004000600000074000080009000300100000000500008070

Beispiel mit Typ 7F: 000000000084005070250093001905000020040800100001030500526000004003400008000000090

Beispiel mit Typ 7G: 000450000056009000000000000000300050008070400910000367001006900090035008000000706

Beispiel mit Typen 2,3,4A,4B,6,7A,7E,7F,7G: 003050000400000000780000004010908000000061870000000015500800600000230090907004200

Beispiel mit Typen 4A,4B,7A,7B,7D,7E,7F,7G: 040000000300000067500900001006790030102300000000020905015000083200400000400030000

Quasi-Ausschluss-Rechtecke:

Das Konzept der Quasi-Ausschluss-Rechtecke wird hier eingeführt: Dies sind unvollständige Ausschluss-Rechtecke, z.B. wenn schon einige Zellen eindeutig besetzt wurden (dann Vermeidbare Ausschluss-Rechtecke genannt) oder (viel allgemeiner) einige Kandidaten in einer Zelle oder mehreren Zellen schon fehlen; diese wurden dann im Allgemeinen in einem vorhergehenden Ausdünnschritt eliminiert und können aber wieder (vorübergehend) eingesetzt werden, um ein Ausschluss-Verfahren zu ermöglichen. Man untersucht dazu die beiden Diagonalen in einem möglichen (Quasi-)Ausschluss-Rechteck: Ist in einer Diagonale eine Zahl bzw. ein Kandidat in beiden Zellen vorhanden, kann man diese Zahl wieder (vorübergehend) in die anderen beiden Kandidatenlisten eintragen. Relativ leicht erkennbar sind Quasi-Ausschluss-Rechtecke, wenn nur eine Zahl zusätzlich eingetragen werden muss; sind zwei zusätzliche Zahlen einzutragen, sind diese oft das gemeinsame Paar des Ausschluss-Rechtecks.

Bewertung: Hierbei gibt es 3 + N (zusätzlich eingesetzte Zahlen) Punkte mehr als bei dem entsprechenden Typ des Ausschluss-Rechtecks.

Beispiel eines Quasi-Ausschluss-Rechtecks:
Betrachte die Zeilen 2 und 3 und die Spalten 3 und 7:

8   379 79 | | 1     5     4     | | 6   37 2   4   2   17 | | 6   8   3   | | 15 9   57 6   13 5   | | 7   9   2   | | 13 8   4   ... ... ... | | ... ... ... | | ... ... ...

Man sieht, dass die 1 in der ersten Diagonale in beiden Kandidatenlisten vorkommt und somit in den Zellen der zweiten Diagonale hinzugefügt werden kann - hier an der Stelle der schon gefundenen, also nicht originalen (!) Zahl 5 in Zeile 3 und Spalte 3 - und dass die 5 in der zweiten Diagonale in beiden Kandidatenlisten vorkommt und somit den Zellen der ersten Diagonale hinzugefügt werden kann. Daraus wird dann ein Ausschluss-Rechteck mit 15 als gemeinsamem Kandidatenpaar, wobei die hinzugefügten Kandidaten in runde Klammern gesetzt werden:

8   379 79 | | 1     5     4     | | 6   37 2   4   2   1(5)71 | | 6   8   3   | | 1[5]2 9   57 6   13 (1)54 | | 7   9   2   | | 13(5)3 8   4   ... ... ... | | ... ... ... | | ... ... ...

Da nun der Kandidat 1 alleine in einer Zeile und Spalte des Rechtecks liegt (nach Typ 7), kann der Kandidat 5 dort im Ausschluss-Rechteck gestrichen werden.

Für die Quasi-Ausschluss-Rechtecke gibt es die gleichen 7 Typen wie bei den normalen Ausschluss-Rechtecken. Typ 5 wurde bisher nur 1 Mal beobachtet!
Ähnliche Anteil-Verhältnisse wie bei den Ausschluss-Rechtecken gelten auch bei den Quasi-Ausschluss-Rechtecke. Die Typen 1, 4A, 4B, 7B. 7F und 7G waren etwa 2500 bis 3000 Mal zu finden, Typ 5 mit 25 Mal und Typ 6 mit 66 Mal lagen wieder am Ende.

Beispiel mit Typ 1: 100000000000100302009602050010004006000005020078000940000040208000000000930070000

Beispiel mit Typ 1 (Vermeidbares Rechteck): 050000000060504200008071000400003608000000000890100700300000000000207010072030090

Beispiel mit Typ 2: 003000000006709020080003400200010050075000300000000070007005894040000200060300000

Beispiel mit Typ 2 (Vermeidbares Rechteck): 085000060000004700030000100000000050600043000070820300000459670000000000904160003

Beispiel mit Typ 3 mit 2-Tupel: 100000709006080020080100000037000014000300000905000008000007250000901000060030900

Beispiel mit Typ 3 mit 3-Tupel: 070006000000000000243500006000320050019000000520000180007040200400090800002013045

Beispiel mit Typ 3 mit 4-Tupel: 100000609000000070080002004000000300090016000514000000002870005000000720071040800

Beispiel mit Typ 3 mit 5-Tupel: 100056000000000023000000004000908630007204008060000000070500096000031070800000000

Beispiel mit Typ 3 mit 6-Tupel: 010400096700060000900005040370800004000100200400009070080250000000000008650000020

Beispiel mit Typ 3 (Vermeidbares Rechteck): 004500130000020000800007600070143508500070004010805000037001000190400000000000300

Beispiel mit Typ 4A: 100000709006080103000000005004300008000000000930010607002600000600072900800500000

Beispiel mit Typ 4B: 000000000000001002003000040000000005000006300020040070000020080006050000701000600

Beispiel mit Typ 5A: 000000000000000012003045000000000600004000300070801000000030460000200000010700000

Beispiel mit Typ 5B: 007200500000000042090000600700430150001670298586190000000000000002003070018560000

Beispiel mit Typ 6: 120056000000000123000000004000908600007004018060000000000502096000031070800000000

Beispiel mit Typ 7A: 120006000050709020009000060000060800000001050670000900500000040801030200000500370

Beispiel mit Typ 7B: 000006248060080930304902510006800072000000095500690000030000759600009001090400000

Beispiel mit Typ 7C: 006020050200009000000608004019000800400000001003000790300200000000500002060070900

Beispiel mit Typ 7D: 000004000005007600108500270000006000300000082509048100050000010801090720600070000

Beispiel mit Typ 7E: 003400000000080023709103005000300078060000900910008000002074800034005090000000000

Beispiel mit Typ 7F: 000050009006008003700203000014800000000000070800000020508000000630004000040000156

Beispiel mit Typ 7G: 120406000006009100080000005015000300000640000000000802001200008000000004940000670

Beispiel mit Typen 1,3,4A,4B,7D,7E,7F: 123000000000100300000000450040500008600000004900003100000804000092301000060070000

Ausschluss-Schleifen:

Die Erweiterung der Ausschluss-Rechtecke sind Ausschluss-Schleifen: Ausschluss-Schleifen sind 2*N Zellen, die in N verschiedenen Zeilen, N verschiedenen Spalten und N (!) verschiedenen Boxen liegen und in allen diesen Zellen neben anderen Kandidaten zwei gleiche Kandidaten haben (siehe z.B. http://home.arcor.de/r.sudogu/r_tec/UniqueLoop.html). Hier wurden alle Versionen mit 6, 8, 10, ... 18 Zellen programmiert; 18er-Ausschluss-Schleifen wurden aber noch nie beobachtet.
Analog den Quasi-Ausschluss-Rechtecken gibt es auch Quasi-Ausschluss-Schleifen. Hier wurden der Einfachheit halber nur einfache 6er-Quasi-Ausschluss-Schleifen programmiert, da diese noch relativ häfig sind - einfach heißt, dass nur ein zweiter Kandidat in einer der 6 Zellen fehlt.

Bewertung: Hierbei gibt es 8, 10, 14, 16 Punkte entsprechend dem Typ der 6er-Ausschluss-Schleife; bei 8er-Ausschluss-Schleifen gibt es jeweils 2 Punkte mehr, usw.
Bei einer 6er-Quasi-Ausschluss-Schleife gibt es 3 + N (zusätzlich eingesetzte Zahlen - zur Zeit immer 1) Punkte mehr als bei dem entsprechenden Typ der 6er-Ausschluss-Schleife.

Übersicht der 6er-Ausschluss-Schleifen-Typen bei 2832 Sudokus (mit "ab" als die zwei gleichen Kandidaten):

• Typ 1:   ab - ab - ab - ab - ab - abc(de)   =>   ab streichbar bzw. c setzbar
• Typ 2:   ab - ab - ab(c) - ab(c) - abc - abc   =>   Alle anderen von (abc -) abc - abc aus sichtbaren c in Zeile/Spalte streichbar - [Relativ häufig]
• Typ 3:   ab - ab - ab - ab - abcd - abe - cde - cde   =>   Quasi-N-Tupel, z.B. cde: Alle anderen cde in betroffener Zeile bzw. Spalte und/oder Box streichbar - [Sehr selten]
• Typ 4:   ab - ab - ab - ab - abcd - abef   =>   a bzw. b streichbar, wenn nicht in gleicher Zeile/Spalte/Box

Beispiel mit Typ 1: 000000700067080001400170000920004080100009030600700920006410070800200016712653098

Beispiel mit Typ 2A: 020406709006000100709000000000010090000938072005002004060000800502000030010000000

Beispiel mit Typ 2B: 000602090070001000000000216030060720000073800081009060107528900590007600000396000

Beispiel mit Typ 2C: 000000000000000012003004000000001000004050000006000370000700400010000000250600800

Beispiel mit Typ 3 mit 2-Tupel: 014000760000106000607000201030405080000060000070908020700804005000301000093000410

Beispiel mit Typ 3 mit 3-Tupel: 009473010560008900100900400700640050040000000251000000005200090308000027000030000

Beispiel mit Typ 3 mit 4-Tupel: 010000600400600030600079000070000020000020003080106009000508001120000000030700000

Beispiel mit Typ 3 mit 5-Tupel: 004069020000030875000500000900320164000000937000607008006080500000000006305976480

Beispiel mit Typ 3 mit 6-Tupel: 000000000000000012003045000000004000000100006005000300020000000070003800610700000

Beispiel mit Typ 4A: 000000001000000023004005000000004000030000006500007800000030000007900400010020000

Beispiel mit Typen 2A,3,4A: 000400080006780000000030500200690000300000057000000016502000000070010003000840000

Beispiel mit Typen 3,4A,4B: 000006080000009102700030500000500000068102090000000068042000907800000000037000000

6er-Quasi-Ausschluss-Schleifen

In 15 Sudokus wurden 6er-Quasi-Ausschluss-Schleifen gefunden:

Beispiel einer 6er-Quasi-Ausschluss-Schleife mit Typ 1: 000006080000009102700030500000500000068102090000000068042000907800000000037000000

Beispiel einer 6er-Quasi-Ausschluss-Schleife mit Typ 2B: 060002008003000004520001000248090006000010000000006430080007001030040020010200340

Beispiel einer 6er-Quasi-Ausschluss-Schleife mit Typ 4A: 000000000000000001002034000000000350000600200070180000000500002030000400680000000

Übersicht der 8er-Ausschluss-Schleifen-Typen bei 236 Sudokus (mit "ab" als die zwei gleichen Kandidaten):

• Typ 1:   ab - ab - ab - ab - ab - ab - ab - abc(de)   =>   ab streichbar bzw. c setzbar
• Typ 2:   ab - ab - ab - ab - ab(c) - ab(c) - abc - abc   =>   Alle anderen von (abc -) abc - abc aus sichtbaren c in Zeile/Spalte streichbar - [Relativ häufig]
• Typ 3:   ab - ab - ab - ab - ab - ab - abcd - abe - cde - cde   =>   Quasi-N-Tupel, z.B. cde: Alle anderen cde in betroffener Zeile bzw. Spalte und/oder Box streichbar - [Sehr selten]
• Typ 4:   ab - ab - ab - ab - ab - ab - abcd - abef   =>   a bzw. b streichbar, wenn nicht in gleicher Zeile/Spalte/Box

Beispiel mit Typ 1: 086002000000001906050009002503000000000000000000000189000800010302500000000100760

Beispiel mit Typ 2A: 700890204200304000304265900070050003806409051500000028000000000400007506050106002

Beispiel mit Typ 2B: 001804700003090000000000600710460000002317000364200000000072530000000104020000080

Beispiel mit Typ 2C: 000000001000000020003004000000003500010000060700080090000200003006000400500100000

Beispiel mit Typ 3: 000050000006100207089000000200000500300090000900700046030006000004200000000004961

Beispiel mit Typ 4A: 100007600450000030009203000000018090030940008000000065008004000000300010002000500

Beispiel mit Typen 3 (3 Mal) und 4A: 390000007004003050705000040009000000800600030406000021047280693613904002028530010

10er-, 12er- und 14er-Ausschluss-Schleifen

Da 8er-Schleifen schon recht selten sind, treten 10er-, 12er und 14er- (und längere) Schleifen in der Praxis selten auf. Der Rechenaufwand ist aber bei 8er-Schleifen schon relativ hoch; es kann daher durch einen Radio-Button festgelegt werden, dass keine 8er- und längere Schleifen gesucht werden sollen.

Mit etwas mehr Aufwand wurden auch Sudokus mit 10er-, 12er- und 14er-Ausschluss-Schleifen gefunden.

Hier einige Beispiele für einige der 55 Sudokus mit 10er-Schleifen:

10er-Schleifen-Beispiel mit Typ 1: 000050089006100000009000010200300000005000900004600750030000270000002500900040030

10er-Schleifen-Beispiel mit Typ 2A: 094831000785062100000740002000590001020016008430007000000020850010008600002000000

10er-Schleifen-Beispiel mit Typ 2B: 000000001000002003045006000000000040000073000006000850000400010020000000300010000

10er-Schleifen-Beispiel mit Typ 3: 100000000050080200700632004210063000000000000508004000000000008800900027040020036

10er-Schleifen-Beispiel mit Typ 4A: 103007009450000200700000000060000000005008002000203040000090000008000030002701860

Und sogar 12er-Schleifen, aber nur Typ 2, dafür bei sogar 56 Sudokus:

12er-Schleifen-Beispiel mit Typ 2A: 000000000000000012003045000000000400060000007820100009000200000004000500030080000

12er-Schleifen-Beispiel mit Typ 2B: 000000000000000001002034000000000000030002040150600700000008000000100005074000030

12er-Schleifen-Beispiel mit Typ 2C: 000456009400000100009200000200000000300900000060000357000000600040579000000040020

Und tatsächlich ein paar 14er-Schleifen, aber auch nur Typ 2, und das bei 24 Sudokus:

14er-Schleifen-Beispiel mit Typ 2A: 000000000000000012000034000000000300001050000067100400000200070340000600800000000

14er-Schleifen-Beispiel mit Typ 2B: 000000000000001002003000040000005001004020000060000070000400890100000000500007020

Fast eine 16er-Schleife (bei 16 Sudokus):

Sudoku mit Fast-16er-Schleife mit Typ 2: 000000000000001002034000050000000006007340000280000001000500030100002000600000000
Dabei würden 3 Zellen der Schleife den Kandidaten 5 in Zeile 8 und Spalte 7 löschen - wenn nicht die Zelle in Zeile 2 und Spalte 1 die 5 hätte:
Fast-16er-Ausschluss-Schleife Typ 2B für (1:1 - 1:7 - 4:7 - 4:8 - 8:8 - 8:2 - 7:2 - 7:6 - 3:6 - 3:9 - 9:9 - 9:5 - 6:5 - 6:4 - 2:4 - 2:1)79 gefunden: Gemeinsam sichtbarer Kandidat 5 fast streichbar

Sehr schwierige Sudokus

Die Punktzahlen sind so einigermaßen den Schwierigkeitsgraden angepasst. Sie hängen aber auch, jedenfalls beim nicht-synchronen Ausdünnen, von der Reihenfolge im Programm ab - so ergibt eine andere Reihenfolge im Suchen von Mustern in den Resten etwas andere Werte. Im nicht-synchronen Fall wird nur der gefundene Ausdünnschritt gewertet, wobei im pseudo-synchronen Fall noch Extra-Punkte hinzukommen, wenn es wenig Alternativen zu diesem Schritt gab. Im synchronen Fall werden aber alle Ausdünnschritte mitgezählt, egal, ob sie am Ende etwas bringen oder nicht. Aber das weiß man ja auch beim Lösen mit Hand vorher nicht...

Ab etwa 100 Punkten wird es interessant, über 125 Punkte ist es schon schwerer, über 150 Punkte wirklich schwer, und über 200 Punkte ist schon eine Herausforderung. Der Mittelwert aller Sudokus liegt bei den einfachen Sudokus (ohne Ausdünnung) bei 92 Punkten (maximale Anzahl bei 89 Punkten, siehe Kurve als PDF-Bild), und bei den nicht-trivialen Sudokus (mit Ausdünnung) bei 156 Punkten (maximale Anzahl bei 132 Punkten, siehe Kurve als PDF-Bild).

Hier einige der wohl schwierigsten Sudokus, die noch mit diesem Programm gelöst werden können - alle im pseudo-synchronen Verfahren gerechnet, wobei bis zu 190 Extra-Punkte gefunden wurden:

• 483 Punkte (bei pseudo-synchroner Bestimmung inklusive 190 Extra-Punkten) aus 23 Zahlen - A: 1, B: 0, C: 0, D: 0, E: 28, F: 29, Ausdünnschritte: 27, Zeilen-/Spalten-Tests: 4, Box-Tests: 5, N-Tupel: 7 (maximal Quadrupel), Einzelzahl-Ketten: 2 (maximal 4 lang), Goldene Ketten: 9 (maximal 4 lang) - in 21.5/132.2sec:
  120000089050009000080000045001700060000003000000600002000004000590006300000031070
• 500 Punkte (bei pseudo-synchroner Bestimmung inklusive 65 Extra-Punkten) aus 24 Zahlen - A: 6, B: 3, C: 0, D: 0, E: 25, F: 23, Ausdünnschritte: 25, Zeilen-/Spalten-Tests: 4, Box-Tests: 0, N-Tupel: 4 (maximal Quadrupel), Einzelzahl-Ketten: 0, Goldene Ketten: 17 (maximal 12 lang) - in 22.4/117.8 sec:
  020000000000700023009100400000000076500230800804005000075040610000000000900008040
• 507 Punkte (bei pseudo-synchroner Bestimmung inklusive 125 Extra-Punkten) aus 23 Zahlen - A: 3, B: 2, C: 0, D: 0, E: 29, F: 24, Ausdünnschritte: 27, Zeilen-/Spalten-Tests: 5, Box-Tests: 1, N-Tupel: 4 (maximal Quadrupel), Einzelzahl-Ketten: 1 (maximal 4 lang), Goldene Ketten: 8 (maximal 7 lang), Ausschluss-Rechtecke: 0/0/0/3/0/0/3, Quasi-Ausschluss-Rechtecke: 0/0/0/2/0/0/0 - in 19.9/113.0 sec:
  003057009000100000009000004005006000800700000904800017010008020000200060040030000
• 532 Punkte (bei pseudo-synchroner Bestimmung inklusive 145 Extra-Punkten) aus 22 Zahlen - A: 8, B: 0, C: 0, D: 0, E: 29, F: 22, Ausdünnschritte: 33, Zeilen-/Spalten-Tests: 6, Box-Tests: 1, N-Tupel: 9 (maximal Doppel), Einzelzahl-Ketten: 5 (maximal 8 lang), Goldene Ketten: 9 (maximal 8 lang), Ausschluss-Rechtecke: 1/0/0/1/0/0/1 - in 94.6/(>300.0) sec:
  100050009000700020080003000000000000300090006004200800002904300000000000037062050
• 540 Punkte (bei pseudo-synchroner Bestimmung inklusive 165 Extra-Punkten) aus 24 Zahlen - A: 4, B: 2, C: 0, D: 0, E: 24, F: 27, Ausdünnschritte: 32, Zeilen-/Spalten-Tests: 4, Box-Tests: 1, N-Tupel: 8 (maximal Quadrupel), Einzelzahl-Ketten: 7 (maximal 6 lang), Goldene Ketten: 10 (maximal 7 lang), Ausschluss-Rechtecke: 0/1/0/0/0/0/1 - in 51.5/247.2 sec:
  120006000050700020009003000010060800000001050600008900000000040840030200000500370
• 542 Punkte (bei pseudo-synchroner Bestimmung inklusive 125 Extra-Punkten) aus 24 Zahlen - A: 7, B: 0, C: 0, D: 0, E: 27, F: 23, Ausdünnschritte: 34, Zeilen-/Spalten-Tests: 2, Box-Tests: 1, N-Tupel: 10 (maximal Tripel), Einzelzahl-Ketten: 10 (maximal 6 lang), Goldene Ketten: 6 (maximal 8 lang), Ausschluss-Rechtecke: 1/0/0/0/0/0/1, Quasi-Ausschluss-Rechtecke: 1/0/0/0/0/0/2 - in 61.7/278.2 sec:
  000050080000089103700000060010000050300004000590070000605200000870091006000000200
• 565 Punkte (bei pseudo-synchroner Bestimmung inklusive 90 Extra-Punkten - Dank an Glenn Fowler, ATT) aus 23 Zahlen - A: 7, B: 2, C: 0, D: 0, E: 29, F: 20, Ausdünnschritte: 27, Zeilen-/Spalten-Tests: 4, Box-Tests: 1, N-Tupel: 4 (maximal Quadrupel), Einzelzahl-Ketten: 1 (maximal 4 lang), Goldene Ketten: 17 (maximal 12 lang) - in 24.4/143.5 sec:
  103050000050009000080000004000060008008000072000290310004072000000004050030000800

63 Punkte: 000709510100500897957081602001090356345876921296135478418050709003918200029007180
70 Punkte: 205670030078934502009250700853496127702815603061723000024369870006587200087142306
80 Punkte: 001809570579001268800007901100080709287910056904070180718090605695708010002100897
90 Punkte: 000100300000000604900602807590000102600001003800006095058200970000080500376500200
100 Punkte: 000000000060950030500280001095307082206845019381090070654700190020009700000000020
110 Punkte: 000000003020300600803602004032400900480020100900500208090837462368040509000900001
120 Punkte: 000000000012043090065100000403000050107089300806000107001090745504000000079450630
130 Punkte: 000000000064203010002508004080100590709030160100000040320006450600451000051002006
140 Punkte: 000000000000000012000034000000000300001005040056100000000270006000800000740000000
150 Punkte: 000000000000000001002003040000000000000150006043007000000000038150600000600000070
160 Punkte: 000000000000000001002034000000001005003000040060070000000080920010000400500600000
170 Punkte: 000000000000000001002003004000000050000004000003006780000090200010500000640100000
180 Punkte: 000000000000000001002034000000000350000600200070180000000500002030000400680000000
190 Punkte: 000000000000000001002003040000002005004000000060010007000004320010000080070060000
200 Punkte: 000000000000000001002034000000000020050000034600100000000620700000800050074000000
210 Punkte: 000000000000000001002003040000002000010005006070000008000070030500400020600080000
220 Punkte: 000000000000000001002003040000005020010060000700000800000070006200010000504000030
230 Punkte: 000000000000000012003004000000005004062000000170000000000170060008000900400200000
240 Punkte: 000000000000000001002034000000002050030000006700100000000050020080000040160700000
250 Punkte: 000000000000000001002003040000000200010000500060074000000010060005000030008560000
260 Punkte: 000000000000000012000034000000000300001000000025100006000200000300070400700050080
270 Punkte: 000000000000000012003045000000000400010060500070100000000200080409003000500000000
280 Punkte: 000000000000000012003004000000000000005030400060700001000040600020000007100089000
290 Punkte: 000000000000000012003004000000000000005060300060120000000003075010000400800090000
300 Punkte: 000000000000000012003045000000000000000006705010080000000290040605000300700000000
310 Punkte: 000000000000000001002003040000005000003020000010000607000600050008000300060170000
320 Punkte: 000000000000001002034000050000050000006430000200000007000060830100000000700009000
330 Punkte: 000000001000001002003040000000005060004000300070200000000070800010000000250000007
340 Punkte: 000000000500080007097401020030000010000659000920000040010203000600070008000000000
350 Punkte: 000000000002608900064300052000000065201705030070030000000007000000086090700010028
360 Punkte: 000000001000001023004000000000002450000060070087000000000540000300000000600000008
370 Punkte: 000000000400089003000120465000000008000267010900500000000000806615030000002000000
380 Punkte: 020006000400080000009120005215000300000000050000000800000800030631002000000075090
390 Punkte: 000400700056000100000023000230500000008070630000001804000000200800002070072610000
400 Punkte: 006003000050000000400100700009006001030000020700400300003009006020080050100700400
411 Punkte: 003050780006009020000103060200000010008200600900010008004070000001805000070000500
420 Punkte: 000050009000000103789100000000834090000010200640000000560000807000007002030008010
439 Punkte: 090005000000000600100708020003009500060000000002010870050000900000006000007200001
444 Punkte: 103006009050000123709000400000300000007041000000600850340008007000230000800900000
459 Punkte: 120050700000009100000020405010000300090070000800600590308500000002940601000000000

Literatur (Allgemeine Lösungsstrategien)

• http://hodoku.sourceforge.net/de/techniques.php (Bernhard Hobiger)
• http://home.arcor.de/r.sudogu/sudogu.html (Rudi Lars)
• http://www.ahr-sudoku.de/solving.php/list/difficulty
• http://www.sudokuwiki.org/Getting_Started
• http://www.sudopedia.org/wiki/Solving_Technique
• http://www.sadmansoftware.com/sudoku/solvingtechniques.htm

Neustart

Ausgewählte (alte) Sudoku-Beispiele (von 24364 Sudokus)

Altes Programm (Loop) mit X-Wing

Nicht-synchrones Programm (Loop)

Variante mit Einbeziehung der Diagonalen

Variante: Farb-Sudoku

Impressum:
Angaben gemäß § 5 TMG:

Verantwortlich für den Inhalt dieser Webseite: Ingolf Giese

Fragen und Kommentare bitte an Ingolf Giesegsi.de, Homepage: http://www-aix.gsi.de/~giese/