Standard-Sudokus: Notwendige Ausgangszahlen i.A. nur von 17 bis 31, extrem selten bis 40

Stand: 21. April 2020 (zuerst: 23. März 2019)   -   Ingolf Giese   -   Letzte Änderung: 25. September 2020

Das Phänomen der "notwendigen Ausgangszahlen" - insbesondere der obere Wert dieses Bereiches - wurde bisher selten untersucht. Das Phänomen bedeutet, dass kein Standard-Sudoku weniger als 17 (Beweis von 2012, Gary McGuire und Kollegen) und im Allgemeinen auch nicht mehr als 31 Ausgangszahlen benötigt - mit extrem wenigen Ausnahmen bei 32 und 33 (und inzwischen auch bis 40) Ausgangszahlen. Dazu analysiert man vorhandene Sudokus durch "Reduzierung": Das heißt, dass man dem zu untersuchenden Sudoku (nacheinander) eine der Ausgangszahlen wegnimmt (reduziert) und feststellt, ob (mindestens) eines dieser abgeleiteten Sudokus immer noch eindeutig lösbar ist. Wenn eines eindeutig lösbar ist, nimmt man diesem (bei mehreren Treffern eventuell zufällig ausgewählten) Sudoku wieder (nacheinander) eine der verbliebenen Ausgangszahlen weg und testet erneut auf eindeutige Lösbarkeit. Das macht man so lange, bis alle erzeugten Sudokus nicht mehr eindeutig lösbar sind - dann ist das im Ablauf vorhergehende (erzeugende) Sudoku ein vollständig reduziertes Sudoku. Dabei gibt es natürlich eine riesige Zahl von möglichen Wegen durch den Reduzierungs-Ablaufbaum, von denen aber normalerweise - aus Rechenzeit-Gründen - in der Praxis nur wenige durchlaufen werden können. Nicht mehr reduzierbare Sudokus heißen auch Minimal-Sudokus.

Beispiel mit dem Ausgangs-Sudoku 000000000012000374040702090400600020073090600820107039060801040034000768000000000:

Alle 31 Ausgangszahlen werden nacheinander weggenommen, aber nur 5 dieser neuen Sudokus sind eindeutig lösbar.
Z.B.: 000000000012000374040702090400600020073090600820107030060801040034000768000000000
Die nun 30 Ausgangszahlen werden nacheinander weggenommen, aber nur 4 dieser neuen Sudokus sind eindeutig lösbar.
Z.B.: 000000000012000374040702090400600020073090600820107030060801040004000768000000000
Die nun 29 Ausgangszahlen werden nacheinander weggenommen, aber nur 2 dieser neuen Sudokus sind eindeutig lösbar.
Z.B.: 000000000012000374040702090400600020073090600820107000060801040004000768000000000
Die nun 28 Ausgangszahlen werden nacheinander weggenommen, aber nur 1 dieser neuen Sudokus ist eindeutig lösbar:
000000000012000374040702090400600020073090600820007000060801040004000768000000000
Die nun 27 Ausgangszahlen werden nacheinander weggenommen, aber keines dieser neuen Sudokus ist eindeutig lösbar. Damit ist das zuletzt erhaltene Sudoku ein vollständig reduziertes Sudoku bzw. Minimal-Sudoku.

Anderes Beispiel: Das Ausgangs-Sudoku 061409352340002961592136784906205143410963520235041600759328416623014800184607230 mit 64 Ausgangszahlen konnte nach 40 Reduzierungsschritten auf ein Sudoku mit 25 Ausgangszahlen reduziert werden: 000409050000002900500100704006005040010903020000000000700300006020014000180000200.

