Hva er bakoverføring?

Question

Accepted Answer

**Bakoverføring** bygger kandidatløsninger inkrementelt og **forlater** (sporer tilbake fra) en delvis kandidat så snart den ikke kan føre til en gyldig løsning. Den utforsker løsningsrommet systematisk via DFS og beskjærer døde sluttresultater.

## Ideen

Velg -> utforsk -> velg bort. Prøv et alternativ, rekurser; hvis det mislykkes, angre det og prøv det neste.

## Eksempel: alle permutasjoner

```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-dronninger**, Sudoku, ridderens tur.
- **Delmengder / kombinasjoner / permutasjoner.**
- **Ordsøk**, løsing av labyrint.

## Kompleksitet

Oft eksponentiell (f.eks. O(n!) for permutasjoner), men **beskjæring** reduserer det praktiske søket dramatisk.

## Når du skal bruke / fallgruver

Bruk for begrensningsoppfyllelse og "finn alle gyldige konfigurasjoner" problemer. Nøkkelvinstenets nøkkelvinnere er **tidlig beskjæring** — hopp over grener som bryter med begrensninger. Å glemme å angre tilstand ("velg bort") er den klassiske feilen.

## Hvorfor det er viktig

Bakoverføring er den systematiske måten å utforske kombinatoriske rom uten å misse eller gjenta kandidater.

God beskjæring gjør en håpløs brute force til noe som avsluttes i tide.

Det driver løsere for puslespill, planlegging og begrensningsproblemer på tvers av bransjen.