Kein Zusammenhang Anzahl Ausgangszahlen und Schwierigkeit eines Sudokus

Auch: Zur Schwierigkeit/Bewertung eines Sudokus

Stand: 5. Mai 2020   -   Ingolf Giese   -   Letzte Änderung: 29. Juli 2020

Es gibt keine allgemeine Formel, um die Schwierigkeit eines Sudokus zu bestimmen.

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", 29-32 Ausgangszahlen mit der Bezeichnung "mittel" und 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.

Alle 25 Sudokus aus dem Kapitel "Sehr einfache (leichte) und sehr schwierige (schwere) Standard-Sudokus" haben 17 bis 27 Ausgangszahlen, die wirklich schwierigen haben 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.

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 4.5 bis zu fast 1000 Punkten (bei der Option 2001 oder NUR BEWERTUNG und bei 17 bis 32 Ausgangszahlen). Denn ein Sudoku mit vielen recht schwierigen Lösungsschritten ist bestimmt schwieriger als eines mit nur einem maximalen Schwierigkeitsgrad. Bei diesem Programm werden in bestimmten Fällen auch Zusatzpunkte addiert oder subtrahiert, wenn es sehr wenige oder sehr viele mögliche Lösungsschritte gibt, und 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 "Anhang".

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

Beispiele verschiedener Sudoku-Arten bei gleichen Ausgangszahlen, aber sehr unterschiedlichen Schwierigkeitsgraden:

Diese Beispiele zeugen eindeutig, dass es keinen Zusammenhang zwischen der Anzahl der Ausgangszahlen und der Schwierigkeit eines Sudokus gibt!

Standard-Sudokus mit interessanten Beispielen:

Sehr einfach lösbar mit 20.5 Punkten bei 17 Ausgangszahlen: 000000001000002000003000045000000200000050000016300700000006308000700000450000000
Sehr schwierig lösbar mit 450 Punkten bei ebenfalls 17 Ausgangszahlen: 000000000002003001050060040000007000000102000400000080060080000000000007001000203

Sehr einfach lösbar mit 17 Punkten bei 20 Ausgangszahlen: 100008000400000007000600023000001080070004000030000006800000010000700040560300000
Extrem schwierig lösbar mit 775 Punkten bei ebenfalls 20 Ausgangszahlen: 001600000080009200300000040600300010000000000090005008040000005007100060000008900

Sehr einfach lösbar mit 9 Punkten bei 23 Ausgangszahlen: 070000804000010005000543000003000617020000000000060000800004000205807000040000260
Extrem schwierig lösbar mit 988 Punkten bei ebenfalls 23 Ausgangszahlen: 080010020600500900000008000060080010700100400005002006020040090300700500000009000

Extrem einfach lösbar mit 5 Punkten bei 31 Ausgangszahlen: 000300000009800075000600980070000000090082041128007069060700804000290100003040027
Extrem schwierig lösbar mit 724 Punkten bei ebenfalls 31 Ausgangszahlen: 040007062008600000006400190100290040000178250020040001002000610000004520500700080

Extrem einfach lösbar mit 3.5 Punkten bei 34 Ausgangszahlen: 000000000009007308780900020903000100840173500610208730108052093000001050200000810
Sehr schwierig lösbar mit 474 Punkten bei ebenfalls 34 Ausgangszahlen: 081020030260305080000008002057002060802070001040000270320900050070200014010050820

Extrem einfach lösbar mit 2.5 Punkten bei 38 Ausgangszahlen: 027605940459070862000000000004309600803000709006807400000000000632040598081906230
Sehr schwierig lösbar mit 365 Punkten bei ebenfalls 38 Ausgangszahlen: 100200035203510400090034000007000053021370040830000107300400070002093004410758302

Extrem einfach lösbar mit 0 Punkten bei 43 Ausgangszahlen: 070200090200000600018060040083452100751090000602871030000916354069024807034785009
Recht schwierig lösbar mit 284 Punkten bei ebenfalls 43 Ausgangszahlen: 000768000007932400300451009001879200000613000863245917010580090030197000900320105

Auch bei Diagonal-Sudokus gibt es interessante Beispiele mit sehr unterschiedlichen Schwierigkeitsgraden:

Sehr einfach lösbar mit 40 Punkten bei 15 Ausgangszahlen: 200000001500020000000980000000007050040000000000500200000004600000000090008000000
Sehr schwierig lösbar mit 509 Punkten bei ebenfalls 15 Ausgangszahlen: 023400000000900000000000610000000506000003000000005000019000000000007000000000028