Eine große Zahl der hier bekannten Standard-Sudokus (bisher etwa 148000 von etwa 1.5 Millionen Sudokus - 55000 weitere haben genau 17 Ausgangszahlen und sind damit nicht reduzierbar) wurden mittels Reduzierungsversuchen analysiert. Etwa 10 % der untersuchten Sudokus konnten von vorne herein nicht reduziert (also verkleinert) werden, und es waren alle untersuchten Sudokus mit mehr als 31 Ausgangszahlen - bei dieser mit Zufallsentscheidungen arbeitenden Methode - reduzierbar: Es wurde dabei kein einziges Sudoku gefunden, das mehr als 31 Ausgangszahlen benötigt! Es wurden bei diesen Rechnungen mit etwa 148000 Sudokus nur 16 Sudokus mit 30 notwendigen Ausgangszahlen und nur 2 mit 31 notwendigen Ausgangszahlen gefunden.

Eine vollständige Analyse (also ohne Benutzung nur eines zufällig ausgewählten abgeleiteten Sudokus, sondern aller abgeleiteten Sudokus) eines bestimmten dieser bisher untersuchten Sudokus 027048063468301070300700000084100600216800309003000000830600590070000006649285731 mit 41 Ausgangszahlen (das Sudoku, das bei den bisherigen "Zufalls"-Rechnungen die meisten Sudokus mit 31 notwendigen Ausgangszahlen erzeugt hatte) zeigte folgendes Ergebnis: Bis zur Ausgangszahl 33 gibt es etwa 350 Millionen mögliche Sudokus, wenn man bis zu 8 der Ausgangszahlen durch 0 ersetzt. Dabei sind aber nicht alle dieser Sudokus eindeutig lösbar. Rechnet man in jeder Stufe von 41 bis zu 33 Ausgangszahlen aber immer nur mit den eindeutig lösbaren Sudokus weiter, muss man nur etwa 250000 Sudokus zu reduzieren versuchen (was aber etwa 200 Stunden Rechenzeit bedeutet). Alle Sudokus mit mehr als 33 Ausgangszahlen waren reduzierbar, im letzten Schritt wurden aber der extrem seltene Fall von 4 sehr ähnlichen Sudokus gefunden, die 33 Ausgangszahlen benötigen:

020048060468301070300700000084100600216800009000000000830600590070000000600285730
020048060468301070300700000084100600216800009000000000830600590070000000609280730
027048060468301070300000000084100600216800009000000000830600590070000000600285730
027048060468301070300000000084100600216800009000000000830600590070000000609280730
Alle 4 Sudokus sind aber relativ einfach lösbar mit 120 bis 126 Punkten bei Option 2001 und mit jeweils 11 Ausdünnschritten (mit maximal 8 Punkten/Schritt).

Eines der anderen Tochter-Sudokus, z.B. 020048000468301070300700000080100000216800309003000000830600590070000000640285730, konnte aber um 1 Ausgangszahl verkleinert werden zum 32er-Sudoku
020048000468301070300700000080100000216800309003000000800600590070000000640285730 (eines von 41 Beispielen).
Zusätzlich wurden 274 Sudokus gefunden, die 31 notwendige Ausgangszahlen haben, und 538 Sudokus, die 30 notwendige Ausgangszahlen haben. Das ist das bezüglich Reduzierung extremste Sudoku, das bisher gefunden wurde.

Das eigentlich bei den "Zufalls"-Rechnungen ähnlich erfolgreiche (mit einem 31er-Sudoku) Sudoku 940682050350904006600050000130000075805000104720005090400020500200501007510749080 wurde ebenso vollständig analysiert (mit etwa 150000 zu untersuchenden Sudokus in etwa 100 Stunden Rechenzeit). Es wurde jedoch kein Sudoku mit 32 oder mehr notwendigen Ausgangszahlen gefunden, aber immerhin 43 Sudokus, die 31 notwendige Ausgangszahlen haben und 265 Sudokus, die 30 notwendige Ausgangszahlen haben. Das zeigt auch die Seltenheit des oben beschriebenen Sudokus 027048....

