Le problème des 8 reines

Entrons dans le problème : sur un échiquier, on cherche à placer des reines de telle sorte qu’elles ne soient pas en position de se prendre. Les reines peuvent se déplacer horizontalement, verticalement ou en diagonale, d’autant de cases qu’elles le souhaitent. On dit qu’une reine en prend une autre si cette dernière se retrouve sur le chemin de la première.

Cela ne paraît pas très compliqué, à première vue il suffit d’avoir un damier et des pièces, puis de chercher une solution.

Intuitivement, on voit qu’en essayant toutes les combinaisons, on a des chances de trouver une situation acceptable (qui respecte les contraintes du problème). Cependant, le temps pour trouver une solution risque d’être long… puisqu’il y a 64⁸ possibilités = 281 474 976 710 656 différentes situations. Il est évident qu’un bon nombre de situations ne seront pas acceptables puisque des reines se retrouveraient sur les mêmes cases. Nous devons donc chercher un autre moyen de trouver une solution.

Danser pour trouver sa place

Dans la suite de cet article, nous proposons d’illustrer la recherche d’une solution avec des danseuses et du backtracking (retour sur trace).

Nous utiliserons une vidéo produite par l’université Sapientia qui illustre les différentes étapes de l’algorithme. Les reines sont des danseuses qui prennent position sur la scène. Pour raccourcir les explications, la vidéo restreint le problème à quatre reines. À chaque fois, vous aurez accès à l’extrait de la vidéo juste après les explications.

Regardons ce qui se passe. Pour commencer, la première reine choisit la première ligne et s’installe sur la première case:

Puis une seconde reine arrive. Comme pour la première, elle choisit la ligne suivante. On note que la première est de toute façon inaccessible car occupée par la première reine. Notre deuxième reine tente de s’installer sur la première case de la seconde ligne.

La première reine veille et repousse la seconde qui était sur la même colonne !

Elle peut ainsi tenter la case suivante. Malheur ! Elle se retrouve sur la diagonale de la première qui la repousse comme on peut le voir ci-dessous.

La case suivante ne pose pas de problème ! Parfait la nouvelle reine trouve une place.

Sur notre damier de 4 cases sur 4 nous avons réussi à placer correctement 2 reines.

La figure ci-dessous nous permet d’avoir une vue d’ensemble. La reine de la première ligne est installée sur la première case de cette ligne, d’où le chiffre 1 en vert au bout de la ligne et les cases qu’elle rend inaccessibles sont identifiées par les lignes jaunes. La deuxième reine, sur la deuxième ligne, est sur la troisième case de la ligne, d’où le chiffre 3 en vert, et les cases qu’elle rend inaccessibles sont identifiées par les lignes bleues.

On peut ainsi regarder les cases du plateau encore accessibles.

On voit tout de suite qu’il ne reste plus qu’une seule case de disponible. Elle est entourée en vert dans l’image ci-dessus. Il ne sera donc pas possible d’ajouter 2 reines de plus !

Mais il s’agit d’un algorithme, donc allons jusqu’au bout en poursuivant son execution.

La troisième reine se présente devant la troisième ligne : elle est rejetée de la première case par la première reine, pour la seconde case elle vérifie qu’elle n’est pas en conflit avec la première reine, mais la seconde reine la chasse, ce qui est aussi le cas pour les deux cases suivantes.

Il n’est pas possible de positionner de reine sur la troisième ligne. Notre stratégie n’est donc pas gagnante. Revenons en arrière (backtracking en anglais), sur la position de la deuxième reine.

Sur cette ligne, les deux premières cases étaient en conflit avec la première reine, la troisième mène à une impasse comme nous venons de le voir. Tentons de déplacer la reine sur  la quatrième case.

La seconde reine étant sur la quatrième case, nous obtenons la nouvelle configuration ci dessous avec les cases rendues inaccessibles.

À nouveau nous pouvons mettre en avant les cases qui restent accessibles en les entourant de vert.

Les choses paraissent toujours fort mal engagées car il reste deux cases qui sont sur la même diagonale. Mais laissons sa chance à la troisième reine.

Sur sa ligne, elle tente la première case et se retrouve en conflit avec la première reine. Sur la case suivante, elle est en bonne position avec la première ainsi qu’avec la deuxième.