Sehr einfach lösbar mit 13.5 Punkten bei 19 Ausgangszahlen: 850002300000000080070000000000040003000500010000070006201080000000006020400001000
Extrem schwierig lösbar mit 676 Punkten bei ebenfalls 19 Ausgangszahlen: 000000040500008010000000000090070500820000300007000020002000600060009000781000000

Sehr einfach lösbar mit 11 Punkten bei 20 Ausgangszahlen: 500904000000005080073000006000020000000306000018000900032000000000000091009200000
Extrem schwierig lösbar mit 813 Punkten bei ebenfalls 20 Ausgangszahlen: 006000070000005000002000000700046090800000000460000000013500000047208000090070000

Sehr einfach lösbar mit 8 Punkten bei 23 Ausgangszahlen: 006003000430000070090000100000480000500700000000900000008000257059040000010807009
Extrem schwierig lösbar mit 599 Punkten bei ebenfalls 23 Ausgangszahlen: 000000841000004093000000050040000008080000070001003500008061700000092080000008002

Extrem einfach lösbar mit 5 Punkten bei 27 Ausgangszahlen: 000000000000072690060000000103090807820000100076050004000000000300001275050830406
Sehr schwierig lösbar mit 417.5 Punkten bei ebenfalls 27 Ausgangszahlen: 000000100000000000900000836008020009500000268094600310000004003426080790070006000

Extrem einfach lösbar mit 1 Punkt bei 39 Ausgangszahlen: 003250700075384921002100500060000002009700800300920070904671305130590467700000000
Recht schwierig lösbar mit 346 Punkten bei ebenfalls 39 Ausgangszahlen: 947003200235700040600542739870030000590000307300970000703004000400000073169387000

Extrem einfach lösbar mit 0 Punkten bei 42 Ausgangszahlen: 607009003830704010201008006012030700406091008080607100350406091029080607760902800
Recht schwierig lösbar mit 297 Punkten bei ebenfalls 42 Ausgangszahlen: 007000025020405070500027009619542738752030000348070502270010053090703280000200007

Und auch bei Farb-Sudokus gibt es interessante Beispiele:

Sehr einfach lösbar mit 15.5 Punkten bei 16 Ausgangszahlen: 000000054300009000060013000000000000070200000020000000200000000417000000000000806
Extrem schwierig lösbar mit 885 Punkten bei ebenfalls 16 Ausgangszahlen: 900000000084700001000200006008000000000056007000003900030000000000000010007000000

Extrem einfach lösbar mit 6.5 Punkten bei 23 Ausgangszahlen: 590010080006000009010700203000000800040200000030000000960300000080050000002849000
Sehr schwierig lösbar mit 511 Punkten bei ebenfalls 23 Ausgangszahlen: 000000100000960002004000006308500001050080700000003000900040000007010090000009617

Extrem einfach lösbar mit 4 Punkten bei 27 Ausgangszahlen: 020000034085003090040009060000000200019020000802004001000000000030001007006705423
Recht schwierig lösbar mit 248.5 Punkten bei ebenfalls 27 Ausgangszahlen: 000600000046000920500004610000000170600010000000000000283009541004052000060043700

Extrem einfach lösbar mit 3.5 Punkten bei 29 Ausgangszahlen: 800305400650104072001060508500601089400200300006000004100000200009000000080000007
Recht schwierig lösbar mit 176 Punkten bei ebenfalls 29 Ausgangszahlen: 710000520000003000000009080100932000060000030034000005300271008002000301401308002

Extrem einfach lösbar mit 3.5 Punkten bei 31 Ausgangszahlen: 000600170596740080200000904962000003000000000380496000750380200823960000000000000
Recht schwierig lösbar mit 159 Punkten bei ebenfalls 31 Ausgangszahlen: 710000520020003000040029080100932000060000030034000005300271008002000301401308000

Extrem einfach lösbar mit 1.5 Punkten bei 35 Ausgangszahlen: 020900500105230849090700300700005008000400601506000000801372096960500003200040080
Etwas schwierig lösbar mit 110 Punkten bei ebenfalls 35 Ausgangszahlen: 500071000200005001001000005000750100010000758057010004605027010100503027720190540

Extrem einfach lösbar mit 0 Punkten bei 38 Ausgangszahlen: 003006089456789120000100000200060000061007200897200000000640978640978002978000600
Etwas schwierig lösbar mit 85 Punkten bei ebenfalls 38 Ausgangszahlen: 000032409430769000920045603000983000000276194069514000090300000000600940000490350