Auch mehrere andere vielversprechende Sudokus (bisher 10 weitere, bei denen die "Zufalls"-Rechnungen wenigstens ein 30er-Sudoku ergaben) wurden in intensiven Tests und zum Teil vollständig durch Reduzierung berechnet (wobei über 5 Millionen Sudokus erzeugt und getestet wurden - in etwa 1000 Stunden Rechenzeit), aber es wurde kein einziges mit mehr als 31 notwendigen Ausgangszahlen gefunden, meistens nur Sudokus mit 30 notwendigen Ausgangszahlen. Insgesamt wurden dabei bisher 348 (also nur 31 weitere - bei 3 der 10 Sudokus) Sudokus gefunden, die 31 notwendige Ausgangszahlen haben, und 1241 (also 438 weitere) Sudokus, die 30 notwendige Ausgangszahlen haben.

Bei Standard-Sudokus lagen also alle notwendigen Ausgangszahlen (also der reduzierten Sudokus) im Bereich 17 bis 33 mit dem Mittelwert 24, mit einer relativ typischen Gaußschen Glockenkurve bei der Verteilung (mit etwas verlängertem rechten Ast): Dabei kamen die Ausgangszahlen 23 bis 25 bei jeweils etwa 20 bis 33 % (Summe 78 %) aller reduzierten Sudokus vor, bei den Ausgangszahlen 21 bis 27 war die Summe 98 %, und die Ausgangszahlen an den Rändern, also bei 18 bis 19 und bei 29 bis 33 lagen weit unter jeweils 1 % der Häufigkeit. Alle Sudokus mit 17 Ausgangszahlen sind natürlich Minimal-Sudokus.

Beispiel eines der Sudokus mit 31 notwendigen Ausgangszahlen (mit 189 Punkten): 008201030200780000007006802901000000406079003070800609009600300000000004014030208
Beispiel eines der Sudokus mit 30 notwendigen Ausgangszahlen (mit 376 Punkten): 500000000000806900080000013750140006003070540240500090030000060009301402100000309

Inzwischen wurde eine englische Webseite gefunden, die sich auch mit dem Thema beschäftigt. Dort wurden Sudokus mit bis zu 40 notwendigen Ausgangszahlen gefunden, insbesondere von "Mladen Dobrichev":
Beispiel eines der beiden Sudokus mit 40 notwendigen Ausgangszahlen (mit 102 Punkten): 000000000012034567034506182001058206008600001020007050003705028080060700207083615
Beispiel eines der 2650 Sudokus mit 39 notwendigen Ausgangszahlen (mit 294 Punkten): 000000000012034056034056102000073600076410080340068007087301005100047008403085700
Beispiel eines der lösbaren Sudokus mit 38 notwendigen Ausgangszahlen (mit 188 Punkten): 000000012001023450024601307000105004045076031107030060052300000408507023700002040
Beispiel eines der lösbaren Sudokus mit 37 notwendigen Ausgangszahlen (mit 81 Punkten): 000000001001023040052046037000000083087030405503084710000008000028065074076412008
Beispiel eines der lösbaren Sudokus mit 36 notwendigen Ausgangszahlen (mit 93 Punkten): 000000000000001023000045006014078205082500071750010008038007060260403087470086300

Die gleichen Reduzierungs-Untersuchungen wurden auch für die hier bekannten etwa 30000 Diagonal-Sudokus und 11500 Farb-Sudokus gemacht. Bei den Diagonal-Sudokus scheint 12 die kleinste Ausgangsanzahl zu sein. Bei den Farb-Sudokus ist sogar 11 (!) die wahrscheinlich kleinste Ausgangsanzahl. Bei allen drei Sudoku-Typen (Standard-, Diagonal-, Farb-Sudoku) waren die Anzahlen der Ausgangszahlen der reduzierten Sudokus recht gut normalverteilt (Gaußsche Glockenkurve).

