♛

Les 8 Reines

Toutes les solutions · Algorithme · Visualisation interactive

1 / 92
87 65 43 21
AB CD EF GH
Reine
Attaquée

Positions

Tableau numérique
Notation algébrique
Index = colonne (0→7), valeur = ligne (0→7)
0
Appels récursifs
0
Backtracks
0
Solutions
—
Colonne
Vitesse
Prêt à démarrer…
Plateau en cours
function solve(col) {
if (col === 8) { // base case
solutions.push([...queens]) // 🎉 trouvé !
return
}
for (let row = 0; row < 8; row++) {
if (isSafe(col, row)) { // tester
queens[col] = row // placer
solve(col + 1) // récursion
queens[col] = -1 // backtrack !
}
}
}

92 solutions

Cliquez pour voir en détail

Le problème

Placer 8 reines sur un échiquier 8×8 de façon à ce qu'aucune reine ne puisse en attaquer une autre — ni en ligne, ni en colonne, ni en diagonale.

92
solutions
12
solutions fondamentales
(sans symétries)

Règles de non-attaque

  • ↔Pas deux reines sur la même ligne : queens[i] ≠ queens[j]
  • ↕Pas deux reines sur la même colonne : garantie par la structure (une par colonne)
  • ↗Pas deux reines sur la même diagonale : |col_i − col_j| ≠ |row_i − row_j|

L'algorithme : Backtracking

  • On traite une colonne à la fois (col 0 à 7). Une seule reine par colonne.
  • Pour chaque colonne, on essaie les 8 lignes possibles.
  • Si la position est sûre → on place la reine et on passe à la colonne suivante (récursion).
  • Si aucune ligne ne convient → backtrack : on retire la dernière reine et on essaie la suivante.
  • Quand col === 8 : toutes les reines sont placées → solution trouvée !
Complexité : ~15 720 appels récursifs pour 92 solutions