posteo.de, Homepage: https://www.sarahandrobin.com/ingo/Absolut FALSCH ist die oft benutzte Aussage, dass ein Sudoku mit wenigen Ausgangszahlen schwieriger ist als ein Sudoku mit vielen Ausgangszahlen. Viele Zeitungen, Zeitschriften und Bücher, die Sudokus anbieten, gehen von dieser unsinnigen Annahme aus, oft z.B. bei 33-36 Ausgangszahlen mit der Bezeichnung "einfach" oder "leicht", bei 29-32 Ausgangszahlen mit der Bezeichnung "mittel" und bei 25-28 Ausgangszahlen mit der Bezeichnung "schwer". Aber es gibt sehr viele Sudokus mit 50 oder mehr Ausgangszahlen, die wirklich schwierig sind. Natürlich sind Sudokus mit 64 oder mehr gegebenen Zahlen im Allgemeinen leicht lösbar.
Fast alle Sudokus aus dem Kapitel "Sehr einfache (leichte) und sehr schwierige (schwere) Standard-Sudokus" haben 17 bis 28 Ausgangszahlen, die wirklich schwierigen haben oft 23 bis 25 Ausgangszahlen.
Es kommt also nur auf die spezielle Verteilung der gegebenen Zahlen an, ob ein Sudoku leicht oder schwierig ist.
Das kann man aber einem Sudoku nicht ansehen. Die "wirkliche" Schwierigkeit kann nur durch ein Programm nachträglich ermittelt werden, da sie vorher bei der Konstruktion des Sudokus nicht festlegbar ist.
Interessant ist eine Untersuchung, ob ein Standard-Sudoku schwierig ist, wenn von den möglichen 9 verschiedenen Ausgangszahlen (1 bis 9) eine Zahl gar nicht vorkommt. Das ist bei etwa 7.3 % aller Sudokus der Fall (260000 von 3.55 Millionen Sudokus). Es ist sogar fast das Gegenteil der Fall, wenn auch nur sehr schwach: Etwa 72 % der Sudokus mit nur 8 verschiedenen Ausgangszahlen haben Punktzahlen bis 56 Punkte ("noch einfach"), bei den Sudokus mit allen Zahlen (1 bis 9) in den Ausgangszahlen sind es "nur" 70 %.
Beispiel mit der fehlenden 8 in den 26 Ausgangszahlen mit 0 Punkten: 000000000000000001000234000051000067090500200340009005030700010005040609960001003
Eine andere Untersuchung, ob die Anzahl der Zeilen und Spalten, die keine Ausgangszahlen haben, eine Rolle spielt, zeigt auch kein klares Bild. Nur in knapp 0.5 % der 3.55 Millionen Sudokus findet man überhaupt 3 oder mehr Zeilen/Spalten, die keine Ausgangszahlen haben. Bei 412 = 0.01 % der Sudokus gibt es erstaunlicherweise 6 Zeilen und Spalten ohne Ausgangszahlen; die Punktzahlen liegen relativ hoch (bis 1320, dem hier festgestellten höchsten Wert), und sehr wenig Sudokus haben weniger als 10 Punkte (Mittelwert über 200). Aber bei den zweit- und dritt-schwierigsten Sudokus liegen in allen Zeilen und Spalten Ausgangszahlen vor. Also kann man auch in diesem Fall keine allgemeinen Schlüsse auf die Schwierigkweit eines Sudokus bilden.
Beispiel des extrem schwierigen Sudokus mit 6 Zeilen und Spalten ohne Ausgangszahlen mit 1320 Punkten und 66 Ausdünnschritten, darunter 4 Goldenen Ketten, 14 Einzelzahl-Widerspruchs-Ketten, 32 Widerspruchs-Ketten und 6 Mal Bowman's Bingo: 000000000001203400020105060064000180000000000087004920010308050009702300000000000
Einfaches optisch sehr ähnliches Beispiel mit 6 Zeilen und Spalten ohne Ausgangszahlen mit nur 6 Punkten: 000000000020809370037405020079100280000000000058904130002708650045306700000000000
Hier zwei Beispiele, bei denen der Austausch nur einer Stelle eines Sudokus zu einem extrem unterschiedlichen Schwierigkeitsgrad führt:
Super einfach lösbar (13 Punkte): 000006002009040050070100300005009006020060030600870000004000900050080010800700004
Ersetzt man die "7" in Zeile 6 und Spalte 5 hier in eine "2" in Zeile 7 und Spalte 5 führt das zu einem sehr schwierigen Sudoku (858 Punkte) mit 51 Ausdünnschritten, darunter 6 Goldenen Ketten, 6 Einzelzahl-Widerspruchs-Ketten und 26 Widerspruchsketten: 000006002009040050070100300005009006020060030600800000004020900050080010800700004
Super einfach lösbar (10 Punkte): 000000000001203400020105060064000180030000000087000920010308050009702300000000000
Ersetzt man die "3" in Zeile 5 und Spalte 2 hier in eine "4" in Zeile 6 und Spalte 6 führt das zu einem extrem schwierigen Sudoku (1320 Punkte) mit 66 Ausdünnschritten, darunter 4 Goldenen Ketten, 14 Einzelzahl-Widerspruchs-Ketten:, 32 Widerspruchs-Ketten und 6 Mal Bowman*s Bingo: 000000000001203400020105060064000180000000000087004920010308050009702300000000000
Eines der wenigen bekannten Programme, bei denen die Schwierigkeit eines Sudokus bestimmt wird, ist der "Sudoku Explainer von Nicolas Juillerat" von 2006/2007. Er gibt eine Punktzahl für den Lösungsschritt mit der maximalen Schwierigkeit aus - zwischen 1.0 (Hidden Single) und 11.9 (Contradiction Forcing oder Region Forcing).
Einen ganz anderen Ansatz zeigt die Software "Standard-Sudoku Solver". Hier wird jeder Lösungsschritt bewertet, und die Summe aller dieser Einzelbewertungen (Punkte) ergibt eine Gesamtzahl, die als "Schwierigkeit" bezeichnet wird - mit 0 bis etwa 1000 Punkten (bei der Option 2001 oder NUR BEWERTUNG). Denn ein Sudoku mit vielen recht schwierigen Lösungsschritten ist bestimmt schwieriger als eines mit nur einem maximalen Schwierigkeitsgrad. Bei diesem Programm werden Zusatzpunkte addiert, wenn nach den ersten einfachen Lösungsschritten die Kandidatenlisten erstellt werden müssen. Natürlich gibt es keine absolute Regel, bei welchem Schritt-Typ (z.B.: Einzige Position einer Zahl, Einzelzahl-Kette, Ausschluss-Rechteck oder Widerspruchs-Kette) wieviel Punkte zur Bewertung genommen werden sollten (im Bereich von 0 bis 36 Punkten), aber es ist eine Sache der Erfahrung - und letztlich auch des Geschmacks. Nach jahrelangen Überlegungen und Sudoku-Lösungen wurde hier ein sehr fein abgestuftes System erarbeitet - Einzelheiten siehe "Punktevergabe".
Zusätzlich zu der Punkte-Summe wird auch die Wurzel aller Punkte zum Quadrat (Euklidische Norm) ausgegeben; das ist als Kompromiss zur einfachen Maximum-Bewertung zu verstehen, die aber auch angegeben wird (mit den meisten Maximum-Werten zwischen 17 und 19, selten über 30).
Analyse der Sudokus mit 17 Ausgangszahlen, gesammelt von Gordon Royle:
Bis 2009 hat Gordon Royle, Professor an der University of Western Australia, alle verfügbaren Sudokus mit 17 Ausgangszahlen zusammengestellt, wobei die Sudokus in eine normierte Darstellung umgeformt wurden, um mehrfache auszuschließen. Außer diesen 49151 Sudokus wurden bis 2019 nur noch 7 weitere Sudokus gefunden (siehe Gordon Royle), wobei der Aufwand, weitere Sudokus mit 17 Ausgangszahlen zu finden, enorm ist. Die Daten wurden auf Gordon Ryle's Zip-File gefunden.
Das Problem der Schwierigkeits-Beurteilung sieht man am besten an den Sudokus mit nur 17 Ausgangszahlen (dem Minimum) - von denen oft behauptet wird, dass sie sehr schwierig sind: 42.8 % der 49158 Sudokus mit 17 Ausgangszahlen sind mit den sehr einfachen direkten Methoden lösbar; rechnet man zu den einfachen Methoden auch die offensichtlichen Zeilen-/Spalten-Tests und offensichtlichen 2-Tupel/Doppel hinzu, sind sogar über vier Fünftel (82.4 %) einfach - also ohne Ausdünnen - lösbar! Nur etwa 0.1 % sind mit diesem Programm bisher nicht lösbar und etwa 17.6 % sind mit bis zu 32 Ausdünnschritten lösbar (von denen auch nur 1.0 % mehr als 120 Punkte haben, also wirklich schwierig sind)!
Man sieht auch, dass bei den meisten Sudokus mit wenigen Ausgangszahlen wenigstens einige Zahlen schnell gefunden werden können, ehe man ins Stocken kommt - und dann fängt die Schwierigkeit an, also erst bei einer höheren Anzahl von noch nicht gefundenen Zahlen. Bei allen wirklich schwierigen Sudokus mit 17 Ausgangszahlen mit mehr als 120 Punkten (500 Sudokus) gibt es bei 82 % der Sudokus mindestens 6 einfache Schritte, ehe überhaupt der Ausdünnvorgang (bei dann zwischen 28 und 50 Zahlen) begonnen werden muss.
Ohne Ausdünnen lösbar (bei ca. 82.4 % der 17er-Sudokus):
Super einfach lösbar (0 Punkte): 000000000000000012003004000000010000005600400034000000000072000100000600720000080
Ebenso einfach lösbar (3 Punkte): 000000000000000001002003040000000005000016007083000000000004980070020000100000030
Ziemlich einfach lösbar (11 Punkte): 000000000000000012003045000000003006000700000040000500000100000006200078305000000
Ebenfalls ziemlich einfach lösbar (22 Punkte): 000000001000002000001000034000000500000140000060007200000300008020000000507000600
Etwas schwieriger, aber noch einfach lösbar (38 Punkte): 000000001000000002003004000000001350060000400700080000000060907000800000205000000
Noch etwas schwieriger, aber immer noch einfach lösbar (59 Punkte): 000000001000002000003000040000030000005460000010000708000500060020000000180007000
Mit Ausdünnen lösbar (bei ca. 17.6 % der 17er-Sudokus):
Lösbar in 5 Ausdünnschritten (42 Punkte): 000000000000000012003004005000000600000025000074000300000008400200000009900100000
Lösbar in 11 Ausdünnschritten (166 Punkte): 000000000000000012003045000000001460007000000020080000000030500210700000600000000
Lösbar in 23 Ausdünnschritten (269 Punkte): 000000001000000020003045000000003400000006000120000007008000500500000600700100000
Lösbar in 26 Ausdünnschritten (369 Punkte): 000000000001002003040050060000000007000000102080400000000060080007000000203001000
Lösbar in 29 Ausdünnschritten (434 Punkte): 000000001000002030004050000000060400020000070300008000000900000046000500080003000
Bisher ungelöst ohne einem Ausdünnschritt in etwa 1 sec (bis dahin 34 Punkte), hier nur mit Trial&Error lösbar: 000000000000001002003004050000010000000020030065000400000300000070006001200000008
Ebenso ungelöst nach 24 Ausdünnschritten (bis dahin 406 Punkte), hier ebenfalls nur mit Trial&Error lösbar: 000000001000002003004056000000000260070000000810300000000170000006000050040000000
Hier nur mit der Methode Bowman's Bingo gelöst werden. Ein paar schwierige Beispiele:
Gelöst mit 51 Ausgangszahlen und 300 Punkten: 105480009040901000900070104218549600593768412467123895059014020624097001001000940
Gelöst mit 54 Ausgangszahlen und 275 Punkten: 020056709056090102009200546205060490074905260960024357590002674642579813007640925
Gelöst mit 58 (!!) Ausgangszahlen und 216 Punkten: 430009206620304090097026034043092600960407023072630940214700369356941782789263415
Hier nur mit der Methode Trial&Error gelöst werden. Ein paar sehr schwierige Beispiele:
Gelöst mit 50 Ausgangszahlen und 374 Punkten: 002630014000401023134052800003200145245010630010543200001375402320804051450120300
Gelöst mit 52 Ausgangszahlen und 305 Punkten: 005718000010293050000456001891624735532987146647135982000372500050841060000569000
Gelöst mit 54 Ausgangszahlen und 188 Punkten: 037942050509000423428350079802703045045020730073405002751034290394200507286500314
Sehr einfach lösbar mit 6 Punkten bei 20 Ausgangszahlen: 100008000400000007000600023000001080070004000030000006800000010000700040560300000
Extrem schwierig lösbar mit 750 Punkten bei ebenfalls 20 Ausgangszahlen: 001600000080009200300000040600300010000000000090005008040000005007100060000008900
Sehr einfach lösbar mit 0 Punkten bei 23 Ausgangszahlen: 070000804000010005000543000003000617020000000000060000800004000205807000040000260
Extrem schwierig lösbar mit 907 Punkten bei ebenfalls 23 Ausgangszahlen: 080010020600500900000008000060080010700100400005002006020040090300700500000009000
Extrem einfach lösbar mit 0 Punkten bei 31 Ausgangszahlen: 000300000009800075000600980070000000090082041128007069060700804000290100003040027
Extrem schwierig lösbar mit 633 Punkten bei ebenfalls 31 Ausgangszahlen, mit Trial&Error gelöst: 040007062008600000006400190100290040000178250020040001002000610000004520500700080
Extrem einfach lösbar mit 0 Punkten bei 38 Ausgangszahlen: 027605940459070862000000000004309600803000709006807400000000000632040598081906230
Sehr schwierig lösbar mit 352 Punkten bei ebenfalls 38 Ausgangszahlen: 100200035203510400090034000007000053021370040830000107300400070002093004410758302
Extrem einfach lösbar mit 0 Punkten bei 43 Ausgangszahlen: 070200090200000600018060040083452100751090000602871030000916354069024807034785009
Recht schwierig lösbar mit 233 Punkten bei ebenfalls 43 Ausgangszahlen: 000768000007932400300451009001879200000613000863245917010580090030197000900320105
Sehr einfach lösbar mit 0 Punkten bei 20 Ausgangszahlen: 500904000000005080073000006000020000000306000018000900032000000000000091009200000
Extrem schwierig lösbar mit 557 Punkten bei ebenfalls 20 Ausgangszahlen: 006000070000005000002000000700046090800000000460000000013500000047208000090070000
Sehr einfach lösbar mit 0 Punkten bei 23 Ausgangszahlen: 006003000430000070090000100000480000500700000000900000008000257059040000010807009
Extrem schwierig lösbar mit 487 Punkten bei ebenfalls 23 Ausgangszahlen: 000000841000004093000000050040000008080000070001003500008061700000092080000008002
Extrem einfach lösbar mit 0 Punkten bei 27 Ausgangszahlen: 000000000000072690060000000103090807820000100076050004000000000300001275050830406
Sehr schwierig lösbar mit 204 Punkten bei ebenfalls 27 Ausgangszahlen: 000000100000000000900000836008020009500000268094600310000004003426080790070006000
Extrem einfach lösbar mit 0 Punkten bei 39 Ausgangszahlen: 003250700075384921002100500060000002009700800300920070904671305130590467700000000
Recht schwierig lösbar mit 361 Punkten bei ebenfalls 39 Ausgangszahlen: 947003200235700040600542739870030000590000307300970000703004000400000073169387000
Extrem einfach lösbar mit 0 Punkten bei 42 Ausgangszahlen: 607009003830704010201008006012030700406091008080607100350406091029080607760902800
Recht schwierig lösbar mit 198 Punkten bei ebenfalls 42 Ausgangszahlen: 007000025020405070500027009619542738752030000348070502270010053090703280000200007
Extrem einfach lösbar mit 0 Punkten bei 23 Ausgangszahlen: 590010080006000009010700203000000800040200000030000000960300000080050000002849000
Sehr schwierig lösbar mit 459 Punkten bei ebenfalls 23 Ausgangszahlen: 000000100000960002004000006308500001050080700000003000900040000007010090000009617
Extrem einfach lösbar mit 0 Punkten bei 27 Ausgangszahlen: 020000034085003090040009060000000200019020000802004001000000000030001007006705423
Recht schwierig lösbar mit 224 Punkten bei ebenfalls 27 Ausgangszahlen: 000600000046000920500004610000000170600010000000000000283009541004052000060043700
Extrem einfach lösbar mit 0 Punkten bei 31 Ausgangszahlen: 000600170596740080200000904962000003000000000380496000750380200823960000000000000
Recht schwierig lösbar mit 142 Punkten bei ebenfalls 31 Ausgangszahlen: 710000520020003000040029080100932000060000030034000005300271008002000301401308000
Extrem einfach lösbar mit 0 Punkten bei 35 Ausgangszahlen: 020900500105230849090700300700005008000400601506000000801372096960500003200040080
Etwas schwierig lösbar mit 92 Punkten bei ebenfalls 35 Ausgangszahlen: 500071000200005001001000005000750100010000758057010004605027010100503027720190540
Extrem einfach lösbar mit 0 Punkten bei 38 Ausgangszahlen: 003006089456789120000100000200060000061007200897200000000640978640978002978000600
Etwas schwierig lösbar mit 69 Punkten bei ebenfalls 38 Ausgangszahlen: 000032409430769000920045603000983000000276194069514000090300000000600940000490350
posteo.de, Homepage: https://www.sarahandrobin.com/ingo/