Bei Diagonal-Sudokus lagen alle Ausgangszahlen der reduzierten Sudokus im (erstaunlich kleinen und schiefen) Bereich 12 bis 22 mit dem Mittelwert 17.9 - woraus man aus Symmetriegründen auch auf ein Diagonal-Sudoku mit maximal notweniger Ausgangszahl von 23 schließen könnte (es wurden aber nur 18 Sudokus mit 22 notwendigen Ausgangszahlen gefunden). Die Ausgangszahlen 17 bis 19 der reduzierten Diagonal-Sudokus bildeten hier jeweils etwa 23, 35 und 24 % aller Fälle, die Rand-Ausgangszahlen 12 bis 14 und 21 bis 22 lagen ebenfalls jeweils weit unter 1 %.

Bei Farb-Sudokus im (erstaunlich großen und auch schiefen) Bereich 11 bis 27 war der Mittelwert 17.5, dabei hatten die Ausgangszahlen 17 und 18 jeweils etwa 30 bzw. 27 % Häufigkeit; die selten (0.25 %) auftretenden Ausgangszahlen 25 bis 27 fielen (trotz der weit unter 1 % liegenden Häufigkeit) aber doch etwas aus der Normalverteilung heraus.

Interessant ist auch die Frage nach der Anzahl aller eindeutig lösbaren Minimal-Sudokus (nicht reduzierbaren Sudokus). Dazu wurden nach einem Vorgehen analog der Rechnung bei "Abschätzung der Gesamtsumme aller eindeutig lösbaren Sudoku-Rätsel" mit dazu zusätzlich ermittelten Prozentsätzen (Anteile der nicht reduzierbaren Sudokus je Ausgangszahl N) und den dort ermittelten Anteilen der Gesamtsumme, insbesondere im Bereich N = 23 bis N = 26, die Anzahl der Minimal-Sudokus zu 1.6 × 10^25 abgeschätzt (mit den gleichen Voraussetzungen wie bei Russell und Jarvis, also ohne Vertauschung der Ziffern, ohne Drehungen, Zeilen- bzw. Spaltenvertauschungen und Blockzeilen- bzw. Blockspaltenvertauschungen) - wobei die benutzten Anteile von Minimal-Sudokus mit Ausgangszahl N etwas ungenau sind (N = 23 bis N = 26 mit ungefähr 25 %, 10 %, 6 % und 1%), da wegen dem riesigen Rechenaufwand nur wenig Sudokus erzeugt werden konnten. Die prozentualen Anteile an der Gesamtsumme sind dann etwa 1 %, 19 %, 46 % und 33 % (Summe 99 %). Im englischen Wikipedia steht eine etwas größere geschätzte Zahl von 2.55 × 10^25, mit viel zu hohen Prozentsätzen (95 %, 90 %, 15 % und 1 %), aber mit den gleichen Anteilen an der Gesamtsumme.

Diese Ergebnisse sind aber aus einem anderen Grund fraglich: Nach Rechnungen mit 100000 Sudokus mit Ausgangszahlen im Bereich von 41 bis 64 und mit 81 Ausgangszahlen (also Lösungen) wurde eine Verteilung der gefundenen Minimal-Sudokus sehr nahe einer Gaußschen Normalverteilung (siehe "Bild der Verteilung") im Bereich 21 bis 28 gefunden, mit Anteilen an der Gesamtsumme für N = 23 bis N = 26 von etwa 15.7 %, 29.5 %, 28.6 % und 15.4 % (insgesamt also etwa 89.2 % aller Anteile) - bei entsprechend angepassten Prozentsätzen; dies ergab eine viel kleinere Anzahl von 1.03 × 10^23 Minimal-Sudokus. Aber alle diese Zahlen geben wenigstens eine grobe Abschätzung an. Und alles im Vergleich zu den 5.3 × 10^33 insgesamt möglichen eindeutig lösbaren Sudokus (alle Zahlen nach Russell und Jarvis)...



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/