Si nous regardons depuis le haut :

Aucune case ne sera accessible pour la reine suivante !

La quatrième reine se fait repousser par les trois précédentes et nous n’avons donc pas de solution.

C’est que nous n’avons pas fait les bons choix.

Il nous faut revenir en arrière sur les derniers choix, en commençant par la position de la troisième reine sur la deuxième case. Tentons avec la troisième case. Si tout va bien avec la première reine, elle se retrouve en conflit avec la deuxième reine. Il en est de même si elle se déplace sur la quatrième case. Aucune case n’est possible pour cette reine.

Ce n’est pas mieux.

Nous remontons donc encore en arrière, soit au choix précédent. La deuxième reine n’a plus d’autres cases à tenter.

Il faut donc remonter jusqu’à la première reine. En fait, nous étions partis sur une mauvaise voie dès le départ. Elle se déplace donc sur la seconde case de sa ligne, d’où le chiffre 2 en vert dans la vue ci-dessous. Si on regarde depuis le haut, elle bloque tout de suite l’accès à pas plusieurs cases. Cependant, il y a des cases entourées de vert sur toutes les lignes, voyons donc ce que l’execution de l’algorithme produit.

La reine suivante n’a pas le choix et ne peut s’installer que sur la quatrième case da la deuxième ligne.

Vue d’en haut, il ne reste déjà plus que 3 cases accessibles, mais nous avons toujours des cases accessibles sur chaque ligne.

La reine de la troisième ligne a de la chance. Elle peut s’installer sur la première case de la troisième ligne.

Le damier est maintenant fort contraint, mais l’horizon se dégage…

La dernière reine se fait repousser de la première case par la troisième reine, de la deuxième case par la première reine et et et !!!

La troisième case est la bonne. Les reines ont exactement la place dont elles ont besoin, chacune à sa place, sans être sur le chemin d’aucune autre.

En cadeau, vous pouvez regarder le ballet de la victoire dans son intégralité.

Retour sur la résolution du problème

Cette description de la recherche d’une solution au problème des 4 reines, montre qu’il est possible d’avoir un algorithme relativement simple qui fonctionne par essais et retours en arrière (backtrack). Il s’agit en fait de parcourir les solutions possibles dans un certain ordre. La recherche revient en arrière quand elle met à jour une situation impossible. Il s’agit en fait d’un parcours en profondeur des situations possibles. C’est déjà une bonne solution.

Cet exemple permet de mettre en avant l’importance des propriétés que l’on souhaite atteindre à la fin de l’execution d’un algorithme. Dans ce problème, comment peut-on déterminer si une situation, la position des reines sur le damier, est une solution acceptable ? Simplement si nous avons 8 reines et qu’elles ne sont pas en situation de se prendre. Soient deux propriétés différentes. Chaque propriété conduit à une définir une stratégie algorithmique différente.

On peut se focaliser sur une propriété en particulier, par exemple le fait que les reines ne puissent pas se prendre. Ainsi, à chaque instant, nous nous assurons que cette propriété est vraie. L’objectif pour atteindre une solution est donc de parvenir à avoir 8 reines sur le plateau ! C’est la stratégie que nous venons de suivre avec les danseuses.

Nous avons un cas simple : celui avec 1 seule reine (ou celui sans reine, c’est en effet un autre cas simple). Nous commençons avec ce cas simple et nous cherchons à lui ajouter une reine de plus, de telle sorte que la propriété reste valide, ici que les reines ne puissent pas se prendre. Nous avançons dans la recherche jusqu’à obtenir 8 reines. Pour réaliser cette stratégie, il nous faut avoir un moyen de décrire comment on passe d’une situation à une autre tout en garantissant la propriété (les reines ne se prennent pas).

Essayons d’écrire ces éléments dans l’autre sens.

résoudre le problème pour 8 reines = résoudre le problème pour 7 reines + ajouter correctement une reine

D’accord, il ne nous reste plus qu’à savoir résoudre le problème pour 7 reines ? … Oui

résoudre le problème pour 7 reines = résoudre le problème pour 6 reines + ajouter correctement une reine

résoudre le problème pour 6 reines = résoudre le problème pour 5 reines + ajouter correctement une reine

