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öpfende Suche