Qu'est-ce que le backtracking ?

Question

Accepted Answer

**Le backtracking** construit des solutions candidates de manière incrémentale et les **abandonne** (revient en arrière) dès qu'une solution partielle ne peut pas mener à une solution valide. Il explore systématiquement l'espace des solutions via DFS, en élaguant les branches mortes.

## L'idée

Choisir -> explorer -> dé-choisir. Essayer une option, récurser ; si elle échoue, l'annuler et essayer la suivante.

## Exemple : toutes les permutations

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

## Problèmes classiques

- **N-reines**, Sudoku, la tournée du cavalier.
- **Sous-ensembles / combinaisons / permutations.**
- **Recherche de mots**, résolution de labyrinthes.

## Complexité

Souvent exponentielle (par exemple, O(n!) pour les permutations), mais **l'élagage** réduit drastiquement la recherche pratique.

## Quand l'utiliser / pièges

Utilisez-le pour les problèmes de satisfaction de contraintes et de « trouver toutes les configurations valides ». Le gain clé est **l'élagage précoce** — ignorer les branches qui violent les contraintes. Oublier d'annuler l'état (« dé-choisir ») est le bug classique.

## Pourquoi c'est important

Le backtracking est le moyen systématique d'explorer les espaces combinatoires sans manquer ou répéter de candidats.

Un bon élagage transforme une force brute intraitable en quelque chose qui se termine à temps.

Il alimente les solveurs pour les puzzles, l'ordonnancement et les problèmes de contraintes dans toute l'industrie.