problème des n reines

Imaginez un échiquier et posez une reine. Elle menace toutes les cases de sa ligne, de sa colonne et de ses deux diagonales. Il faut ensuite placer les autres reines uniquement sur les cases qui échappent à ces directions.

Le défi grandit avec l'échiquier : pour n lignes et n colonnes, il faut placer exactement n reines. Une disposition réussie contient donc une reine par ligne et par colonne, sans alignement diagonal.

Le problème des n reines est un problème de placement sur un échiquier carré comportant n lignes et n colonnes. Il demande de choisir n cases pour que deux reines distinctes ne partagent ni une ligne, ni une colonne, ni une diagonale. Comme il y a autant de reines que de lignes et de colonnes, toute solution place nécessairement une reine dans chacune d'elles.

On peut décrire une disposition par la ligne occupée dans chaque colonne. Si la reine de la colonne i occupe la ligne q_i, les nombres q_i sont tous différents. Pour deux colonnes distinctes i et j, l'absence d'attaque diagonale impose aussi $\mathrm{\mid }{q}_i-q_j\mathrm{\mid }\mathrm{\ne }\mathrm{\mid }i-j\mathrm{\mid }|q\_i-q\_j|\; \backslash neq\; |i-j|$. Ces deux conditions suffisent à caractériser une solution.

Le cas n = 8 est le problème historique des 8 reines. Il possède 92 solutions si chaque orientation compte séparément, mais 12 seulement lorsque les rotations et les réflexions d'une même disposition sont regroupées. Le problème fournit ainsi un exemple classique de satisfaction de contraintes et de retour sur trace.

Prenons n = 4. Les colonnes sont numérotées de 1 à 4, comme les lignes. La disposition proposée place les reines aux lignes 2, 4, 1 et 3, dans cet ordre de colonnes. Une représentation de cette disposition permet de contrôler les trois interdictions.

1. On place une reine en colonne 1, ligne 2.
2. En colonne 2, la ligne 4 évite sa ligne et ses diagonales.
3. En colonne 3, la ligne 1 n'est menacée par aucune des deux premières reines.
4. En colonne 4, la ligne 3 complète la disposition sans conflit.

Les lignes occupées sont 2, 4, 1 et 3 : chacune apparaît une fois. Pour le contrôle diagonal, les différences de lignes entre deux reines valent successivement 2, 1, 1, 3, 1 et 2, tandis que les écarts de colonnes correspondants valent 1, 2, 3, 1, 2 et 1. Aucun couple n'a deux écarts égaux. La disposition est donc une solution du problème des 4 reines.

Pour chercher une solution à la main, on avance colonne par colonne. À chaque étape, on barre les lignes et diagonales déjà menacées, puis on choisit une case encore disponible.

Si une colonne ne contient plus aucune case possible, le retour sur trace consiste à revenir au dernier choix et à essayer une autre case. Une exploration exhaustive serait préférable seulement si le nombre de dispositions à examiner reste assez petit.

Pour contrôler une disposition donnée, il suffit d'abord de compter une reine par ligne et par colonne, puis de comparer les écarts de lignes et de colonnes de chaque paire. Des écarts égaux révèlent une diagonale commune.

Le problème des n reines est la question à résoudre ; le retour sur trace est une méthode possible pour la résoudre. Une disposition sans attaque répond au problème, même si elle a été trouvée sans cet algorithme.

Un problème de satisfaction de contraintes désigne une famille plus large de problèmes. Les n reines en sont un exemple précis : les variables indiquent les positions, et les contraintes interdisent les lignes, colonnes ou diagonales communes.

Le seuil n ≥ 4 ne signifie pas que tous les plus petits cas échouent. Pour n = 1, l'unique reine constitue déjà une solution. Pour n = 2 ou n = 3, aucune disposition ne satisfait simultanément les trois interdictions.

Le nombre 92 pour n = 8 compte séparément les dispositions orientées sur l'échiquier. Si l'on identifie celles qui se déduisent l'une de l'autre par rotation ou réflexion, il reste 12 solutions fondamentalement distinctes. Il faut donc préciser la convention avant de comparer un dénombrement.

Une reine par ligne et par colonne ne suffit pas. La disposition 1, 2, 3, 4 sur un échiquier 4 × 4 respecte ces deux comptages, mais place toutes les reines sur la même diagonale. Le contrôle des paires reste indispensable.

L'entrée algorithme précise ce qu'est une procédure finie et organisée, cadre utile pour formaliser le retour sur trace.

L'analyse combinatoire élargit la perspective vers les méthodes qui organisent et dénombrent des configurations soumises à des contraintes.