Le problème des reines

Dans ma dernière vidéo, j’abordais le lien entre les carrés magiques et le problème des reines. Dans ce dernier, l’énigme consistait à placer n reines sur un échiquier de taille n x n sans qu’aucune reine ne puisse en attaquer une autre.

Des solutions existent pour toute taille d’échiquier strictement supérieure à 3… Il est temps de s’y atteler !

Le problème aux origines

Au départ, il n’y avait qu’un échiquier classique, de taille 8 x 8, et c’est un joueur d’échec allemand, Max Bezzel, qui proposa l’énigme en 1848. En 1850, un certain Carl Friedrich Gauss affirma que ce problème présentait au total 92 solutions (en comptant toutes les possibilités, y compris celles qui ne sont que des rotations d’autres solutions de ce problème).

Mais comme pour tout problème de mathématique, il serait dommage de s’arrêter à un cas particulier. On se demanda alors si le même problème était résoluble pour des tailles d’échiquier différentes.

Notons d’abord que, puisqu’il ne peut y avoir qu’une seule reine par colonne, écrire une solution revient à écrire une liste comportant une seule et unique fois chaque entier de 1 à n. Ces nombres représentent les lignes sur lesquelles placer nos reines. Par exemple, sur l’échiquier 5 x 5 qui suit, la solution présentée peut se résumer par la liste ( 3 ; 5 ; 2 ; 4 ; 1 )

Solution 5 x 5

Une solution pour l’échiquier 5 x 5

Comment alors se rendre compte si la solution donnée est correcte ?

Prenez chaque nombre de cette liste et ajoutez-y le numéro de sa colonne – sa position dans la liste.

Pour le cas précédent, cela donne ( 3 + 1 ; 5 + 2 ; 2 + 3 ; 4 +4 ; 1 + 5 ) soit (4 ; 7 ; 5 ; 8 ; 6). On remarque que tous les nombres obtenus sont différents.

Maintenant, reprenez la liste de départ, et retirez à chaque nombre sa position, sa colonne. Dans l’exemple on a ( 3 – 1 ; 5 – 2 ; 2 – 3 ; 4 – 4 ; 1 – 5 ), soit (2 ; 3 ; -1 ; 0 ; -4). Là encore, tous les nombres sont différents… Eh bien, avec ces deux critères, nous pouvons affirmer que notre liste donne bien une solution au problème des reines.

En effet, récapitulons les conditions au problème de la reine.

  • Il ne peut y avoir qu’une reine par colonne. C’est pour cela que nous pouvons résumer un placement des reines avec des nombres entiers.
  • Il y a une et unique reine par ligne : tous les nombres de 1 à n doivent être présents une et une seule fois dans la liste.
  • Deux reines ne doivent pas partager la même diagonale. C’est ce que l’on vérifie en faisant cette manipulation.

Regardons par exemple ce placement, qui n’est pas une solution du problème des reines.

Placement incorrect

Ce placement s’écrit (1 ; 4 ; 3 ; 5 ; 2). Il respecte les deux premières conditions. Ajoutons donc à chaque nombre sa position dans la liste.

( 1 + 1 ; 4 + 2 ; 3 + 3 ; 5 + 4 ; 2 + 5) fait (2 ; 6 ; 6 ; 9 ; 7). On voit apparaître le nombre 6 en 2ème et 3ème position : c’est parce que les reines des deuxièmes et troisièmes colonnes sont sur la même diagonale ascendante.

Faisons de même avec la soustraction ( 1 – 1 ; 4 – 2 ; 3 – 3 ; 5 – 4 ; 2 – 5), ce qui fait
(0 ; 2 ; 0 ; 1 ; -3). Cette fois, le 0 apparaît en 1ère et 3ème position : c’est parce que les reines des premières et troisièmes colonnes sont sur la même diagonale descendante.

Un test fort pratique donc ! Pour les amateurs de permutation, on cherche donc une permutation P de l’ensemble des entiers de 1 à n telle que P + id et P – id soient injectives. Oui, d’un coup, ça fait plus savant et sérieux que placer des dames sur du carrelage.

D’accord, mais nous on veut les solutions !

Passons donc aux choses sérieuses. Plusieurs cas existent, suivant la taille de votre échiquier.

Cas n°1 : La taille de votre échiquier n’est pas de la forme 6k + 2 ou 6k + 3.

C’est le cas d’un échiquier de taille 5, 6, 7, mais pas de taille 8, puisque 8 = 6 x 1 + 2, ni de 39, puisque 39 = 6 x 6 + 3. Ce cas est très simple puisqu’il suffit de placer les reines en « L ».

Placez une reine sur la deuxième case en partant du bas sur la première colonne. Puis avancez d’une case à droite et deux cases en haut, placez une nouvelle reine. Et ainsi de suite, jusqu’à dépasser du bord supérieur. Placez alors une reine tout en bas dans la colonne suivante et recommencez. Vous avez votre solution !

Solution pour 7

Une solution en escalier pour un échiquier 7 x 7

Cas n°2 : La taille de votre échiquier est de la forme 6k + 2

C’est le cas de 8, 14, 20, et ainsi de suite, de 6 en 6.

Placez les nombres paires d’un côté et les nombres impairs de l’autre. Pour 8, cela donne (2 ; 4 ; 6 ; 8 ; 1 ; 3 ; 5 ; 7).

Inversez le 1 et le 3, puis placez le 5 à la fin : (2 ; 4 ; 6 ; 8 ; 3 ; 1 ; 7 ; 5). Terminé !

Solution 14 x 14

Une solution pour le problème 14 x 14

Cas n°3 La taille de votre échiquier est de la forme 6k + 3

C’est le cas de 9, 15, 21 et ainsi de 6 en 6.4

De la même manière, séparons la liste des entiers selon la parité. Pour 15, cela donnerait donc (2 ; 4 ; 6 ; 8 ; 10 ; 12 ; 14 ; 1 ; 3 ; 5 ; 7 , 9 , 11 ; 13 ; 15)

Il faut ensuite placer le 2 à la fin de la liste des pairs puis le 1 et le 3 à la fin de la liste des impairs, ce qui donne ( 4 ; 6 ; 8 ; 10 ; 12 ; 14 ; 2 ; 5 ; 7 ; 9  ; 11 ; 13 ; 15 ; 1 ; 3)

Solution sur l’échiquier 15×15

Et c’est terminé !

Combien de solutions ?

C’est bien beau tout ça, mais combien de solutions a-t-on ? Ces nombres ont été déterminés pour des échiquiers de taille allant jusqu’à 27 : on compte 234907967154122528 – plus de 200 millions de milliards – solutions au total, ce qui se réduit à 29363495934315694 – plus que 29 millions de milliards.

Les plus curieux pourront consulter les séquences A002562 et A000170 sur l’OEIS.

Pour le reste, nul ne sait vraiment. L’hypothèse a été faite que le nombre total était de l’ordre de n!/c où c est un réel, environ égal à 2,54, mais nul ne le sait vraiment. Alors, si vous vous ennuyez un jour…

Pour aller plus loin

Cet article, publié dans Curiosités et récréation, est tagué , , , , , . Ajoutez ce permalien à vos favoris.

Un commentaire pour Le problème des reines

  1. Une actu plus récente : le problème « queens completion » a été démontré NP-complet en 2017 (https://jair.org/index.php/jair/article/view/11079/26262). Donc le problème devient difficile si certaines reines sont déjà placées.

    J'aime

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s