Analyse der Sudokus mit 17 Ausgangszahlen

Das Problem der Schwierigkeits-Beurteilung sieht man am besten an den sehr zahlreichen und ausführlich untersuchten Sudokus mit nur 17 Ausgangszahlen (dem Minimum) - von denen i.A. behauptet wird, dass sie sehr schwierig sind: Etwa 33 % der vorliegenden etwa 57000 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 (80 %) einfach - also ohne Ausdünnen - lösbar! Nur etwa 0.5 % sind mit diesem Programm bisher nicht lösbar und etwa 19 % mit bis zu 30 Ausdünnschritten lösbar (von denen auch nur knapp 0.2 % mehr als 240 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 Zahlen. Bei allen hier vorhandenen wirklich schwierigen Sudokus mit mindestens 240 Punkten (knapp 17000) gibt es bei 75 % der Sudokus mindestens 6 einfache Schritte, ehe überhaupt der Ausdünnvorgang (bei dann zwischen 28 und 50 Zahlen) begonnen werden muss.

Einige - sehr unterschiedlich schwierige - Beispiele bei 17 Ausgangszahlen (bei Standard-Sudokus):

Ohne Ausdünnen lösbar (bei ca. 80 % der 17er-Sudokus):
Sehr einfach lösbar (22 Punkte): 000000000000000012000003004000000050004010000006007300000604800010020009050000000
Einfach lösbar (40.5 Punkte): 000000000000000012003045000000003006000700000040000500000100000006200078305000000
Schon etwas schwieriger lösbar (62 Punkte): 000000001000000002003004000000001350060000400700080000000060907000800000205000000
Relativ schwierig lösbar (90.5 Punkte): 000000001000002000003000040000030000005460000010000708000500060020000000180007000

Mit Ausdünnen lösbar (bei ca. 19 % der 17er-Sudokus):
Lösbar in 11 Ausdünnschritten (168 Punkte): 000000000000000012003045000000001460007000000020080000000030500210700000600000000
Lösbar in 23 Ausdünnschritten (287 Punkte): 000000000000001002034000050000000006000050300007042000000630800109000000200000000
Lösbar in 28 Ausdünnschritten (399 Punkte): 000000001000000023004005000000000060000007500120030000000120008000400000076000000
Lösbar in 28 Ausdünnschritten (438 Punkte): 000000000001002003040050060000000007000000102080400000000060080007000000203001000

Bisher ungelöst bei 17 Ausgangszahlen ohne einem Ausdünnschritt in etwa 1 sec (bis dahin 68 Punkte): 000000000000001002003004050000010000000020030065000400000300000070006001200000008
Immer noch ungelöst nach 12 Ausdünnschritten und etwa 6 sec (bis dahin 203 Punkte): 000000001000000020003045000000003400000006000120000007008000500500000600700100000
Immer noch ungelöst nach 22 Ausdünnschritten und etwa 12 sec (bis dahin 353 Punkte): 000000001000002003004056000000000260070000000810300000000170000006000050040000000

Umgekehrt gibt es viele Sudokus mit mehr als 36 Ausgangszahlen (der üblichen Grenze), die gar nicht so einfach lösbar sind. Hier ein paar Beispiele:

Etwas schwierig lösbar bei 48 Ausgangszahlen in 13 Ausdünnschritten (168 Punkte): 000001043040300012103245607000674301310020764764103200076430120421000030830012476
Etwas schwierig lösbar bei 52 (!) Ausgangszahlen in 17 Ausdünnschritten (188 Punkte): 754000230198237654623405070417000062582674000936021047245100700069702400071040020
Etwas schwierig lösbar bei 55 (!!) Ausgangszahlen in 15 Ausdünnschritten (147 Punkte): 003716004040895360060243000618954003732168459594372816300681040006429030400537600
Einfacher lösbar bei 58 Ausgangszahlen in 5 Ausdünnschritten (45 Punkte): 950140328023090001001230900639851274572964183184723569000019032290380410310472090
Einfacher lösbar bei 64 Ausgangszahlen in 2 Ausdünnschritten (23 Punkte): 245816397103024658068503412804007520057082940021405873009248165516009284482651739

Und es gibt viele Sudokus mit mehr als 36 Ausgangszahlen (der üblichen Grenze), die mit diesem Programm nicht lösbar sind. Hier ein paar Beispiele:
Bisher ungelöst bei 43 Ausgangszahlen nach 14 Ausdünnschritten (bis dahin 194 Punkte): 008240730230087000700390028000032405593470280402050003600023007320710000017064302
Bisher ungelöst bei 48 Ausgangszahlen nach nur 5 Ausdünnschritten (bis dahin 88 Punkte): 104296030200734000000158240041063572002071400706425310400382000020617004010549023
Bisher ungelöst bei 55 Ausgangszahlen nach nur 1 Ausdünnschritt (bis dahin 36 Punkte): 501023004400501032023046159012305406000402501045019023000158247184237965257004318
Bisher ungelöst bei 61 Ausgangszahlen nach nur 2 Ausdünnschritten (bis dahin 43 Punkte): 206051043045036012103204600309105426014602030062043100638519274951427368427368591



 

Anhang:

Einzelheiten zu den einzelnen Lösungsmethoden siehe "Direkte Sudoku-Lösungsmethoden" und "Methoden zur Ausdünnung der Reste (Kandidatenliste)"

Punktevergabe für alle direkten Lösungsmethoden:

Einzige Position einer Zahl (A)
   A1/A2: 0 bis 2 Punkte (bei 1-2, 3-4, 5-9 noch fehlenden Zahlen) innerhalb Zeilen/Spalten, A3: 0 bis 1 Punkte (bei 1-2, 3-9 noch fehlenden Zahlen) innerhalb Boxen
Einzig mögliche Zahl (B)
   B0: 2 bis 4 Punkte (bei 1-4, 5-8, 9-12 noch fehlenden Zahlen)
Offensichtlicher Zeilen-/Spalten-Test (C)
   C1/C2: 1 bis 2 Punkte (bei 1-3, 4-9 noch fehlenden Zahlen abzgl. Anzahl Begründungen) innerhalb Zeilen/Spalten, C3: 1 Punkt innerhalb Boxen; plus 2 * Anzahl der notwendigen Begründungen
   C0 (Einzig mögliche Zahl): 2 bis 6 Punkte (bei 1-4, 5-8, 9-12, 13-16, 17-20 noch fehlenden Zahlen abzgl. Anzahl Begründungen); plus 2 * Anzahl der notwendigen Begründungen
Offensichtliche 2-Tupel (Doppel) (D)
   D1/D2: 1 bis 2 Punkte (bei 1-3, 4-9 noch fehlenden Zahlen abzgl. 2 * Anzahl Doppel) innerhalb Zeilen/Spalten, D3: 1 Punkt innerhalb Boxen; plus 2 * Anzahl der notwendigen Doppel
   D0 (Einzig mögliche Zahl): 2 bis 5 Punkte (bei 1-5, 6-10, 11-15, 16-20 noch fehlenden Zahlen abzgl. 2 * Anzahl Doppel); plus 2 * Anzahl der notwendigen Doppel
   D4 (2 Paare von offensichtlichen 2-Tupeln in einer einzigen Zelle): 5 Punkte
   D5 (2 Paare von offensichtlichen 2-Tupeln in drei Ecken eines Ausschluss-Rechtecks): 5 Punkte
Ausdünnung mit einem alleine auftretendem Kandidaten (E)
   E1/E2/E3: 0 bis 1 Punkte (bei 1-3, 4-9 noch fehlenden Zahlen) innerhalb Zeilen/Spalten/Boxen
Ausdünnung mit einem einzig möglichen Kandidaten (einstelliger Rest) (F)
   F0: 0 bis 1 Punkte (bei 1-6, 7-9 noch fehlenden Zahlen)


Punktevergabe und Reihenfolge der Abarbeitung/Ermittlung für alle Ausdünnmethoden (gekürzt):

StufeMethodePunkte
Bei Stufe 2 (Einfache Bestimmung) mit 2-5 Punkten
2-Tupel2
Zeilen-/Spalten-Tests3
Box-Tests4
Ausschluss-Rechtecke Typ 1, 2, 3A, 5A-5B4-5
Dazu bei Stufe 3 (Mittlere Bestimmung) mit 5-8 Punkten
3-Tupel5
Versteckte 2-Tupel8
3er- bis 5er-Goldene Ketten6-8
XYZ-Wing7
2*2-Einzelzahl-Gitter (4er-Einzelzahl-Ketten als X-Wings)7
4er-Einzelzahl-Ketten8
Ausschluss-Rechtecke Typ 3B bis 8C7-8
Quasi-Ausschluss-Rechtecke bei 1 Zusatzzahl Typ 1, 2, 3A, 5A-5B7-8
6er-Ausschluss-Schleifen Typ 1, 2, 3A, 5A-5C7-8
Dazu bei Stufe 4 (Hohe Bestimmung) mit 8-11 Punkten
4-Tupel8
Versteckte 3-Tupel11
6er- bis 8er-Goldene Ketten9-11
WXYZ-Wing10
Erweiterter WXYZ-Wing11
3*3-Einzelzahl-Gitter (Swordfish)10
6er-Einzelzahl-Ketten11
Ausschluss-Rechtecke Typ 3C (Quasi-4-Tupel)11
Quasi-Ausschluss-Rechtecke bei 1-3 Zusatzzahlen (versch. Typen)9-11
6er-Ausschluss-Schleifen Typ 3B bis 8C10-11
6er-Quasi-Ausschluss-Schleifen bei 1 Zusatzzahl Typ 1, 2, 3A, 5A-5C10-11
8er-Ausschluss-Schleifen Typ 1, 2, 3A, 5A-5D10-11
Dazu bei Stufe 5 (Komplexe Bestimmung) mit 11-14 Punkten
5-Tupel11
9er- bis 11er-Goldene Ketten12-14
4*4-Einzelzahl-Gitter (Jellyfish)13
8er-Einzelzahl-Ketten14
Ausschluss-Rechtecke Typ 3D (Quasi-5-Tupel)14
Quasi-Ausschluss-Rechtecke bei 2-4 Zusatzzahlen (versch. Typen)12-14
6er-Ausschluss-Schleifen Typ 3C (Quasi-4-Tupel)14
6er-Quasi-Ausschluss-Schleifen bei 1-3 Zusatzzahlen (versch. Typen)12-14
8er-Ausschluss-Schleifen Typ 3B, 4A-4C, 6, 7A-7C, 8A-8C13-14
10er-Ausschluss-Schleifen Typ 1, 2, 3A, 5A-5E13-14
Dazu bei Stufe 6 (Weitestgehende Bestimmung) mit 14-17 Punkten
6-Tupel (theoretisch)14
12er- bis 14er-Goldene Ketten15-17
10er-Einzelzahl-Ketten17
Ausschluss-Rechtecke Typ 3E (Quasi-6-Tupel)17
Quasi-Ausschluss-Rechtecke bei 2-4 Zusatzzahlen (versch. Typen)15-17
6er-Ausschluss-Schleifen Typ 3D (Quasi-5-Tupel)17
6er-Quasi-Ausschluss-Schleifen bei 2-4 Zusatzzahlen (versch. Typen)15-17
8er-Ausschluss-Schleifen Typ 3C (Quasi-4-Tupel)17
10er-Ausschluss-Schleifen Typ 3B, 4A-4C, 7A-7C, 8A-8C16-17
12er-Ausschluss-Schleifen Typ 1, 2, 3A, 5A-5E16-17
Dazu bei Stufe 7 (Allerweitestgehende Bestimmung) mit 17 bis 36 Punkten
7-Tupel (theoretisch)17
12er- und 14er-Einzelzahl-Ketten20-23
Ausschluss-Rechtecke Typ 3F (Quasi-7-Tupel)20
Quasi-Ausschluss-Rechtecke bei 1-4 Zusatzzahlen Typ 3C-3F19-29
6er-Ausschluss-Schleifen Typ 3E-3F (Quasi-6-7-Tupel)20-23
6er-Quasi-Ausschluss-Schleifen bei 2-6 Zusatzzahlen (versch. Typen)16-36
8er-Ausschluss-Schleifen Typ 3D-3F (Quasi-5-7-Tupel)20-26
10er-Ausschluss-Schleifen Typ 3C-3F (Quasi-4-7-Tupel)20-29
12er-Ausschluss-Schleifen Typ 3B-3F, 4A-4C, 6, 7A-7C, 8A-8C19-32
14er-Ausschluss-Schleifen alle Typen19-35
Alle Widerspruchs-, Folgerungs- und Alternativ-Ketten bis Länge 1417-31



Datenschutz: DSGVO-Hinweis:
Personenbezogene Daten werden NICHT ermittelt, verarbeitet oder gespeichert!

Impressum:
Angaben gemäß § 5 TMG:

Verantwortlich für den Inhalt dieser Webseite: Ingolf Giese

Fragen und Kommentare bitte an I.Gieseposteo.de, Homepage: https://www.sarahandrobin.com/ingo/