Che cos'è il backtracking?

Question

Accepted Answer

**Backtracking** costruisce soluzioni candidate in modo incrementale e **abbandona** (backtrack) un candidato parziale non appena non può portare a una soluzione valida. Esplora sistematicamente lo spazio delle soluzioni tramite DFS, potando i rami senza soluzione.

## L'idea

Scegli -> esplora -> annulla la scelta. Prova un'opzione, ricorri; se fallisce, annulla e prova la successiva.

## Esempio: tutte le permutazioni

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

## Problemi classici

- **N-queens**, Sudoku, il giro del cavallo.
- **Sottoinsiemi / combinazioni / permutazioni.**
- **Ricerca di parole**, risoluzione di labirinti.

## Complessità

Spesso esponenziale (es. O(n!) per permutazioni), ma la **potatura** riduce drasticamente la ricerca pratica.

## Quando usare / insidie

Utilizza per problemi di soddisfacimento di vincoli e "trova tutte le configurazioni valide". Il vantaggio principale è **potare presto** — salta i rami che violano i vincoli. Dimenticare di annullare lo stato ("annulla la scelta") è il bug classico.

## Perché è importante

Backtracking è il modo sistematico per esplorare spazi combinatoriali senza perdere o ripetere candidati.

Una buona potatura trasforma una ricerca esaustiva intrattabile in qualcosa che termina in tempo.

Fa funzionare i risolutori per puzzle, scheduling e problemi di vincoli in tutta l'industria.