Parallélisation du problème des N-reines
Le but du problème des N reines (mieux connu sous le nom de « problème des huit dames » en français) est de placer huit reines d’un jeu d’échecs sur un échiquier de N x N cases de telle sorte que les dames ne puissent se menacer en un coup, selon les règles traditionnelles du jeu d’échecs (en ignorant la couleur des pièces).
Pour la résolution du problème avec 8 reines, il est assez simple de trouver les solutions avec un algorithme séquentiel. Cela ne prend que quelques secondes. C’est pourquoi nous avons décidé de généraliser le problème à un nombre quelconque de reines sur un échiquier de taille plus grande, mais toujours de même taille que le nombre de reines. S’il est trivial pour un processeur de trouver toutes les solutions avec 8 reines, il en est moindre avec 16 reines, par exemple. C’est ici que la parallélisation de l’algorithme entre en jeu pour accélérer le traitement du calcul.
Pour la conception de la version parallèle des n reines nous avons utilisés les threads POSIX sur le serveur Solaris.