Le problème des huit dames

Recherche en profondeur (backtracking)

Un programme de recherche en profondeur 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, comme on peut le voir sur ces animations :

Références

• Wikipédia : Le problème des huit dames
• Interstices - Le problème des 8 reines, par Maxime Amblard
• Interstices - Le problème des 8 reines… et au-delà, par Jean-Paul Delahaye

Didier Müller, 1.8.21