Backtracking

Einfache Sprache

Backtracking sucht den gesamten Lösungsraum nach einer optimalen und zulässigen Lösung ab. Der Lösungsraum wird meist als Baum dargestellt. Der Baum wird systematisch durchsucht. Wenn keine Lösung in einem Zweig gefunden wird, so geht man zurück und durchsucht andere Zweige. Es ist die Anwendung des Versuch-und-Irrtum-Prinzip

Example

Ein Beispiel ist das N-Damen-Problem (wie das Damenproblem bloß mit $N$ Damen)