Was ist Backtracking?

Question

Accepted Answer

**Backtracking** erstellt Kandidatenlösungen schrittweise und **verwirft** (zieht sich zurück aus) einen Teilkandidaten, sobald er nicht zu einer gültigen Lösung führen kann. Es durchsucht den Lösungsraum systematisch via DFS und beschneidet tote Enden.

## Die Idee

Wähle -> erkunde -> mache die Wahl rückgängig. Versuche eine Option, wiederhole; wenn fehlgeschlagen, mache rückgängig und versuche die nächste.

## Beispiel: alle Permutationen

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # complete solution
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                             # un-choose (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 permutations
```

## Klassische Probleme

- **N-Queens**, Sudoku, Springertour.
- **Teilmengen / Kombinationen / Permutationen.**
- **Wortsuche**, Labyrinth-Lösung.

## Komplexität

Often exponentiell (z. B. O(n!) für Permutationen), aber **Beschneiden** reduziert die praktische Suche dramatisch.

## Wann verwenden / Fallstricke

Verwendung bei Constraint-Satisfaction und "alle gültigen Konfigurationen finden"-Problemen. Der Schlüsselvorteil ist **frühes Beschneiden** — überspringe Äste, die Constraints verletzen. Vergessen, den Zustand rückgängig zu machen ("Wahl rückgängig machen") ist der klassische Bug.

## Warum es wichtig ist

Backtracking ist der systematische Weg, kombinatorische Räume zu durchsuchen, ohne Kandidaten zu übersehen oder zu wiederholen.

Gutes Beschneiden verwandelt unhandliches Brute-Force in etwas, das rechtzeitig fertig wird.

Es treibt Solver für Rätsel, Scheduling und Constraint-Probleme in der gesamten Branche an.