Hvad er backtracking?

Question

Accepted Answer

**Backtracking** bygger kandidatløsninger trinvist og **opgiver** (trækker sig tilbage fra) en delvis kandidat så snart det ikke kan føre til en gyldig løsning. Det udforsker systematisk løsningsrummet via DFS og beskærer døde ender.

## Idéen

Vælg -> udforsk -> fortryd valget. Prøv en mulighed, gentag; hvis det mislykkes, fortryd og prøv den næste.

## Eksempel: alle permutationer

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

## Klassiske problemer

- **N-queens**, Sudoku, springerens tur.
- **Delmængder / kombinationer / permutationer.**
- **Ordsøgning**, løsning af labyrint.

## Kompleksitet

Oftest eksponentiel (f.eks. O(n!) for permutationer), men **beskæring** skærer det praktiske søgning dramatisk ned.

## Hvornår skal man bruge det / faldgruber

Brug til begrænsningssatisfiering og "find alle gyldige konfigurationer"-problemer. Den vigtigste fordel er **tidlig beskæring** — spring grene over, der krænker begrænsninger. At glemme at fortryde tilstand ("fortryd valget") er fejlen klassisk.

## Hvorfor det betyder noget

Backtracking er den systematiske måde at udforske kombinatoriske rum uden at misse eller gentage kandidater.

God beskæring forvandler en uovervindelig rå kraft til noget, der afsluttes til tiden.

Det driver løsere til puslespil, planlægning og begrænsningsproblemer på tværs af industrien.