Wat is backtracking?

Question

Accepted Answer

**Backtracking** bouwt kandidaatoplossingen incrementeel op en **verlaat** (backtracking) een gedeeltelijke kandidaat zodra deze niet tot een geldige oplossing kan leiden. Het verkent de oplossingruimte systematisch via DFS en snoeidt doodslopende wegen weg.

## Het idee

Kies -> verken -> ontkies. Probeer een optie, recurse; als het mislukt, maak het ongedaan en probeer de volgende.

## Voorbeeld: alle permutaties

```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
```

## Klassieke problemen

- **N-queens**, Sudoku, de tocht van het paard.
- **Deelverzamelingen / combinaties / permutaties.**
- **Woordzoeken**, doolhof-oplosser.

## Complexiteit

Vaak exponentieel (bijvoorbeeld O(n!) voor permutaties), maar **snoeien** verkleint de praktische zoekopdracht drastisch.

## Wanneer te gebruiken / valkuilen

Gebruik voor beperkingsvoldoening en "alle geldige configuraties zoeken" problemen. Het belangrijkste voordeel is **vroeg snoeien** — overslaan takken die beperkingen schenden. Vergeten de status ongedaan te maken ("ontkies") is de klassieke fout.

## Waarom het belangrijk is

Backtracking is de systematische manier om combinatorische ruimten te verkennen zonder kandidaten te missen of te herhalen.

Goed snoeien verandert een onhandelbare brute force in iets dat op tijd klaar is.

Het voorziet oplossingsprogramma's voor puzzels, planning en beperkingsproblemen in de hele industrie van stroom.