Sudoku Solver
Auflistung aller Einzelschritte inklusive genauer Erklärungen und Punkte-Bewertung - mit Einzelzahl-Ketten, Goldenen Ketten und Ausschluss-Ketten (-Rechtecken und -Schleifen); NEU: mit offensichtlichen 2-Tupeln und mit Anzeigen aller Alternativen auch beim Ausdünnen
Geben Sie die Ausgangszahlen ein (1..9)
Prinzipen zur Lösung von Sudokus
Sudoku-Grundregel: Es sollen in jeder Zeile, in jeder Spalte und in jeder Box (3x3-Kästchen) alle Zahlen von 1 bis 9 genau einmal vorkommen. 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.
Dieses Programm benutzt 6 Lösungsverfahren mit verschiedener Punkte-Gewichtung, wobei für die Ausdünnung 6 verschiedene Analysemethoden (ebenfalls mit unterschiedlichen Punkten gewichtet) programmiert wurden.
Dabei wird im nicht-synchronen Verfahren nach einem Treffer immer wieder bei der einfachsten Methode begonnen, und zusätzlich in der Reihenfolge: Suche immer erst in Boxen (was wegen dem engeren Gesichtsfeld einfacher zu erkennen ist) - dadurch sind diese Fälle immer am häufigsten -, dann in Zeilen, zuletzt in Spalten. In den neuen synchronen Verfahren 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 Alternativen es gibt.
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). Das 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. 3D-Medusa) bzw. nahe einem Trial&Error-Verfahren liegen (allgemeine Zwangsketten, Forcing Chains). 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. Und: Ein "richtiges" Sudoku sollte auf jeden Fall eindeutig gelöst werden können.
Programm-Neuigkeiten
- Die 6 Untertypen bei den Ausschluss-Rechtecken Typ 7 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 13 Fällen - ohne Ausdünnen: 000000000000001002034000050000006300005000040200017000000800090100050000600000000
Mit 11 Fällen - dabei 1 Mal 20 Punkte beim Einsetzen: 000000089050780000080003004030805600001000000070034200000200050002067000000000300
Mit 7 Fällen - dabei 3 Mal 20 Punkte beim Einsetzen: 000000000000109200780030000060000004500610000000720800041900006005000090000000043
Mit 9 Fällen - dabei 20 Punkte sowohl beim Einsetzen als auch beim Ausdünnen: 000470000080020005007006900042700000010090070000000830209600100800040060000052000
Mit 5 Fällen - dabei 3 Mal 20 Punkte beim Ausdünnen: 000000000000001002003040050000000006000000207005030000000087090020900000160000000
Mit 5 Fällen - dabei 4 Mal 20 Punkte beim Ausdünnen: 100050000000009003000020465030600050007000200010002000002001000570360090900070030
Drei Sudokus konnten synchron nicht mehr gelöst werden, weil sich die Ausdünn-Methoden gegenseitig Kandidaten wegnehmen, was sich insbesondere bei den Ausschluss-Ketten auswirken kann.
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 voher - 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 Sudoku-Lösungsmethoden (A bis F)
- Einfachste Methode (Wert: 1 Punkt innerhalb Boxen, 3 Punkte innerhalb Zeilen/Spalten, 0 Punkte bei der 9. fehlenden Zahl; Farbmarkierung: Grün): 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.
Bemerkung: In knapp 95 % aller Lösungsschritte findet man eine Zahl (und den dazugehörenden Ort) mit dieser Methode, davon 90 % mit der Suche innerhalb von Boxen!
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.
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.
Beispiele mit vielen A-Fällen und hohen Punktzahlen:
47 wirkende von 79 A-Fällen (mit 134 Punkten): 004065000900000800000000000060900100005100020000800000890000000000070050200000000
50 wirkende von 83 A-Fällen (mit 129 Punkten): 780000001000430020000000000403500000000608000000000000060001000000000840000080700
45 wirkende von 77 A-Fällen (mit 147 Punkten): 720000080000500000000010000000200060001003000400000000800000301050690000000000200
36 wirkende von 69 A-Fällen (mit 167 Punkten): 000050100240000000000000700000400030100000800008000000000309020070000046000010000
- Einzig mögliche Zahl (Wert: 5 Punkte, Farbmarkierung: Blau): 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.
Beispiel: Die einzige Zahl an der Position Zeile 3 und Spalte 4 (mit kleinem x markiert) kann nur die Zahl 7 sein, weil alle anderen Zahlen schon in gleicher Zeile (1, 4, 8, 9), in gleicher Spalte (2, 5), bzw. in gleicher Box (1, 2, 3, 6) vorhanden sind.
Beispiele mit vielen B-Fällen:
21 wirkende von 27 B-Fällen - ohne offensichtliche Zeilen-/Spalten-Tests und 2-Tupel: 003000000001600800080025049002706080005000700060301200630590070009007500000000400
18 wirkende von 25 B-Fällen - ohne Ausdünnung: 000000019000000003020076000000950000310000085000037000000810040200000000760000000
12 wirkende von 15 B-Fällen - mit Ausdünnung: 020006009400080000700130000000000970690008300000017006008205000001000040000000600
- Erweiterte oder indirekte Dreier-Methode (Wert: 2 Punkte mal Anzahl der Begründungen, Farbmarkierung: Rot): Bestimme den Ort der dritten Zahl ohne genaue Kenntnis des Ortes der zweiten Zahl (entspricht dem hier offensichtlichen Zeilen-/Spalten-Test, siehe unter Ausdünnen):
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.
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).
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.
Beispiele mit vielen C-Fällen:
19 wirkende von 23 C-Fällen (2 Mal "und folgend", 1 Mal "und ... und folgend"): 000080010500000200600000000017000008000200600000000000030000087200406000000500000
21 wirkende von 26 C-Fällen (1 Mal "und ... und folgend"): 000008100000005000630000040400007002005000800100600003080000074000300000002100000
24 wirkende von 30 C-Fällen (4 Mal "und"): 000000000000000012003045000000000000000100067045000080000003500100000200600700000
5 wirkende von 12 C-Fällen (2 Mal "und", 1 Mal "und folgend", 1 Mal "und ... und folgend") : 030406250020307180000000000700102009250600300460083701800030012000000000070904800
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 ... und folgend ... und folgend") : 900600078852000900000008000009802103003090007200001009008030006090207000001000390
- Offensichtliche 2-Tupel (Doppel) (Wert: 5 Punkte, Farbmarkierung: Gelbgrün): 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öchen das Auffinden von Zahlen, ohne dass alle Kandidaten aufgeschrieben werden müssen. Dabei gibt es drei Arten:
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.
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.
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.
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:
20 wirkende von 38 D-Fällen (mit 27 Mal D1-3 und 8 Mal D0 und 3 Mal D4): 000400080006090037700032000000070000010905000890010070500000790002000413008000000
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): 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 "In Zeile 2 und Spalte 5 kann Zahl 8 gesetzt werden ... "): 003406000050000000000001504010000603000008900090020007500070002807000056000010070
- Vollständige Ausdünnung mit einzig auftretender Restzahl (alleine auftretender Kandidat) (Wert: 4 Basis-Punkte, Farbmarkierung: Lila): 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.
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.
- Vollständige Ausdünnung mit einstelliger Restzahl bzw. einziger Kandidatenzahl (Wert: 1 Basis-Punkt, Farbmarkierung: Braun): 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.
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.
Sechs Methoden zur Ausdünnung der Reste (I bis VI)
Der Begriff der Ausdünnung zur Verkürzung der Reste wurde im vorherigen Abschnitt unter Methode D schon erläutert. Im Allgemeinen sind, um eine Lösung zu finden, immer mehrere Ausdünnschritte notwendig (bis zu 23 direkt nacheinander wurden schon beobachtet!). Manche Schritte helfen dabei nicht zur Lösungsfindung, aber das weiß man vorher nicht.
Über die Hälfte aller hier berechneten Sudokus sind nur durch Anschreiben der Reste und anschließender Ausdünnung lösbar!
In den folgenden Beispielen werden oft nur Teile eines Sudokus mit entsprechenden Resten dargestellt, um das Ganze übersichtlicher zu machen; es sind Ausschnitte aus aktuellen Sudokus.
- 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:
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:
- 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:
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:
- 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):
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:
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.
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 vielen bzw. großen N-Tupeln:
11 wirkende von 21 N-Tupel (maximal 7-Tupel): 100050600000080207009030000030000000500900008008204000004000000600000701070000306
14 wirkende von 24 N-Tupel (maximal 6-Tupel): 100007009050100000080260000007000400314020000800000030000000040040900270000005360
12 wirkende von 25 N-Tupel (maximal 7-Tupel): 100407080006009030700200050231000900005000401000000000000010000000008002890700000
15 wirkende von 27 N-Tupel (maximal 5-Tupel): 003450009000109700080060000000090000014000000005320000000006908040000100000005062
- Einzelzahl-Ketten (Single Digit Pattern, Forcing X-Chain): Kette aus Resten, bei denen überall eine bestimmte Zahl vorkommt (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 Paare 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 Paar liegen; interessant ist hierbei, dass die anderen Kandidaten der jeweiligen Reste keine Rolle spielen. 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 Paar 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:
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 Paar 27-27 in Spalte 5, kann man mit dem zweiten Spaltenpaar (24-24) über Zeile 4 verbinden (die dritte 2 in dieser Zeile stört hier nicht). Das Zeilenpaar kann man als letzten Teil der Kette in der rechten oberen Box anschließen (das starke Paar 28-24 ist hierbei keine Notwendigkleit) 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 Paar ist), kann somit nicht in Zeile 4/Spalte 7 sein, muss also in Zeile 3/Spalte 7 sein (starkes Paar 24-24), also nicht in Zeile 1/Spalte 9, und muss daher in Zeile 1/Spalte 1 (starkes Paar 2389-28) sein. Damit erhält man:
Bisher wurde hier die X-Wing-Methode benutzt. Diese ist aber nur ein Sonderfall der Einzelzahl-Ketten-Methode, im Beispiel also die Ketten 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:
Die Erkenntnis, dass X-Wing nur ein Sonderfall der Einzelzahl-Ketten-Methode ist, erklärt auch, warum X-Wing relativ selten (gegenüber der Goldenen Kette) auftrat. Aber auch dieses Verfahren könnte noch mehr verallgemeinert werden...
Beispiele mit vielen bzw. langen Einzelzahl-Ketten:
17 wirkende von 63 Einzelzahl-Ketten (maximal 12 lang): 070608040006702300200000006012000487600070000057080960500000001709815604060407050
19 wirkende von 66 Einzelzahl-Ketten (maximal 10 lang): 300409010000020300079010008000700000014203760700001030400000970090060000020008001
4 wirkende von 45 Einzelzahl-Ketten (maximal 14 lang): 000000000000000012003045000000006500070000000120000080000271000000400000006000300
14 wirkende von 42 Einzelzahl-Ketten (maximal 16 lang): 000000000000000012003045000000006400010000000270000008000100000004000530020070000
- Goldene Kette (Golden 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 (nach wenigen anderen Ausdünnschritten):
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 vielen bzw. langen (wirkenden) Goldenen Ketten:
55 wirkende von 84 Goldenen Ketten (maximal 15 lang): 103050000050009000080000004000060008008000072000290310004072000000004050030000800
56 wirkende von 105 Goldenen Ketten (maximal 12 lang): 006003092009500030038001000900007400540030008007400000060270000000005300075009000
38 wirkende von 62 Goldenen Ketten (maximal 18 lang) - davon 32 in einem Ausdünnschritt: 023056000406009100000000000004600800010000006900370040002041005070000030000000902
21 wirkende von 48 Goldenen Ketten (maximal 19 lang): 050072000000000004009086025020000081600000050007205063300090008081004500040803070
30 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
- 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.
Bewertung: Hierbei gibt es 4, 5, 12, 10, 6, 10, 10 Punkte entsprechend dem Typ des Ausschluss-Rechtecks.
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.
Beispiel eines Ausschluss-Rechtecks vom einfachen, aber auch recht häufigen Typ 1:
Würde man die 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 Kandidat; 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.
Ü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 - [Am häufigsten]
- 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)
- Typ 7: ab - abc - abd - ab(e), a nur im Rechteck => b streichbar aus gegenüber liegender Zelle mit Zusatzkandidat (offiziell: Verstecktes Rechteck) - [Recht häufig]
Bei den 113700 gerechneten Sudokus traten Ausschluss-Rechtecke insgesamt fast 136000 Mal auf; Typ 1 war 13000 Mal (10%) zu finden, Typ 2 und Typ 3 etwa 4900 Mal (4%), Typ 4 war mit 76000 (56%) am häufigsten, Typ 5 mit 46 (0.03%) am seltensten, Typ 6 war mit 2000 Mal (1.5%) im Gegensatz zu Hodokus Aussage doch relativ selten, und Typ 7 mit 35000 Mal (25%) am zweit-häufigsten.
Ähnliche Verhältnisse gelten bei den Quasi-Ausschluss-Rechtecken, wobei allerdings Typ 5 nie aufgetreten war. Die Ausschluss-Rechtecke waren mit 92.6% am häufigsten, die Quasi-Ausschluss-Rechtecke hatten 4.4%, die 6er-Ausschluss-Schleifen 2.8% und die 8er-Ausschluss-Schleifen 0.2% Anteile.
Beispiel mit Typ 1: 000000000000000012003004000000000005000003600027010000000800300070000400650020000
Beispiel mit Typ 2: 000000001000001020003000000000040500010000300260007000000430000005080000070000060
Beispiel mit Typ 3: 000000001000001023004000000000000500000670400130000000000050700006040000200000008
Beispiel mit Typ 3: 000000000400009023789000400200000030000070516000018000007000000800000204042560070
Beispiel mit Typ 4: 000400600050009030009300540000600005610000000830500010000800794000003000001070000
Beispiel mit Typ 5: 103400000050709000000020004000005007600000090000007258092000000501090300000060000
Beispiel mit Typ 6: 120406700000000130000000500295800000007020000000004000002000890600001000004500200
Beispiel mit Typ 7: 100050000006009000080120004004600300000007010097000600000800000568000200040001076
Beispiel mit Typ 7 (7B,7D,7E): 004600090860190007000000006480060023070948060150070084600000000700029058030006100
Beispiel mit Typ 7 (3,4A,4B,7B,7F): 000000780050009000789000060015800000300217000000000402000092030802000000060040000
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 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. Oft sind die beiden neu einzutragenden Zahlen dann das gemeinsame Paar des Ausschluss-Rechtecks.
Bewertung: Hierbei gibt es 2 Punkte mehr als bei dem entsprechenden Typ des Ausschluss-Rechtecks.
Beispiel eines Quasi-Ausschluss-Rechtecks in den Zeilen 2 und 3 und den Spalten 3 und 7:
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:
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 allerdings bisher noch nicht beobachtet. Einige Beispiele:
Beispiel mit Typ 1: 000000000000000012000034000000000500001006000007000003030000400050070060800310000
Beispiel mit Typ 1: 050000000060504200008071000400003608000000000890100700300000000000207010072030090
Beispiel mit Typ 2: 609700000201080040070500020708000060300000001060000905020006090010090802000004306
Beispiel mit Typ 2: 085000060000004700030000100000000050600043000070820300000459670000000000904160003
Beispiel mit Typ 3: 900708100007030000000500402300090205070600000080050010006000004400003500000800000
Beispiel mit Typ 3: 004500130000020000800007600070143508500070004010805000037001000190400000000000300
Beispiel mit Typ 4: 800054367007900008532007190000040000058069070003800010000090000000708050680000739
Beispiel mit Typ 5: Bisher nicht gefunden (schon normale Ausschluss-Rechtecke vom Typ 5 sind extrem selten!)
Beispiel mit Typ 6: 000000000045203780070605020020806300000000070060500890082100500034070000000000000
Beispiel mit Typ 7: 120000600006100207080200000000300090091006000805000003000908006030000000000074005
Beispiel mit Typ 7: 000400089050109200700300000090008000030000020000035006008060570002000300010000000
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 die Versionen mit 6 und 8 Zellen programmiert; es geht wohl auch mit 10 oder 12 Zellen (bis theoretisch maximal 18 Zellen), was aber wohl extrem selten sein muss.
Bewertung: Hierbei gibt es 8, 9, 16, 14 Punkte entsprechend dem Typ der 6er-Ausschluss-Schleife; bei 8er-Ausschluss-Schleifen gibt es 2 Punkte mehr.
Übersicht der 6er-Ausschluss-Schleifen-Typen (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 - 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: 065000270008205400000709000802000307000050000004107500040503020009604700006000800
Beispiel mit Typ 2: 000215000100000008043908170054800610900000003032001780081306490300000001000182000
Beispiel mit Typ 3: 003000009400709000080000040060900070000020001500000408000500000842000007900600200
Beispiel mit Typ 4: 360009000000070080400610050100700200000040000005006001050087009090060000000200043
Übersicht der 8er-Ausschluss-Schleifen-Typen (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 - 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: 000000000000000012000034005000000000000006403017800000000700080300100000520000000
Beispiel mit Typ 2: 000000000000000012003045000000000000000006307140002000000010400007080900600000000
Beispiel mit Typ 3: 190008070006490008007010006670000002803700004502060030008000001030500020000006000
Beispiel mit Typ 4: 000000780050089000709000060015800000300207000000900402007092030802000000060048000
Da 8er-Schleifen schon sehr selten sind, sind 10er- (und längere) Schleifen in der Praxis kaum zu erwarten. Der Rechenaufwand ist aber bei 8er-Schleifen schon ziemlich hoch (im Mittel etwa 50 % der Gesamtlaufzeit); es kann daher durch einen Radio-Button festgelegt werden, dass keine 8er-Schleifen gesucht werden sollen.
Allgemeines (Stand Juni 2010)
Die Punktzahlen sind so einigermaßen den Schwierigkeitsgraden angepasst. Sie hängen aber auch von der Reihenfolge im Programm ab - so ergibt eine andere Reihenfolge im Suchen von Mustern in den Resten etwas andere Werte. Gerade die Bewertung beim Ausdünnen ist schwierig: es werden 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 50 Punkten wird es interessant, über 75 Punkte ist es schon schwerer, über 100 Punkte wirklich schwer, und über 125 Punkte ist schon eine Herausforderung. Der Mittelwert aller Sudokus liegt bei 106 Punkten (der Hauptwert liegt um 60 Punkte ohne Ausdünnung (siehe Kurve), und um 144 Punkte mit Ausdünnung (siehe Kurve)). Aktuelles Maximum mit schwer zu überbietenden 591 Punkten (sehr viel mehr Punkte sind mit diesen Methoden wohl kaum erreichbar?!), also das bisher am schwersten (hier) gelöste Sudoku:
- Bisher: 440 Punkte aus 23 Zahlen (erste einfache Schritte: 11, Verhältnis 7.6): - A: 48, B: 2, C: 2, D: 5, E: 1, Ausdünnschritte: 27, N-Tupel: 3 (bis Tripel), Einzelzahl-Ketten: 4 (maximal 8 lang), Goldene Ketten: 12 (maximal 10 lang) - in 4.3 sec:
000000070003805906050403080047000320000000000020000100000204050506100000080000000
- Neu (Dank an Michael Jentsch): 515 Punkte aus 25 Zahlen (erste einfache Schritte: 6, Verhältnis 9.2): - A: 46, B: 2, C: 1, D: 4, E: 3, Ausdünnschritte: 28, N-Tupel: 1 (bis Tripel), Einzelzahl-Ketten: 0, Goldene Ketten: 17 (maximal 11 lang) - in 5.1 sec:
507000040003100009000000800000503100002010950070004600006000000380000000009280306
- Neuer (Dank an Glenn Fowler, ATT): 591 Punkte aus 23 Zahlen (erste einfache Schritte: 9, Verhältnis 10.2): - A: 49, B: 1, C: 1, D: 1, E: 6, Ausdünnschritte: 29, N-Tupel: 3 (maximal Quadrupel), Einzelzahl-Ketten: 1 (maximal 4 lang), Goldene Ketten: 17 (maximal 12 lang) - in 5.8 sec:
103050000050009000080000004000060008008000072000290310004072000000004050030000800
- PS: Ohne Einzelzahl-Ketten, Goldene Ketten und Ausschluss-Rechtecken liegt das Maximum bei 218 Punkten aus 17 Zahlen (erste einfache Schritte: 2, Verhältnis 3.4): - A: 49, B: 4, C: 0, D: 8, E: 3, Ausdünnschritte: 20, N-Tupel: 4 (bis Quadrupel), Einzelzahl-Ketten: 0, Goldene Ketten: 0 - in 0.2 sec:
008000000000002540031060000000000070000400200063000000000000001500007000000080003
Das 440-Punkte-Sudoku wurde durch Reduzierung aller bis dahin gelösten etwa 9200 Sudokus in einem Aufwand von über 2100 Stunden Rechenzeit (insgesamt wurden fast 3 Millionen Sudokus durchgerechnet) gefunden... Reduzierung heißt hier: Lässt man aus einem Sudoku mit N Zahlen jeweils eine Zahl aus, so entstehen N Sudokus mit jeweils N-1 Zahlen, die alle berechnet werden. Gibt es dabei Lösungen, macht man die gleiche Prozedur mit dem berechneten Sudoku, das die höchste Punktzahl hat, usw., bis es keine Lösung mehr gibt.
Literatur:
Allgemeine Lösungsstrategien bei: http://www.sadmansoftware.com/sudoku/solvingtechniques.htm
oder bei: http://hodoku.sourceforge.net/de/techniques.php