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 :
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