Problème des N-Reines
Backtracking classique sur échiquier
Enonce
Implémenter n_reines(n) qui renvoie le nombre de placements valides distincts de $n$ reines sur un échiquier $n \times n$.
On attend par exemple n_reines(4) == 2, n_reines(8) == 92.
⚠ Méthode : backtracking récursif. Placer une reine par ligne, élaguer dès qu'un conflit apparaît.
Signature attendue
def n_reines(n: int) -> int:Exemples
n_reines(1)→1n_reines(2)→0 (impossible)n_reines(3)→0 (impossible)
📖 Rappel de cours
Problème historique (1848, Max Bezzel) : placer $n$ reines sur un échiquier $n \times n$ de telle sorte qu'aucune ne puisse en attaquer une autre. Deux reines s'attaquent si elles sont sur la même ligne, la même colonne ou la même diagonale.
Stratégie (backtracking) :
- On place une reine par ligne (il ne peut y en avoir qu'une par ligne).
- Pour la ligne $\ell$, on essaie chaque colonne $c \in \{0, \ldots, n-1\}$.
- Si $(l, c)$ ne conflit avec aucune des reines déjà placées : on avance à la ligne suivante, sinon on essaie une autre colonne.
- Si on a placé toutes les reines : solution trouvée. Si plus aucune colonne ne marche : on revient en arrière (backtrack).
Test de conflit diagonal :
Deux cases $(l_1, c_1)$ et $(l_2, c_2)$ sont sur une même diagonale ssi $|c_1 - c_2| = |l_1 - l_2|$.
Valeurs : $n = 4 \to 2$ solutions, $n = 8 \to 92$, $n = 10 \to 724$, $n = 12 \to 14200$.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Chemins dans une Grille
- Distance d'Édition (Levenshtein)
- Rendu de Monnaie (DP)
- Traitement d'Image — Seuillage et Barycentre
- Algorithme de Bresenham
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.