résoudre le problème pour 5 reines = résoudre le problème pour 4 reines + ajouter correctement une reine

résoudre le problème pour 4 reines = résoudre le problème pour 3 reines + ajouter correctement une reine

résoudre le problème pour 3 reines = résoudre le problème pour 2 reines + ajouter correctement une reine

résoudre le problème pour 2 reines = résoudre le problème pour 1 reine + ajouter correctement une reine

résoudre le problème pour 1 reine !! Nous savons faire, il s’agit du cas simple évoqué au début de cette section !

Ce processus est ce qu’on appelle un algorithme récursif. Pour résoudre le problème, on fait appel à la résolution du problème sur une description du problème plus petite. Ou du moins sur une description du problème qui se rapproche d’un cas que nous savons traiter. L’avantage (non négligeable) de ce type de stratégie, est que nous n’avons pas besoin de rentrer dans le détail de toute la résolution. Il suffit d’écrire que tant qu’on n’a pas un cas simple, on cherche à résoudre un plus petit problème et on lui ajoutera quelque chose.

Nous pouvons écrire cela sous la forme d’un algorithme simple sous forme de pseudo code :

def Reine (n):
        Si (n == 1): 
                retourner la solution pour 1 reine
        Sinon:
                retourner Reine(n-1) + ajouter 1 reine

Les algorithmes récursifs sont le pendant en informatique des raisonnements inductifs en mathématiques ou des preuves par récurrence.

La recherche avec backtracking que nous avons étudiée précédemment fonctionne selon ce principe. Comme il existe plusieurs solutions différentes pour (n-1) reines, il faut trouver la bonne qui permet d’ajouter correctement la reine suivante. Le retour en arrière se fait lorsqu’une mauvaise solution avec moins de reines avait été choisie.

Nous remarquons que nous pouvons poursuivre la recherche sans s’arrêter à la première solution ce qui permet d’identifier toutes les solutions à ce problème, au nombre de 92.

Nous avons insisté sur le fait que ce problème se compose de deux propriétés à respecter : le nombre de reines, et le fait quelles soient bien placées. En conservant le principe de fixer une propriété et en tentant de valider l’autre, nous pouvons fixer le nombre de reines à 8 et chercher à les placer correctement. Cette seconde stratégie est plus efficace. Il s’agit de programmation par contraintes.

Dans ce cas, on place 8 reines sur l’échiquier. On peut fixer comme principe que chaque reine est sur une ligne. Ce que l’on cherche à atteindre c’est de n’avoir  qu’une reine par colonne et une reine par diagonale. À chaque étape la situation compte 8 reines, mais qui peuvent encore être en position de se prendre. L’algorithme compte alors le nombre de conflits et utilise une méthode prédisant comment améliorer la situation en diminuant ce nombre. Une solution pourrait être de déplacer la reine ayant le plus de conflits en la mettant à une place où le nombre de ses conflits diminue.

Cette stratégie est plus difficile à illustrer car elle dépend fortement de la position des reines au départ. Il est aussi plus difficile d’avoir une intuition sur les différentes étapes qui conduisent à une solution. Mais ce qui est incroyable, c’est que c’est une bien meilleure stratégie pour atteindre 1 solution. En effet, tant que le nombre de conflits entre les reines diminue, nous nous rapprochons d’une solution acceptable où ce nombre est égal à zéro. En pratique, cela se fait plus rapidement qu’avec la recherche systématique du backtracking. Par contre, nous ne découvrons qu’une seule solution et non les 92 comme précédemment. Si vous souhaitez en savoir plus sur toutes ces solutions vous pouvez vous référer à cet article.

Ce problème minimaliste permet de mettre en avant que les algorithmes sont fondés sur des propriétés qu’ils cherchent à garantir. Déterminer la manière dont ils y parviennent définit des solutions algorithmiques différentes qui fonctionnent plus ou bien. Tout le travail réside dans la compréhension du problème et la description de ces propriétés. Et si vous êtes à l’aise pour exécuter l’algorithme, maintenant vous pourrez le danser.

Nous remercions le Professeur Kátai Zoltán de l’Université hongroise Sapientia de Transylvanie en Roumanie pour son autorisation de réutilisation de cette vidéo parue sur la chaine Youtube AlgoRythmics.