CentraleSupélec LMF, UMR CNRS 9021
Département informatique Laboratoire Méthodes Formelles
Bât Breguet, 3 rue Joliot-Curie Bât 650 Ada Lovelace, Université Paris Sud
91190 Gif-sur-Yvette, France Rue Noetzlin, 91190 Gif-sur-Yvette, France
HuitReines

Résolution du problème des 8 reines par essais successifs

Le problème des 8 reines consiste à placer 8 reines sur un échiquier sans qu'aucune d'elles ne soit en position de prise. Une reine peut prendre toute pièce qui se trouve sur la même ligne, la même colonne ou la même diagonale qu'elle.

Principe général

Le principe de la résolution d'un problème par un algorithme à essais successifs est, partant d'une situation initiale (ici, l'échiquier vide) :

  • si la situation est une solution du problème, la rendre ;
  • sinon :
1. déterminer les actions possibles (ici, une action consiste à poser une reine sur l'échiquier sans qu'elle soit en situation de prise) ;
2. effectuer une des actions possibles (poser une reine sur une des cases possibles) et l'éliminer de la liste des actions possibles ;
3. appliquer de nouveau l'algorithme en partant de la situation obtenue ;
4. annuler l'action effectuée en 2 (retour arrière, ou backtrack) ;
5. retourner en 2 tant que la liste d'actions possibles n'est pas vide.

Ceci permet de trouver toutes les solutions du problème. Si on souhaite simplement trouver une solution, il suffit de s'arrêter dès que l'étape 3 trouve une solution.

Afin d'accélerer l'algorithme, l'étape 1 doit prendre en compte le plus petit nombre d'actions possibles qui permet de trouver une ou les solutions. Pour le problème des 8 reines, on sait que chaque reine sera seule sur une ligne de l'échiquier, et donc que toute solution aura une unique reine par ligne. Ainsi, au lieu d'envisager 64 cases pour poser la première reine, on pourra se contenter de n'envisager que les 8 cases de la première ligne, puisqu'une solution aura forcément une reine sur la première ligne. De même, on n'envisagera que les cases de la deuxième ligne pour la deuxième reine etc.

Optimisations

Parmi les 92 solutions que l'on trouve ainsi, certaines sont identiques à une rotation de l'échiquier près, d'autres sont identiques à une symétrie près. Si on ne s'intéresse qu'à la disposition relative des reines sur l'échiquier, on ne gardera qu'un exemplaire de ces solutions « équivalentes ».

Lancement

Vous avez le choix de faire fonctionner l'algorithme de placement des huit reines :

  • dans votre navigateur sous forme d'applet ;
  • sur votre ordinateur, en utilisant toujours la version la plus à jour grâce à Java Web Start ;
  • sur votre ordinateur, en utilisant une archive Java que vous lancerez en double-cliquant son icône ou grâce à la commande : java -jar HuitReines.jar