Backtracking ist ein Verfahren zur systematischen Suche. Es baut eine Kandidatenlösung Schritt für Schritt auf und verwirft einen Zweig, sobald er die Bedingungen des Problems verletzt oder keine vollständige Lösung mehr ergeben kann.
Das Verfahren wird etwa bei Constraint-Problemen, kombinatorischer Suche und manchen Rätseln eingesetzt. Es kann viele Kandidaten prüfen und im ungünstigen Fall exponentielle Laufzeit haben; gute Pruning-Regeln können die Suche verkleinern.
Backtracking kann eine oder mehrere Lösungen finden, sofern Abbruchbedingungen und Suchraum passend definiert sind.
Inhaltlich überarbeitet am 2026-10-13. Suchprinzip und ungünstige Laufzeit ergänzt.