- Kleinere Änderungen und Anpassungen (April 2014). Nach längeren Rechnungen erzeugt: Zwei Beispielseiten mit jeweils 4 Sudokus, die bei Option 1000 (asynchrone Rechnung mit einfachen offensichtlichen Zeilen-/Spalten-Tests und 2-Tupel) noch "leicht" mit Hand gelöst werden können:
4 Sudokus, 73 bis 78 Punkte, keine Ausdünnfelder
4 Sudokus, 88 bis 89 Punkte, 29 bis 30 Ausdünnfelder (maximal mit einfacher Bestimmung, also 2-Tupel, Zeilen-/Spalten-Tests, Box-Tests, einfache Ausschluss-Rechtecke wie Typ 1, 2, 3A)
Verbesserung der Beispiel-Sudokus und der Dokumentation der Ausschluss-Ketten (Mai 2014).
- Programmierung der optionalen nicht-synchronen und pseudo-synchronen direkten Lösungsmethoden (A bis F) mit der gleichen Option wie beim Ausdünnen; dabei werden bei A bis D nach jeweils 3 gefundenen Lösungen die Ergebnisse im Sudoku-Feld angezeigt, bei E bis F jeweils gleichzeitige F-Fälle.
Umbenennen einiger Ausschluss-Rechteck-Typen, deren Nomenklatur ab Typ 5 recht durcheinander ist. Und: Der alte Typ 7F war identisch mit dem alten Typ 4B... Zusätzlich wurde die Reihenfolge einiger Typen geändert, und die drei sehr ähnlichen alten Typen 7E, 7D und 7C (Analyse beider Hauptkandidaten) wurden zu 8A, 8B und 8C umbenannt. Bei allen Ausschluss-Schleifen wurden nun auch die Typen 7A-7C, 8A-8C und 6 programmiert.
Bemerkung: Es wurde immer wieder beobachtet, dass einige wenige Sudokus nach der Umstellung der Reihenfolge der Verfahren nicht mehr lösbar sind; umgekehrt wurden dann aber auch Sudokus gelöst, die vorher nicht gelöst werden konnten. Das liegt daran, dass ein Verfahren Kandidaten streicht, die für ein anderes Verfahren aber nützlich gewesen wären.
Neufestlegung der 6 Stufen beim synchronen Verfahren, auch entsprechend der veränderten Bewertung: 2-5, 5-8, 8-11, 11-14, usw. Punkte in den jeweiligen 3 Punkte breiten Bereichen.
Neufestlegung der Punktzahlen, z.B. 0.5 Punkte bei Methode F; N/2 statt N Punkte für das Anschreiben aller Kandidaten; 3.5 Punkte statt 3 Punkte beim Box-Test; bei N-Tupeln mit 2, 5, 8, ... (=3*N-4) Punkten werden bei höheren Tupeln die eventuell kleineren Punktzahlen für die versteckten M-Tupel mit 8, 11, 14 (=3*M+2) Punkten angerechnet; Vorziehen der einfach zu erkennenden Typen 1, 2, 5 und 3A der Ausschluss-Ketten; Goldene Ketten 6, 7, 8, ... (=N+3 statt 2*N) Punkte - auch bei Geschlossenen Goldenen Ketten; Einzelzahl-Ketten 8, 11, 14, ... (=1.5*N+2 statt 2*N) Punkte, auch bei Geschlossenene Einzelzahl-Ketten; jeweils 3 mehr Punkte für die Ausschluss-Schleifen. Umkehrung der Reihenfolge Einzelzahl-Ketten und Goldene Ketten, da Goldene Ketten einfacher zu finden sind. Bei Geschlossenen Goldenen und Einzelzahl-Ketten, die in etwa jedem 6.-12. Fall auftreten, können mehr Kandidaten gestrichen werden, weil jede der betroffenen Zellen Anfangspunkt sein kann; sie werden daher den nicht-geschlossenen Ketten vorgezogen. Bei Geschlossenen Einzelzahl-Ketten bekommt der einfacher zu erkennende Sonderfall X-Wing 7 statt 8 Punkte.
Neben der Angabe der Summe aller erreichten Punkte gibt es auch die sehr aussagekräftige 2-Norm oder Euklidische Norm, d.h. die Wurzel aus der Quadratsumme aller Punkte, bei der die höheren Punktwerte stärker zur Geltung kommen - das ist nicht so extrem wie die nun auch angeführte Tschebyscheff-Norm, also das Maximum der Punktwerte, wie sie z.B. bei SudokuExplainer benutzt wird.
Die Dokumentation wurde, insbesondere bei den Ausschluss-Ketten, stärker (unter fleißiger Mithilfe von Edgar K.) überarbeitet.
Die meisten Beispiel-Sudokus wurden noch nicht überarbeitet (September 2012 bis Februar 2013).
- Ein neues Programm zum Ausdrucken von jeweils 4 neu zufällig ausgewählten Sudokus auf einer Seite wird angeboten (Sudoku Print). Dabei kann man den Typ der Sudokus (entsprechend der Typen bei der Optionsangabe) und die minimale und maximale Punktzahl (beim nicht-synchronen Verfahren berechnet) angeben. Weiter: Die Höhe der Extra-Punkte bei den direkten Lösungsmethoden wurde verkleinert, da sie sich doch als weniger aussagekräftig gezeigt haben; auch andere Punktevergaben wurden minimal geändert. Außerdem werden nun alle gefundenen Schritte mit Nummern ausgegeben (Juli 2012).
Bei neuen Rechnungen mit Zählungen aller wirkenden und nicht-wirkenden Ausdünnschritte wurden beim nicht-synchronen (bzw. voll-synchronen) Verfahren bei nun fast 136000 nicht-trivialen Sudokus für die 20 beim nicht-synchronen Verfahren häufigsten Verfahren (98.6 % bzw. 89.7 % aller Ausdünnschritte) gefunden:
- 145492 (349792) Zeilen-/Spalten-Tests
- 142446 (166399) 2-Tupel
- 102836 (813538) 4er-Einzelzahl-Ketten
- 61144 (143920) 3-Tupel
- 51877 (124050) 3er-Goldene Ketten
- 44429 (259984) 4er-Goldene Ketten
- 40939 (341923) Box-Tests
- 29908 (229672) 5er-Goldene Ketten
28997 (362990) Ausschluss-Rechtecke Typ 1 bis 7G (Gesamtsumme) - 15690 (231853) 6er-Goldene Ketten
- 14602 (305685) 6er-Einzelzahl-Ketten
- 7715 ( 87533) Ausschluss-Rechtecke Typ 4B
- 7641 ( 96433) 4-Tupel
- 5954 (167762) 7er-Goldene Ketten
- 5129 ( 19380) Ausschluss-Rechtecke Typ 1
- 3318 ( 18452) Ausschluss-Rechtecke Typ 3
- 3309 ( 45611) Ausschluss-Rechtecke Typ 7B
- 3212 ( 32322) Ausschluss-Rechtecke Typ 4A
- 2062 (116869) 8er-Goldene Ketten
- 1619 ( 7931) Ausschluss-Rechtecke Typ 2
- 1507 ( 46530) 5-Tupel
- 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 sollte 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:
- 137629 (202237) Zeilen-/Spalten-Tests
- 132991 (105136) 2-Tupel
- 88768 (503708) 4er-Einzelzahl-Ketten
- 58036 (83028) 3-Tupel
- 45433 (94619) 3er-Goldene Ketten
- 39695 (189050) 4er-Goldene Ketten
- 35611 (208952) Box-Tests
- 27575 (181527) 5er-Goldene Ketten
- 14655 (182539) 6er-Goldene Ketten
- 10431 (180788) 6er-Einzelzahl-Ketten
- 7451 (61588) Ausschluss-Rechtecke Typ 4B
- 6011 (52481) 4-Tupel
- 5701 (136437) 7er-Goldene Ketten
- 4821 (12909) Ausschluss-Rechtecke Typ 1
- 3173 (33958) Ausschluss-Rechtecke Typ 7B
- 3061 (21045) Ausschluss-Rechtecke Typ 4A
- 2801 (12066) Ausschluss-Rechtecke Typ 3
- 1921 (94727) 8er-Goldene Ketten
- 1471 (5115) Ausschluss-Rechtecke Typ 2
- 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 K.). 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 (und 105 Extra-Punkten) - ohne Ausdünnen: 000000000000001002034000050000006300005000040200017000000800090100050000600000000
Mit 10 Fällen (und 105 Extra-Punkten) - mit Ausdünnen: 000000089050780000080003004030805600001000000070034200000200050002067000000000300
Mit 9 Fällen (und 115 Extra-Punkten) - dabei 3 Mal 20 Punkte beim Einsetzen und 1 Mal beim Ausdünnen: 000470000080020005007006900042700000010090070000000830209600100800040060000052000
Mit 4 Fällen (und 60 Extra-Punkten) - 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 Goldenen 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) wurden 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 - was 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 wurde bisher keine Kette 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 neu 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 Ketten 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 (Dezember 2008).
- Programmierung der Ausdünn-Methoden X-Wing und Goldene Kette (Februar 2008).
- Programmierung der einfachen Ausdünn-Methoden N-Tupel, Box-Tests und Zeilen-/Spalten-Tests (Mai 2007).
- Programmierung aller einfachen direkten Methoden (November/Dezember 2006).
- Erste Version des Sudoku-Programms (August/September 2005).
posteo.de, Homepage: https://www.sarahandrobin.com/ingo/