Sur un échiquier, la dame est une pièce redoutable car sa simple position rend de nombreuses autres cases invalides. Pour transformer cette situation en problème de recherche, on commence par définir précisément quelles cases une dame attaque ; on peut alors considérer ces attaques comme des contraintes qui invalident les placements potentiels. Cette approche est importante car elle permet à un algorithme de résolution de construire une solution étape par étape et d’écarter les candidats partiels dès qu’ils enfreignent une règle, plutôt que d’attendre que l’échiquier soit entièrement rempli.
Un placement n’est valide que si aucune dame n’en attaque une autre, ce qui implique le respect simultané de trois contraintes. Deux dames ne peuvent pas se trouver sur la même ligne, sur la même colonne ni sur la même diagonale.
Pour mieux visualiser ces contraintes, observez comment une dame placée à des coordonnées précises marque les cases attaquées sur un petit échiquier.
Les contraintes de ligne et de colonne sont directes, car toute case partageant le même indice de ligne ou de colonne est attaquée. La contrainte de diagonale repose également sur un mécanisme simple : les cases restent sur une même diagonale lorsque leurs indices de ligne et de colonne varient simultanément ; ainsi, une dame attaque les cases situées le long des deux diagonales jusqu’à ce que le bord du plateau interrompe la ligne.
Une fois les contraintes bien définies, l’étape suivante consiste à choisir une représentation facilitant la construction progressive de solutions candidates. Une solution simple consiste à utiliser un tableau unidimensionnel tel que queens[row] = col, signifiant que la dame située à la ligne row est placée dans la colonne col. Avec cette représentation, la contrainte de ligne est respectée par construction, puisque chaque indice de ligne n’apparaît qu’une seule fois.
Le widget illustre la correspondance entre un tableau donné et une configuration du plateau représentée graphiquement.