Le problème des dames

Poser $n$ dames sur un échiquier de $n$ sur $n$, de 4 à 10, sans que deux d'entre elles se menacent. Une solution est une permutation soumise à deux conditions sur les diagonales ; on les compte toutes par retour arrière.

Sur un échiquier de $n$ lignes et $n$ colonnes, avec $n$ de $4$ à $10$, on pose et l'on retire des dames ; deux dames se menacent si elles partagent une ligne, une colonne ou une diagonale. Il faut en poser $n$ sans aucune menace. La page encadre les dames qui se menacent, teinte les cases menacées, signale l'impasse quand il ne reste plus aucune case libre, et peut ajouter sur demande une dame qui ne ferme pas la porte.

Ce que cela signifie : une solution a exactement une dame par ligne et par colonne, c'est donc une permutation $\sigma$ de $\{1, \dots, n\}$, et les conditions sur les diagonales s'écrivent : les nombres $i - \sigma(i)$ sont deux à deux distincts, ainsi que les nombres $i + \sigma(i)$. On ne connaît pas de formule pour le nombre de solutions ; la page les énumère par retour arrière et trouve $2$, $10$, $4$, $40$, $92$, $352$ et $724$ solutions pour $n$ de $4$ à $10$. Pour $n = 8$, les $92$ solutions, parmi $8! = 40\,320$ permutations, forment $12$ familles sous les huit symétries du carré.

Le piège le plus courant est de croire qu'une position sans menace mène toujours à une solution : sur l'échiquier de $8$ sur $8$, une dame en ligne $1$, colonne $1$ et une autre en ligne $2$, colonne $3$ ne se menacent pas, mais aucune solution ne les contient toutes les deux.