Dans le Queens

Le casse-tête des N reines met le joueur au défi de placer N reines sur un échiquier NxN de manière à ce qu’aucune paire de reines ne se menace mutuellement. Étant donné qu’une reine peut attaquer sur sa ligne, sa colonne et ses deux diagonales, aucune paire de reines ne doit se trouver sur la même ligne, la même colonne ou la même diagonale. La version classique utilise un échiquier 8x8 avec 8 dames, mais le casse-tête peut être joué sur un échiquier de n'importe quelle taille à partir de 4x4 (il n'existe pas de solution pour les échiquiers 2x2 ou 3x3). Le nombre de solutions distinctes augmente rapidement avec la taille du plateau : le problème des 8 reines comporte 92 solutions (12 solutions uniques si l'on tient compte de la symétrie).

Règles

1. Placer N reines sur un échiquier de N × N cases.
2. Aucune paire de reines ne doit se trouver sur la même ligne.
3. Aucune paire de reines ne doit se trouver dans la même colonne.
4. Aucune paire de reines ne doit se trouver sur la même diagonale (dans les deux sens).
5. Les N reines doivent toutes être placées simultanément sur l'échiquier.

Stratégies

• Placement ligne par ligne : placez une reine par ligne, en commençant par le haut. Cela satisfait automatiquement la contrainte relative aux lignes et réduit le problème au choix d'une colonne pour chaque ligne.
• Suivi des colonnes : notez quelles colonnes sont déjà occupées. Chaque nouvelle reine doit être placée dans une colonne inoccupée.
• Suivi des diagonales : pour les deux directions diagonales, les cases situées sur une même diagonale partagent une valeur constante égale à (ligne - colonne) ou (ligne + colonne). Suivez ces valeurs pour identifier rapidement les cases sûres.
• Retour en arrière : si vous atteignez une ligne où aucune colonne n’est sûre, revenez à la ligne précédente et essayez la colonne disponible suivante. Cette approche systématique garantit de trouver une solution.
• Exploitation de la symétrie : Les solutions peuvent être pivotées de 90°, 180° ou 270° et réfléchies. Trouver une solution vous donne gratuitement jusqu’à 8 solutions associées.
• Commencez par les coins : Placer une reine dans un coin élimine immédiatement de nombreuses cases, ce qui, paradoxalement, peut faciliter le placement restant en réduisant les choix.

Le casse-tête des « N reines » trouve son origine dans le « casse-tête des huit reines », proposé pour la première fois en 1848 par le joueur d’échecs Max Bezzel dans la revue allemande Schachzeitung. Le défi consistant à placer huit reines sur un échiquier standard de manière à ce qu’aucune n’en attaque une autre a captivé l’imagination des mathématiciens comme des passionnés d’échecs.

Les premières solutions furent publiées en 1850 par Franz Nauck, qui généralisa également le problème à N reines sur un échiquier de taille N×N. Le grand mathématicien Carl Friedrich Gauss s’est intéressé à ce problème et a entretenu une correspondance à ce sujet avec son ami Heinrich Schumacher, bien qu’il n’ait initialement trouvé que 72 des 92 solutions pour le cas des 8 reines et ait cru à tort qu’il s’agissait de l’ensemble complet.

Ce casse-tête est devenu un problème fondamental en informatique. En 1972, Edsger Dijkstra a utilisé le problème des 8 reines pour illustrer la puissance de la programmation structurée et de l’algorithme de retour en arrière. Il reste l’un des exercices de programmation les plus couramment proposés dans les cours universitaires d’informatique, utilisé pour enseigner la récursivité, la satisfaction de contraintes et la conception d’algorithmes. Il sert également de référence pour comparer l’efficacité de différents algorithmes de recherche et techniques de propagation de contraintes.

Le problème des N reines présente des liens avec de nombreux domaines des mathématiques, notamment la combinatoire, la théorie des groupes (à travers ses symétries) et l’algèbre linéaire. En 2021, une avancée majeure a été réalisée lorsque Michael Simkin a démontré une formule asymptotique pour le nombre de solutions, confirmant ainsi une conjecture de longue date. Ce problème trouve également des applications pratiques dans le stockage parallèle de la mémoire, les tests de circuits VLSI et le contrôle du trafic. Malgré son énoncé en apparence simple, le problème des N reines continue de révéler de nouvelles profondeurs mathématiques.