Backtracking am Beispiel des Dameproblems

Im Schachspiel darf sich die Dame als einzige Figur frei horizontal, vertical und diagonal bewegen. Beim k-Dameproblem versucht man, auf einem k x k Felder großen Schachbrett k Damen so zu platzieren, dass sie sich nicht gegenseitig im Weg stehen, sich also niemals zwei Damen in der gleichen Reihe, Spalte oder Diagonalen befinden. Lösungen für das Dameproblem kann man mit Hilfe einer erschöpfenden Suche ermitteln. Dabei ist es sinnvoll, immer eine Dame nach der anderen auf das Schachbrett zu stellen. Wenn man dabei nicht weiter kommt, muss man zuvor aufgestellte Damen wieder zurücknehmen. Das nennt man dann "Backtracking".
00:00 - Intro
00:19 - Einleitung
03:17 - Beispiel für k = 4
04:12 - Wie zählt man alles auf?
06:22 - Algorithmus
13:05 - Algorithmus mit Backtracking
15:56 - Was bedeutet "Backtracking"?
16:19 - Beispiel für k = 7
- Erschöpfende Suche: • Rucksackproblem: Ersch...

[@sLiv256]

Exzellent erklärt, vielen Dank.

[@ubokbiivobuvivij9051]

Sehr hilfreich vielen Dank

[@kpunkt.klaviermusik]

Super erklärt, besonders auch das mit dem Zurücknehmen von Zügen am Ende!

[@conan1231]

Ja, das letzte Beispiel hat es auch mir endlich verständlich gemacht.