Standard-Sudokus: Abschätzung der Gesamtsumme aller eindeutig lösbaren Sudoku-Rätsel

Stand: 18. Juni 2020   -   Ingolf Giese   -   Letzte Änderung: 7. Juli 2020

Das deutsche Wikipedia sagt auf der Diskussionsseite zu Sudoku: "Die Anzahl der möglichen Sudokus liegt irgendwo zwischen 10^13 und 10^50". Das kann jetzt also genauer angegeben werden.

Im Januar 2006 berichteten Ed Russell und Frazer Jarvis, dass es 5 472 730 538 (≈ 5.5 × 10^9) wesentlich verschiedene (also ohne Vertauschung der Ziffern, ohne Drehungen, Zeilen- bzw. Spaltenvertauschungen und Blockzeilen- bzw. Blockspaltenvertauschungen) vollständig ausgefüllte, also gelöste Sudokus gibt.

Im Wesentlichen alle Auskünfte im Web zu der Frage, wie viele Sudoku-Rätsel es gibt, werden falsch beantwortet, und zwar mit der ("leicht" berechenbaren) Anzahl der vollständig ausgefüllten Sudokus, im Allgemeinen mit dem von Felgenhauer und Jarvis 2005 errechneten Wert 6 670 903 752 021 072 936 960 (≈ 6.7 × 10^21) bzw. mit dem (sinnvolleren) o.a. Wert 5 472 730 538, dem Wert ohne der Vertauschungen, Drehungen und Vertauschungen (Russell und Jarvis). Aber die eigentlich interessante Frage ist die nach der Anzahl der Sudoku-Rätsel, also die noch nicht ausgefüllt und außerdem eindeutig lösbar sind. Immerhin hat Brian Hayes das Problem schon 2008 erkannt: "Es muss betont werden, dass beide Berechnungen (von Felgenhauer und Jarvis und von Russell und Jarvis) die Anzahl der Lösungen und nicht die Anzahl der Rätsel zählen" - aber konnte die Rechnungen nicht durchführen.

Hier wurde nun untersucht, wie viele Sudoku-Rätsel mit 17 bis 80 Ausgangszahlen und mit den gleichen Voraussetzungen wie bei Russell und Jarvis möglich und eindeutig lösbar sind. Die folgende Übersichtstabelle zeigt die bisher erzielten Ergebnisse für einige interessante Bereiche der Ausgangszahlen mit der jeweils errechneten Gesamtsumme:

	17-32:	≈ 1.3 × 10^31
	17-36:	≈ 2.7 × 10^32
	17-40:	≈ 1.5 × 10^33
	17-48:	≈ 4.9 × 10^33
	17-64:	≈ 5.3 × 10^33
	17-80:	≈ 5.3 × 10^33

Das Prinzip für die Berechnung dieser Gesamtsummen ist das Folgende:
Für jedes der etwa 5.5 × 10^9 wesentlich verschiedenen Sudokus gibt es für jeweils N Ausgangszahlen , kurz "81 über N", unterschiedliche Sudokus. Das Produkt beider Zahlen ist die Gesamtzahl aller möglichen Sudokus bei N Ausgangszahlen, als Gesamtsumme für alle Ausgangszahlen N von 17 bis 80 also etwa 1.3 × 10^34; davon sind aber natürlich nicht alle Sudokus eindeutig lösbar. Daher muss jedes dieser Produkte jeweils multipliziert werden mit einem durch zahlreiche Zufallsrechnungen ermittelten Prozentsatz (immer bezogen auf N Ausgangszahlen). Dann können die Summen für jede Anzahl N von Ausgangszahlen und damit die Gesamtsummen für interessante Bereiche von Ausgangszahlen berechnet werden (Beispiele siehe Tabelle).

Zur Bestimmung der Prozentsätze nimmt man für jede Ausgangszahl N von 17 bis 80 beispielsweise 50 oder mehr zufällige (vollständig ausgefüllte) Ausgangssudokus und bestimmt für jedes dieser Sudokus 81-N zufällige Stellen, bei denen man die dort vorhandene Zahl streicht (d.h. durch 0 oder "." ersetzt); dies macht man z.B. 100000 Mal. Für jedes dieser insgesamt erzeugten Sudokus ermittelt man durch ein Trial&Error-Programm, wie viele dieser Sudokus eindeutige Lösungen haben. Dabei erhält man dann einen Prozentsatz, der besagt, wie viele Sudokus bei N Ausgangszahlen eine Lösung haben, wobei der Prozentsatz natürlich abhängig von den verwendeten Zufallszahlen etwas schwankt. Die aktuelle Verteilung zeigt das Bild der Prozentsätze, erstellt aus etwa 350 Millionen erzeugten und gerechneten Sudokus.

Die Prozentsätze für die Ausgangszahlen 78 bis 80 sind offensichtlich 100 %, für N = 77 aber 99.999391... %, da genau 6/80*(2/79*1/8)*1/78 + 2/80*(6/79*1/8)*1/78 Sudokus immer zwei Lösungen haben wegen eines Ausschluss-Rechtecks mit den fehlenden Zahlen in waagrecht und senkrecht liegenden Boxen. Außerdem folgt daraus für N = 76 der genau 5-fache Wert, da es "5 über 4" = 5 Möglichkeiten gibt, ein Ausschluss-Rechteck zu bilden - das ergibt dann 99.996957... % für diesen Anteil der eindeutig lösbaren Sudokus. Analog gilt für N = 75, 74, 73, ... jeweils der Faktor "6 über 4" = 15, "7 über 4" = 35, "8 über 4" = 70, u.s.w., bis andere Fälle/Konstellationen auftreten, dass ein Sudoku nicht eindeutig lösbar wird - das waren in allen Beispielen im Allgemeinen mehrere 6er-Ausschluss-Schleifen bzw. 3 parallele Paare (bei N = 74 in 0.12 % der Fälle, bei N = 73 in 0.30 % der Fälle).

Es ist noch möglich, die gefundenen Prozentsätze (sinnvollerweise deren Logarithmen, da deren Bereich viel kleiner ist) zu glätten, z.B. mit der Methode der kleinsten Quadrate, etwa mit einem Polynom 5. Grades. Eine Glättung und eine Extrapolation im Bereich unterhalb von 24 erbrachte nur eine Abweichung in der jeweils 3. Stelle.

Der Binomialkoeffizient oder "81 über N" = 81! / (N! × (81-N)!) = (81-N+1)×(81-N+2)×...×79×80×81 / (1×2×3×...×(N-1)×N) gibt an, auf wie viele verschiedene Arten man N bestimmte Objekte aus einer Menge von 81 verschiedenen Objekten auswählen kann - ohne Beachtung der Reihenfolge. Bekannt ist diese Formel auch bei der Berechnung der Anzahl der in Deutschland möglichen Lottozahlen: "49 über 6".

Den höchsten Anteil an der berechneten Gesamtsumme haben die Sudokus mit 35 bis 51 Ausgangszahlen, das sind etwa 97 %. Die Prozentsätze für die Anzahlen unter 24 wurden extrapoliert, da sie sehr aufwendig zu bestimmen sind (man braucht dann schon jeweils mindestens 10^7 bis 10^12 Rechnungen statt z.B. 100000) und die daraus errechneten Anzahlen tragen sowieso nur geringfügig zu der gesuchten Gesamtsumme bei.

Von allen Sudokus mit 17 bis 80 Ausgangszahlen (13 232 250 261 443 826 842 603 337 271 215 336 ≈ 1.3 × 10^34) sind ziemlich genau 40 % lösbar, die meisten davon (etwa 71 %) natürlich im oberen Bereich mit 41 bis 80 Ausgangszahlen.

Interessant ist z.B., dass es zwar etwa 4.3 × 10^32 lösbare Sudokus mit 40 Ausgangszahlen gibt, aber davon tatsächlich 2 Sudokus von Mladen Dobrichev gefunden wurden, die nicht reduzierbar sind. Andererseits sind die von Gordon Royle bis 2012 gesammelten etwa 50000 Sudokus mit 17 Ausgangszahlen wesentlich näher an der möglichen Anzahl von etwa 10^12 Sudokus.

Verzichtet man auf die Einschränkungen von Russell und Jarvis, und rechnet also mit dem viel höheren Wert von Felgenhauer und Jarvis (≈ 6.7 × 10^21), werden alle genannten Anzahlen um den Faktor 1.2 × 10^12 höher: d.h. es gibt dann 1.6 × 10^46 mögliche Sudokus, von denen 6.4 × 10^45 eindeutig löbar sind.

Englische Version

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/