Problème des huit dames - Définition
La liste des auteurs de cet article est disponible ici.
Le problème des huit dames en informatique
Le problème des huit dames est un bon exemple de problème simple mais non évident. Pour cette raison, il est souvent employé comme support de mise en œuvre de différentes techniques de programmation, y compris d'approches non traditionnelles de la programmation telles que la programmation par contraintes, la programmation logique ou les algorithmes génétiques.
Le plus souvent, il est employé comme exemple d'un problème qui peut être résolu avec un algorithme récursif, en exprimant qu'une solution du problème des n-dames peut être obtenue, par récurrence, à partir d'une solution quelconque du problème des (n-1)-dames par l'adjonction d'une dame. La récurrence commence avec la solution du problème de 0-dame qui repose sur un échiquier vide.
Cette technique est beaucoup plus efficace que l'algorithme naïf de recherche exhaustive, qui parcourt chacun des 648 = 248 = 281 474 976 710 656 placements possibles des huit dames, pour retirer tous ceux pour lesquels plusieurs dames se trouvent sur une même case (laissant seulement
Ce très « mauvais » algorithme produira les mêmes résultats à plusieurs reprises en attribuant différentes places aux huit dames, et recommencera les mêmes calculs plusieurs fois pour différentes parties de chaque solution. Un algorithme légèrement meilleur de recherche exhaustive place une seule dame par rangée, réduisant à seulement 88 = 224 = 16 777 216 placements possibles.
Il est possible de faire beaucoup mieux que cela. Par exemple, le programme de recherche en profondeur ci-dessous examine seulement 15 720 placements possibles des dames en construisant un arbre de recherche et en parcourant les rangées de l'échiquier une par une, éliminant la plupart des positions possibles à un stade très primitif de leur construction.
La programmation par contraintes est bien plus efficace pour ce problème. Un algorithme de « réparation itérative » commence typiquement à partir d'un placement de toutes les dames sur l'échiquier, par exemple avec une seule dame par colonne. Il compte alors le nombre de conflits entre dames, et utilise une méthode heuristique pour déterminer comment améliorer les placements des dames. La méthode heuristique de moindre conflit, qui consiste à déplacer la pièce ayant le plus grand nombre de conflits, dans la même colonne à une place où le nombre de conflits est le plus petit, est particulièrement efficace. Elle résout le problème des millions de dames (sur un échiquier de 1 000 000× 1 000 000 cases) en moins de 50 étapes en moyenne!
L'obtention de cette moyenne de 50 étapes suppose que la configuration initiale soit raisonnablement bonne. Si au début, un million de dames sont placées dans la même rangée, l'algorithme prendra évidemment plus de 50 étapes pour résoudre le problème. Un point de départ « raisonnablement bon » consiste à placer chaque dame dans une colonne telle qu'elle soit en conflit avec le plus petit nombre de dames se trouvant déjà sur l'échiquier.
Remarquez que la méthode de réparation itérative, à la différence de la recherche en profondeur décrite ci-dessus, ne garantit pas une solution. Comme toutes les méthodes de plus profonde descente, elle peut se bloquer sur un extremum local (dans ce cas l'algorithme peut être remis en marche avec une configuration initiale différente.) D'un autre côté, elle peut résoudre des problèmes de grandes tailles qui sont largement au-delà de la portée d'une recherche en profondeur.
