♛ Le retour arrière à l'œuvre sur l'échiquier
L'algorithme pose une reine par colonne, de gauche à droite. Quand il est coincé, il revient en arrière (backtrack) et essaie une autre case. Regarde-le débusquer les 92 solutions.
Solutions trouvées
0 / 92
Reines posées
0 / 8
Retours arrière
0
Échiquier vide. Appuie sur « Résoudre » pour lancer le retour arrière, ou « Solution suivante » pour avancer vers la prochaine configuration valide.
♛ Le défi (Max Bezzel, 1848)
En 1848, le joueur d'échecs allemand Max Bezzel pose une question d'apparence innocente dans une revue spécialisée : peut-on placer 8 reines sur un échiquier 8 × 8 de telle sorte qu'aucune n'en attaque une autre ?
Aux échecs, la reine (la dame) est la pièce la plus puissante : elle balaie toute sa ligne, toute sa colonne et ses deux diagonales. Le problème revient donc à disposer 8 reines sans que deux d'entre elles partagent jamais une ligne, une colonne ou une diagonale. Simple à énoncer, redoutable à résoudre à la main.
Le grand Carl Friedrich Gauss s'y intéresse dès 1850 et en dénombre, après quelques tâtonnements et une erreur initiale, les solutions. La réponse finale est devenue célèbre : il existe exactement 92 solutions.
Le résultat clé
Sur un échiquier 8 × 8, il existe exactement
92 solutions → 12 fondamentales par symétrie
🔢 Pourquoi c'est un problème de combinatoire
Combien y a-t-il de façons de poser 8 reines sur 64 cases ? Si l'on choisit librement 8 cases parmi 64, le nombre de placements est énorme :
C(64, 8) = 4 426 165 368 ≈ 4,4 milliards
Plus de 4 milliards de configurations à examiner ! Tester chacune une par une serait absurde. Mais une remarque simple change tout : dans une solution valide, il y a exactement une reine par colonne (sinon deux reines partageraient une colonne). On peut donc se contenter de choisir, pour chacune des 8 colonnes, l'une des 8 lignes. Cela ramène l'espace de recherche à :
88 = 16 777 216 ≈ 16,8 millions
On passe de 4,4 milliards à ~16,8 millions rien qu'en exploitant une contrainte évidente. Si l'on ajoute « une reine par ligne aussi », on tombe sur les 8! = 40 320 permutations à tester. C'est déjà beaucoup moins — mais on peut faire infiniment mieux grâce au retour arrière.
↩️ Le retour arrière (backtracking) : essayer, échouer, revenir
Le retour arrière est l'une des idées algorithmiques les plus fondamentales de l'informatique. Plutôt que d'engendrer toutes les configurations puis de les filtrer, on construit la solution pas à pas et on abandonne dès qu'une piste est sans espoir.
Algorithme placer(colonne c) :
- Si c = 8 : toutes les colonnes sont remplies → solution trouvée !
- Pour chaque ligne r de 0 à 7 :
- Si la case (r, c) n'est attaquée par aucune reine déjà posée → on pose la reine.
- On appelle placer(c + 1).
- On retire la reine (RETOUR ARRIÈRE) et on essaie la ligne r suivante.
- Si plus aucune ligne ne convient → on revient à la colonne précédente.
L'élégance vient de l'élagage : dès qu'une reine en crée un conflit, on ne perd plus de temps à explorer les colonnes suivantes — toute une branche de l'arbre des possibilités est coupée d'un coup. Là où la force brute examinerait des millions de positions, le retour arrière n'en visite que quelques milliers. C'est la différence entre fouiller chaque grain de sable et suivre une carte au trésor.
Le test « la case est-elle attaquée ? » est immédiat : deux reines en (r₁, c₁) et (r₂, c₂) sont en conflit si r₁ = r₂ (même ligne), ou si |r₁ − r₂| = |c₁ − c₂| (même diagonale). Comme on place une reine par colonne, le conflit de colonne ne peut jamais se produire.
🌍 Et avec n reines ? L'explosion combinatoire
Le problème se généralise naturellement au problème des n reines sur un échiquier n × n. On sait qu'une solution existe pour tout n ≥ 4. Mais compter le nombre de solutions devient vertigineux :
- n = 8 : 92 solutions.
- n = 10 : 724 solutions.
- n = 12 : 14 200 solutions.
- n = 27 : 234 907 967 154 122 528 solutions (un record de calcul atteint en 2016).
Attention à une idée reçue fréquente : trouver une solution n'est pas NP-difficile. Il existe des méthodes directes qui en construisent une rapidement pour tout n. Ce qui explose, c'est le dénombrement de toutes les solutions : aucune formule close n'est connue, et le nombre de configurations à explorer croît plus vite que n'importe quelle exponentielle simple. C'est un terrain d'essai favori pour les algorithmes de satisfaction de contraintes.
🤖 Bien plus qu'un jeu : les CSP
Le problème des 8 dames est devenu l'exemple canonique d'une famille de problèmes majeurs en intelligence artificielle : les problèmes de satisfaction de contraintes (CSP, Constraint Satisfaction Problems). Le schéma est toujours le même : des variables (où poser chaque reine), des domaines (les lignes possibles), et des contraintes (ne pas s'attaquer).
Exactement la même machinerie — variables, domaines, contraintes, retour arrière — résout des problèmes bien réels :
- Planification : emplois du temps scolaires, horaires de trains, affectation des salles sans chevauchement.
- Allocation de ressources : attribuer des fréquences radio à des antennes sans interférence, colorier une carte avec un minimum de couleurs.
- Configuration industrielle : assembler un produit en respectant toutes les compatibilités entre composants.
- Sudoku et casse-têtes logiques : un Sudoku n'est rien d'autre qu'un gros CSP résolu par retour arrière et propagation de contraintes.