Rückzieher
wuerg, 17.11.2024 16:20
Plötzlich schlug Youtube mir eine Erläuterung des Backtrackings in der Informatik vor. Und wie ein KI‑System spontan und assoziativ zumeist zufälligerweise richtig liegt, so kam mir analog Backpropagating in den Sinn, womit man Physik-Nobelpreise gewinnen kann, wenn man auch noch Boltzmann ins Spiel bringen kann.
Erweist sich etwas als falsch, kann ich das meinem Gefühl oder meinen Überlegungen anlasten und ihnen zukünftig skeptischer gegenüberstehen (backpropagation). Probiere ich einfach etwas aus und es scheitert, dann wird wohl das Gegenteil richtig sein (backtracking). Zwei schlichte Überlegungen, die von vielen Menschen gerne ignoriert werden, ohne bessere zu verwenden.
Backtracking in der Informatik als „Methode der Problemlösung“ besteht einfach darin, eine Aufgabe in mehrere Fälle zu teilen, um dies mit ihnen abermals und in der Folge immer und immer wieder zu tun, bis Erfolg oder Scheitern offenkundig wird, was man nach oben (back) meldet. Wieder an der Spitze angekommen ist dann das Problem gelöst oder auch nicht.
Ich frug mich, wie man diese simple Idee deutsch benennt. In der allwissenden Müllhalde fand ich holprige Wörter wie Rücksetzverfahren und Rückverfolgung. Glücklicherweise war Rückkopplung schon vergeben. Sinnvoll ist Tiefensuche (depth first search), weil die Unterfälle in die Tiefe führen, nicht nach oben oder in die Breite.
Man hätte auf einen eigenen Namen verzichten und Backtracking als eine Ausprägung von Versuch und Irrtum (trial and error) belassen können. Und geradezu edel ist die Beschreibung aus einer Zeit, da es weder Geschlechtskunde noch Informatik an Universitäten gab: Teile und herrsche. Dennoch habe ich für die Überschrift die witzige Google-Übersetzung gewählt: Rückzieher.
Doch Youtube wird mir das Filmchen eines Informatik-Jungspundes aus einem profaneren Grunde hochgepoppt haben, nämlich wegen Sudokus und deren Lösung durch Backtracking. Lang, breit und, wenn man es noch sagen darf, bis zur Vergasung erklärte er die Methode: Im ersten freien Feld alle Ziffern 1 bis 9 ausprobieren, um mit der gleichen Methode das so entstandene Sudoku mit einen freien Feld weniger zu lösen. So geht es weiter bis alle Felder ausgefüllt sind. Der Erfolg wird nach oben gemeldet, das Sodoku ist gelöst.
Da ich vor Jahren ein Programm nicht in der vorgestellten Brutalität (rekursiver Selbstaufruf), doch entlang dieser schlichten Idee schrieb, war ich der Meinung, dies sei die Brute-Force-Methode. Doch von dieser das Backtracking abwertenden Begrifflichkeit mußte sich der Youtuber absetzen und verstand darunter, bei n freien Feldern einfach alle 10 hoch n Belegungen durchzuprobieren.
Leider fand ich mein altes Programm nicht mehr und habe schnell ein neues erstellt, ohne rekursiv aufrufbare Platz und Zeit fressende ‚Methode‘, früher einfach Unterprogramm genannt. Geschrieben in Fortran IV hätte es weit vor der Erfindung des Sudoku, da mir allein Algol als rekursive Programmiersprache bekannt war, jedes Rätsel in bescheidener Laufzeit gelöst.
Langer Rede kurzer Sinn: Ich habe die vor Jahren hier betrachteten Sudoku durch mein Programm laufen lassen. Für eine erschöpfende Suche fielen normalerweise ein paar tausend Konfigurationen an. Bis zur Lösung ist davon mal weniger, mal mehr als die Hälfte abzuwickeln. Nur für dieses
Offensichtlich ist bei satten 38 vorgegebenen Feldern nicht nur der mittlere Block, sondern auch die erste Zeile schwach. Nur sieben Kombinationen reichten, im ersten freien Feld (Zeile 1, Spalte 2) alles außer der 5 auszuschließen. Für die 3 danach waren auch nur acht erforderlich, weshalb mit 254 begonnen werden muß. Glücklicherweise führte 2541 direkt (heute würde man sagen: linear) zur Lösung.
Natürlich wußte ich bereits, daß dieses Sudoku leicht durch reine Suche nach versteckten Einern zu lösen ist: Zunächst fallen alle fehlenden Einsen, dann die Zweien bis zu den Neunen. Ein weiterer Durchgang ist nicht erforderlich. Trotzdem hätte ich nie gerade mit der ersten Zeile begonnen, in der ja nur drei Ziffern gegeben sind.
Sudoku | Einer | Raster
Erweist sich etwas als falsch, kann ich das meinem Gefühl oder meinen Überlegungen anlasten und ihnen zukünftig skeptischer gegenüberstehen (backpropagation). Probiere ich einfach etwas aus und es scheitert, dann wird wohl das Gegenteil richtig sein (backtracking). Zwei schlichte Überlegungen, die von vielen Menschen gerne ignoriert werden, ohne bessere zu verwenden.
Backtracking in der Informatik als „Methode der Problemlösung“ besteht einfach darin, eine Aufgabe in mehrere Fälle zu teilen, um dies mit ihnen abermals und in der Folge immer und immer wieder zu tun, bis Erfolg oder Scheitern offenkundig wird, was man nach oben (back) meldet. Wieder an der Spitze angekommen ist dann das Problem gelöst oder auch nicht.
Ich frug mich, wie man diese simple Idee deutsch benennt. In der allwissenden Müllhalde fand ich holprige Wörter wie Rücksetzverfahren und Rückverfolgung. Glücklicherweise war Rückkopplung schon vergeben. Sinnvoll ist Tiefensuche (depth first search), weil die Unterfälle in die Tiefe führen, nicht nach oben oder in die Breite.
Man hätte auf einen eigenen Namen verzichten und Backtracking als eine Ausprägung von Versuch und Irrtum (trial and error) belassen können. Und geradezu edel ist die Beschreibung aus einer Zeit, da es weder Geschlechtskunde noch Informatik an Universitäten gab: Teile und herrsche. Dennoch habe ich für die Überschrift die witzige Google-Übersetzung gewählt: Rückzieher.
Doch Youtube wird mir das Filmchen eines Informatik-Jungspundes aus einem profaneren Grunde hochgepoppt haben, nämlich wegen Sudokus und deren Lösung durch Backtracking. Lang, breit und, wenn man es noch sagen darf, bis zur Vergasung erklärte er die Methode: Im ersten freien Feld alle Ziffern 1 bis 9 ausprobieren, um mit der gleichen Methode das so entstandene Sudoku mit einen freien Feld weniger zu lösen. So geht es weiter bis alle Felder ausgefüllt sind. Der Erfolg wird nach oben gemeldet, das Sodoku ist gelöst.
Da ich vor Jahren ein Programm nicht in der vorgestellten Brutalität (rekursiver Selbstaufruf), doch entlang dieser schlichten Idee schrieb, war ich der Meinung, dies sei die Brute-Force-Methode. Doch von dieser das Backtracking abwertenden Begrifflichkeit mußte sich der Youtuber absetzen und verstand darunter, bei n freien Feldern einfach alle 10 hoch n Belegungen durchzuprobieren.
Leider fand ich mein altes Programm nicht mehr und habe schnell ein neues erstellt, ohne rekursiv aufrufbare Platz und Zeit fressende ‚Methode‘, früher einfach Unterprogramm genannt. Geschrieben in Fortran IV hätte es weit vor der Erfindung des Sudoku, da mir allein Algol als rekursive Programmiersprache bekannt war, jedes Rätsel in bescheidener Laufzeit gelöst.
Langer Rede kurzer Sinn: Ich habe die vor Jahren hier betrachteten Sudoku durch mein Programm laufen lassen. Für eine erschöpfende Suche fielen normalerweise ein paar tausend Konfigurationen an. Bis zur Lösung ist davon mal weniger, mal mehr als die Hälfte abzuwickeln. Nur für dieses
+-------+-------+-------+ | 2 . . | . 7 8 | . . . | | 6 . 1 | . 9 . | . 4 5 | | . 9 . | . 4 . | 1 8 . | +-------+-------+-------+ | . . 7 | . 2 6 | 3 5 . | | . . 9 | 7 . . | . 1 6 | | 8 . 5 | . . 9 | . . . | +-------+-------+-------+ | . 7 . | 4 3 . | 2 . . | | . 1 2 | 5 8 . | 6 . 4 | | . 3 8 | 9 . . | . . 1 | +-------+-------+-------+Sudoku, an dessen mittleren Block ich erläuterte, wie man mit einfachen Mitteln einer Lösung näher kommen kann, ging es überraschend schnell:
1 - 24..78...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 2 - 243.78...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 3 - 243178...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 4 - 2431789..6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 5 - 24317896.6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 6 - 243678...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 7 - 2436789..6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 8 - 25..78...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 9 - 253.78...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 10 - 253178...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 11 - 2531789..6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 12 - 25317896.6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 13 - 253678...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 14 - 2536789..6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 15 - 254.78...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 16 - 254178...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 17 - 2541789..6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 18 - 25417893.6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 19 - 25417896.6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 20 - 2541789636.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 21 - 254178963681.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 22 - 25417896368129..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 23 - 254178963681293.45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 24 - 254178963681293745.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 25 - 25417896368129374539..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 26 - 25417896368129374579..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 27 - 254178963681293745793.4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 28 - 25417896368129374579364.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 29 - 25417896368129374579364518...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 30 - 254178963681293745793645182..7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 31 - 2541789636812937457936451821.7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 32 - 254178963681293745793645182147.2635...97...168.5..9....7.43.2...1258.6.4.389....1 33 - 25417896368129374579364518214782635...97...168.5..9....7.43.2...1258.6.4.389....1 34 - 254178963681293745793645182147826359..97...168.5..9....7.43.2...1258.6.4.389....1 35 - 2541789636812937457936451821478263593.97...168.5..9....7.43.2...1258.6.4.389....1 36 - 2541789636812937457936451821478263593297...168.5..9....7.43.2...1258.6.4.389....1 37 - 25417896368129374579364518214782635932975..168.5..9....7.43.2...1258.6.4.389....1 38 - 254178963681293745793645182147826359329754.168.5..9....7.43.2...1258.6.4.389....1 39 - 2541789636812937457936451821478263593297548168.5..9....7.43.2...1258.6.4.389....1 40 - 254178963681293745793645182147826359329754816865..9....7.43.2...1258.6.4.389....1 41 - 2541789636812937457936451821478263593297548168653.9....7.43.2...1258.6.4.389....1 42 - 254178963681293745793645182147826359329754816865319....7.43.2...1258.6.4.389....1 43 - 2541789636812937457936451821478263593297548168653194...7.43.2...1258.6.4.389....1 44 - 25417896368129374579364518214782635932975481686531942..7.43.2...1258.6.4.389....1 45 - 254178963681293745793645182147826359329754816865319427.7.43.2...1258.6.4.389....1 46 - 25417896368129374579364518214782635932975481686531942757.43.2...1258.6.4.389....1 47 - 25417896368129374579364518214782635932975481686531942757643.2...1258.6.4.389....1 48 - 2541789636812937457936451821478263593297548168653194275764312...1258.6.4.389....1 49 - 25417896368129374579364518214782635932975481686531942757643129..1258.6.4.389....1 50 - 254178963681293745793645182147826359329754816865319427576431298.1258.6.4.389....1 51 - 25417896368129374579364518214782635932975481686531942757643129891258.6.4.389....1 52 - 2541789636812937457936451821478263593297548168653194275764312989125876.4.389....1 53 - 254178963681293745793645182147826359329754816865319427576431298912587634.389....1 54 - 2541789636812937457936451821478263593297548168653194275764312989125876344389....1 55 - 25417896368129374579364518214782635932975481686531942757643129891258763443896...1 56 - 254178963681293745793645182147826359329754816865319427576431298912587634438962..1 57 - 2541789636812937457936451821478263593297548168653194275764312989125876344389625.1 58 - 254178963681293745793645182147826359329754816865319427576431298912587634438962571 59 - 25417896368129374579364518214782635932975481686531942797.43.2...1258.6.4.389....1 60 - 25417896368129374579364518214782635932975481686531942797643.2...1258.6.4.389....1 61 - 2541789636812937457936451821478263593297548168653194279764312...1258.6.4.389....1 62 - 25417896368129374579364518214782635932975481686531947..7.43.2...1258.6.4.389....1 63 - 2541789636812937457936451824.7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 64 - 25417896368139..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 65 - 254178963681392.45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 66 - 254178963681392745.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 67 - 25417896368139274539..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 68 - 25417896368139274579..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 69 - 254178963681392745793.4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 70 - 25417896368139274579364.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 71 - 25417896368139274579364518...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 72 - 254178963681392745793645182..7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 73 - 2541789636813927457936451821.7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 74 - 254178963681392745793645182147.2635...97...168.5..9....7.43.2...1258.6.4.389....1 75 - 25417896368139274579364518214782635...97...168.5..9....7.43.2...1258.6.4.389....1 76 - 254178963681392745793645182147826359..97...168.5..9....7.43.2...1258.6.4.389....1 77 - 2541789636813927457936451821478263593.97...168.5..9....7.43.2...1258.6.4.389....1 78 - 2541789636813927457936451821478263593297...168.5..9....7.43.2...1258.6.4.389....1 79 - 25417896368139274579364518214782635932975..168.5..9....7.43.2...1258.6.4.389....1 80 - 254178963681392745793645182147826359329754.168.5..9....7.43.2...1258.6.4.389....1 81 - 2541789636813927457936451821478263593297548168.5..9....7.43.2...1258.6.4.389....1 82 - 254178963681392745793645182147826359329754816865..9....7.43.2...1258.6.4.389....1 83 - 2541789636813927457936451824.7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 84 - 254378...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 85 - 2543789..6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 86 - 25437896.6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 87 - 254678...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 88 - 2546789..6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 89 - 25467893.6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1
Offensichtlich ist bei satten 38 vorgegebenen Feldern nicht nur der mittlere Block, sondern auch die erste Zeile schwach. Nur sieben Kombinationen reichten, im ersten freien Feld (Zeile 1, Spalte 2) alles außer der 5 auszuschließen. Für die 3 danach waren auch nur acht erforderlich, weshalb mit 254 begonnen werden muß. Glücklicherweise führte 2541 direkt (heute würde man sagen: linear) zur Lösung.
Natürlich wußte ich bereits, daß dieses Sudoku leicht durch reine Suche nach versteckten Einern zu lösen ist: Zunächst fallen alle fehlenden Einsen, dann die Zweien bis zu den Neunen. Ein weiterer Durchgang ist nicht erforderlich. Trotzdem hätte ich nie gerade mit der ersten Zeile begonnen, in der ja nur drei Ziffern gegeben sind.
Sudoku | Einer | Raster
... comment
wuerg,
19.11.2024 22:09
Geht denn das immer so flott mit dem Computer? Ja und nein. Ja, weil moderne Rechner sehr schnell sind und selbst eine 80‑fach geschachtelte Rekursion bewältigen. Nein, weil nicht nur schwere, sondern auch recht leichte Sudoku deutlich mehr Schritte benötigen, weit über zehntausend. Hier ein von mir im Jahre 2006 betrachtetes Sudoku:
Daß dies auch auf einem bescheidenen Notebook ruckzuck geht, sollte nicht dazu verleiten, auf diese Weise ein leeres Sudoku lösen zu lassen, um so ihre Gesamtzahl zu bestimmen, denn es sind n=6.670.903.752.021.072.936.960. Selbst wenn man nur die mit 123456789 in der obersten Zeile beginnenden ermittelt, sind es immer noch n/9!=18.393.222.420.692.992. Selbst bei einer Milliarde Lösungen pro Sekunde, dauert es noch sieben Monate. Es ist deshalb sinnvoll, in weitere Unterfälle zu teilen. [2].
[1] Von einem Sudoku ist natürlich gefordert, daß es genau eine Lösung hat. Es gilt aber als unschön, dieses Wissen auszunutzen, insbesondere eine Ziffer zu setzen, weil es ansonsten zwei Lösungen geben muß.
[2] Felgenhauer, Jarvis: There are 6670903752021072936960 Sudoku grids. 2005.
+-------+-------+-------+ | 1 . . | . 6 . | . . 5 | | . 8 . | 9 . 3 | . 1 . | | . . 7 | . . . | 8 . . | +-------+-------+-------+ | . 7 . | . 4 . | . 9 . | | 5 . . | 7 . 1 | . . 6 | | . 6 . | . 3 . | . 7 . | +-------+-------+-------+ | . . 3 | . . . | 9 . . | | . 1 . | 3 . 9 | . 4 . | | 9 . . | . 2 . | . . 1 | +-------+-------+-------+Erst nach 25.551 Schritten in die Tiefe und Breite wurde die Lösung gefunden. Die Gesamtsuche nach allen Lösungen [1] benötigte mit 28.745 kaum mehr, weil das erste zu ermittelnde Feld eine 9 erfordert.
0 - 1...6...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
1 - 12..6...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
..
5723 - 13..6...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
..
8132 - 14..6...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
..
14860 - 19..6...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
14861 - 192.6...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
...
20953 - 194.6...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
20954 - 19426...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
....
23740 - 19486...5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
23741 - 194862..5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
23742 - 1948623.5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
23743 - 1948627.5.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
23744 - 194862735.8.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
23745 - 19486273528.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
..........
24421 - 19486273568.9.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
24422 - 1948627356829.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
............
24427 - 1948627356859.3.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
24428 - 194862735685973.1...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
24429 - 19486273568597321...7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
24430 - 194862735685973214..7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
24431 - 1948627356859732142.7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
...................
24959 - 1948627356859732143.7...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
24960 - 194862735685973214327...8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
24961 - 1948627356859732143271..8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
......................
25283 - 1948627356859732143274..8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
......................
25477 - 1948627356859732143275..8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25478 - 19486273568597321432751.8...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25479 - 1948627356859732143275158...7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25480 - 19486273568597321432751486..7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25481 - 194862735685973214327514869.7..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25482 - 19486273568597321432751486927..4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25483 - 194862735685973214327514869271.4..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25484 - 19486273568597321432751486927164..9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25485 - 194862735685973214327514869271645.9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
.................................
25512 - 194862735685973214327514869271648.9.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25513 - 19486273568597321432751486927164839.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25514 - 19486273568597321432751486927164859.5..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25515 - 1948627356859732143275148692716485935..7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25516 - 19486273568597321432751486927164859353.7.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25517 - 1948627356859732143275148692716485935387.1..6.6..3..7...3...9...1.3.9.4.9...2...1
25518 - 194862735685973214327514869271648593538791..6.6..3..7...3...9...1.3.9.4.9...2...1
25519 - 1948627356859732143275148692716485935387914.6.6..3..7...3...9...1.3.9.4.9...2...1
25520 - 194862735685973214327514869271648593538791426.6..3..7...3...9...1.3.9.4.9...2...1
25521 - 19486273568597321432751486927164859353879142646..3..7...3...9...1.3.9.4.9...2...1
25522 - 194862735685973214327514869271648593538791426469.3..7...3...9...1.3.9.4.9...2...1
25523 - 19486273568597321432751486927164859353879142646923..7...3...9...1.3.9.4.9...2...1
25524 - 194862735685973214327514869271648593538791426469235.7...3...9...1.3.9.4.9...2...1
25525 - 19486273568597321432751486927164859353879142646923517...3...9...1.3.9.4.9...2...1
25526 - 194862735685973214327514869271648593538791426469235178..3...9...1.3.9.4.9...2...1
25527 - 1948627356859732143275148692716485935387914264692351787.3...9...1.3.9.4.9...2...1
25528 - 194862735685973214327514869271648593538791426469235178743...9...1.3.9.4.9...2...1
25529 - 1948627356859732143275148692716485935387914264692351787431..9...1.3.9.4.9...2...1
25530 - 19486273568597321432751486927164859353879142646923517874315.9...1.3.9.4.9...2...1
...........................................................
25537 - 19486273568597321432751486927164859353879142646923517874318.9...1.3.9.4.9...2...1
25538 - 1948627356859732143275148692716485935387914264692351787431869...1.3.9.4.9...2...1
25539 - 19486273568597321432751486927164859353879142646923517874318695..1.3.9.4.9...2...1
25540 - 194862735685973214327514869271648593538791426469235178743186952.1.3.9.4.9...2...1
25541 - 19486273568597321432751486927164859353879142646923517874318695281.3.9.4.9...2...1
25542 - 1948627356859732143275148692716485935387914264692351787431869528123.9.4.9...2...1
25543 - 194862735685973214327514869271648593538791426469235178743186952812359.4.9...2...1
25544 - 19486273568597321432751486927164859353879142646923517874318695281235964.9...2...1
25545 - 1948627356859732143275148692716485935387914264692351787431869528123596479...2...1
25546 - 19486273568597321432751486927164859353879142646923517874318695281235964795..2...1
25547 - 194862735685973214327514869271648593538791426469235178743186952812359647956.2...1
25548 - 19486273568597321432751486927164859353879142646923517874318695281235964795642...1
25549 - 194862735685973214327514869271648593538791426469235178743186952812359647956427..1
25550 - 1948627356859732143275148692716485935387914264692351787431869528123596479564273.1
25551 - 194862735685973214327514869271648593538791426469235178743186952812359647956427381
Daß dies auch auf einem bescheidenen Notebook ruckzuck geht, sollte nicht dazu verleiten, auf diese Weise ein leeres Sudoku lösen zu lassen, um so ihre Gesamtzahl zu bestimmen, denn es sind n=6.670.903.752.021.072.936.960. Selbst wenn man nur die mit 123456789 in der obersten Zeile beginnenden ermittelt, sind es immer noch n/9!=18.393.222.420.692.992. Selbst bei einer Milliarde Lösungen pro Sekunde, dauert es noch sieben Monate. Es ist deshalb sinnvoll, in weitere Unterfälle zu teilen. [2].
[1] Von einem Sudoku ist natürlich gefordert, daß es genau eine Lösung hat. Es gilt aber als unschön, dieses Wissen auszunutzen, insbesondere eine Ziffer zu setzen, weil es ansonsten zwei Lösungen geben muß.
[2] Felgenhauer, Jarvis: There are 6670903752021072936960 Sudoku grids. 2005.
... link
... comment
