Une Approche Aveugle Sans Récursivité et Économique en Espace pour Trouver Toutes les Solutions Possibles au Problème des N-Dames

Le problème des N-dames consiste à placer N dames d’échecs sur un échiquier de taille N×N de telle manière qu’aucune d’entre elles ne puisse attaquer une autre. Une dame aux échecs peut se déplacer horizontalement, verticalement et en diagonale. Ainsi, les voisines d’une dame doivent être placées de façon à éviter tout conflit dans ces trois directions. Les scientifiques reconnaissent que le facteur de branchement augmente de manière presque linéaire. Grâce à des algorithmes d’intelligence artificielle basés sur des stratégies de recherche telles que la recherche en largeur d’abord (BFS), la recherche en profondeur d’abord (DFS) et les algorithmes de retour arrière (backtracking), de nombreux chercheurs ont étudié ce problème et développé diverses méthodes pour déterminer les solutions possibles. Les approches aveugles, c’est-à-dire les recherches non informées telles que la BFS et la DFS, utilisent la récursivité. De même, l’algorithme de retour arrière repose sur la récursivité pour résoudre ce problème. Toutefois, tous ces algorithmes récursifs utilisent une pile système dont la capacité est limitée. Ainsi, pour de petites valeurs de N, la mémoire système est rapidement épuisée, bien que cela dépende de la machine utilisée. Ce papier traite du problème susmentionné et propose une approche fondée sur une recherche DFS non récursive afin de réduire la consommation de mémoire système. Dans ce travail, la recherche en profondeur d’abord (DFS) est utilisée comme méthode aveugle ou recherche non informée. Cette étude expérimentale a permis d’obtenir des résultats significatifs en termes de temps d’exécution et d’utilisation mémoire.