Les sujets de Parisiennes incluent régulièrement des questions Python où l’énoncé définit un algorithme récursif et demande de l’implémenter ou de le compléter. Le backtracking est précisément un algorithme récursif avec contraintes et entre parfaitement dans ce cadre et pourrait donc tomber dans ces épreuves. Le problème des n-reines, que nous allons étudier, illustre parfaitement l’intérêt de ce type d’algorithme ! Dans cet article, nous allons poser le problème, montrer pourquoi la force brute est inefficace, implémenter le backtracking, puis l’optimiser.
Introduction
Le problème des n-reines est l’un des plus célèbres problèmes en algorithmique combinatoire. Il consiste à placer \(n\) reines sur un échiquier de taille \(n \times n\) de sorte qu’aucune reine ne s’attaque à une autre. Deux reines s’attaquent si elles sont sur la même ligne, la même colonne ou la même diagonale.
En prépa ECG, ce problème illustre parfaitement la méthode du backtracking (ou retour en arrière) : une stratégie où on construit progressivement une solution en explorant les chemins possibles, et on revient en arrière dès qu’on détecte qu’une branche ne peut pas mener à une solution valide.
Énoncé du problème
Définition
On dispose d’un échiquier de taille \(n \times n\). On veut placer \(n\) reines comme suit :
- une et une seule reine par ligne ;
- une et une seule reine par colonne ;
- aucune reine ne partage une diagonale avec une autre.
Pour \(n = 4\), une solution valide est : reines aux positions \((0,1)\), \((1,3)\), \((2,0)\), \((3,2)\) (où \((i,j)\) désigne la ligne \(i\) et la colonne \(j\)).
Pourquoi c’est difficile
Si on ignore les contraintes, il y a \(n^2\) cases où placer la première reine, \((n^2 – 1)\) pour la deuxième, etc., soit par itérations \((n^2)!\) configurations possibles pour placer \(n\) reines. Même avec les contraintes, le nombre de configurations à vérifier est immense : pour \(n = 8\), il y a \(8! = 40\,320\) façons de placer une reine par colonne, et vérifier chaque configuration naïvement (c’est-à-dire par méthode force brute) peut être fastidieux.
C’est pourquoi le backtracking est indispensable. En effet, cette méthode permet d’éliminer les branches impossibles sans les explorer entièrement et donc gagner un temps précieux dans un cas de grande dimension \(n\).
Approche force brute
Principe
Une première approche consiste à générer toutes les permutations des colonnes (puisqu’on met une reine par ligne et une par colonne), puis à vérifier si chaque permutation satisfait les contraintes diagonales. On appelle cela la méthode force brute, puisqu’on implémente chaque possibilité et on vérifie ex post que ces dernières vérifient les conditions du problème.
Voici un algorithme qui permet d’implémenter cela en Python :
Analysons ensemble ce premier script
On commence par définir une fonction verifier_diagonales qui prend en argument une permutation et vérifie que deux reines i et j ne partagent pas de diagonale. La condition abs(solution[i] – solution[j]) == abs(i – j) capture exactement cela : si la différence de colonnes est égale à la différence de lignes, les deux reines sont sur la même diagonale.
La fonction brute_force_n_reines génère ensuite toutes les permutations de range(n) grâce à itertools.permutations : chaque permutation représente une façon de placer une reine par ligne et une par colonne. Pour chaque permutation, on vérifie les contraintes diagonales et on ajoute la configuration à la liste solutions si elle est valide.
Cette approche est correcte mais inefficace : elle génère systématiquement toutes les n! permutations sans jamais éliminer les chemins voués à l’échec en cours de route.
Inefficacité
Cette approche génère \(n!\) permutations et vérifie chacune en \(O(n^2)\), soit une complexité totale en \(O(n! \cdot n^2)\). Pour \(n = 10\), cela signifie \(10! \times 100 = 362\,880\,000\) opérations.
De plus, cette approche explore des chemins qui sont voués à l’échec bien avant la fin : par exemple, si les deux premières reines s’attaquent déjà, pas besoin de placer les autres, puisque cela complexifie les vérifications, alors que l’on est certain de ne pas être en présence d’une solution convenable.
Backtracking
Principe
Le backtracking place les reines ligne par ligne. À chaque étape, on essaie de placer la reine courante dans chaque colonne libre, puis on vérifie immédiatement si elle s’attaque à une reine déjà placée.
Si oui, on essaie la colonne suivante. À l’inverse, on passe à la ligne suivante. Si on place avec succès les \(n\) reines, on a trouvé une solution. Si on ne peut placer la reine courante nulle part, on revient en arrière (on déplace la reine précédente) et on essaie une autre colonne.
Implémentation
Analysons ensemble ce deuxième script
La fonction backtracking_n_reines définit deux fonctions imbriquées, ce qui leur permet d’accéder à solutions et à n directement sans les passer en argument. La première, est_securisee, vérifie si placer une reine à la position (ligne, colonne) est compatible avec toutes les reines déjà placées aux lignes 0 jusqu’à ligne – 1 : on vérifie l’égalité de colonne et les deux diagonales via abs(col_reine – colonne) == abs(i – ligne). On n’a besoin de vérifier que les lignes précédentes : en effet, les lignes futures ne contiennent encore aucune reine.
La seconde fonction, placer, est la fonction récursive centrale. Si toutes les n reines sont placées (ligne == n), on ajoute une copie de la solution avec solution[:], et non solution directement car solution est une liste mutable et on perdrait toutes les solutions précédentes si on stockait uniquement la référence.
Si toutes les reines ne sont pas placées encore, on essaie chaque colonne : si la position est sécurisée, on place la reine, on appelle récursivement placer pour la ligne suivante, puis on retire la reine avec solution[ligne] = -1 pour laisser cette case disponible et explorer les colonnes suivantes.
C’est cette dernière ligne qui constitue la définition même du retour en arrière du backtracking : on défait la dernière décision pour en essayer une autre.
Efficacité
Le backtracking explore seulement les branches viables, ce qui permet à cet algorithme d’être particulièrement redoutable par rapport à un algorithme de type force brute. Dès qu’on détecte un conflit, on élimine une sous-arborescence. Pour \(n = 8\), l’algorithme explore environ \(15\,000\) positions au lieu des \(8! = 40\,320\) permutations que l’on aurait en force brute, soit une réduction d’environ 60 %.
Combien de solutions existe-t-il ?
Script de comptage
Une question naturelle se pose : combien de configurations valides existe-t-il pour chaque valeur de \(n\) ? On peut y répondre en une dizaine de lignes en appelant le backtracking pour chaque valeur de \(n\) de \(1\) à \(12\) et en comptant le nombre de solutions trouvées.
On initialise une liste resultats vide, puis on boucle sur n de 1 à 12. Pour chaque valeur, on appelle backtracking_n_reines(n) et on stocke la longueur de la liste renvoyée, c’est-à-dire le nombre de solutions. On affiche ensuite les résultats avec une f-string alignée pour avoir un beau formatage de réponse (voir cet article sur le formatage des solutions).
Résultats et interprétation
On obtient alors :
n=1 : 1 solution
n=2 : 0 solution
n=3 : 0 solution
n=4 : 2 solutions
n=5 : 10 solutions
n=6 : 4 solutions
n=7 : 40 solutions
n=8 : 92 solutions
n=9 : 352 solutions
n=10 : 724 solutions
n=11 : 2 680 solutions
n=12 : 14 200 solutions
Pour \(n = 2\) et \(n = 3\), on remarque qu’il n’existe aucune solution : avec seulement deux ou trois cases de côté, il est impossible de placer autant de reines sans qu’elles se menacent mutuellement. Pour \(n = 4\), il n’existe que deux solutions, symétriques l’une de l’autre.
Le cas \(n = 8\) est le plus célèbre : les 92 solutions de l’échiquier standard sont connues depuis le \(XIX^e\) siècle et constituent l’un des premiers problèmes combinatoires étudiés systématiquement. On remarque également que le nombre de solutions n’est pas monotone : \(n = 6\) donne quatre solutions, tandis que \(n = 5\) en donne dix, ce qui illustre que la géométrie de l’échiquier joue un rôle non trivial.
Au-delà de \(n = 12\), le temps de calcul augmente rapidement, puisque le nombre de solutions possibles augmente !
Conclusion
En définitive, le problème des n-reines illustre comment le backtracking réduit drastiquement l’espace de recherche en éliminant les branches impossibles dès qu’elles sont détectées. Implémenter le backtracking, comprendre le rôle du « retour en arrière » dans cet algorithme et savoir l’optimiser avec des structures de données efficaces sont trois compétences directement évaluables dans des épreuves corsées de type Maths I.
Il n’y a plus qu’à croiser les doigts pour qu’un tel thème tombe aux concours !
Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !
