... newer stories
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 (edler mit -tion) 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 9 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 9 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:
0 - 2...78...6.1.9..45.9..4.18...7.2635...97...168.5..9....7.43.2...1258.6.4.389....1 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
... link (8 Kommentare) ... comment
... older stories
