Le problème des huits dames Le problème des huit dames est un problème de placement sur un échiquier, dans lequel l'objectif est de placer huit dames sur un plateau d'échecs de $64$ cases de manière à ce qu'aucune dame ne puisse attaquer une autre dame. En d'autres termes, aucune dame ne doit partager la même ligne, colonne ou diagonale avec une autre dame.

L'algorithme Python ci-dessous permet de donner la liste de l'ensemble des positionnements solutions du problème. nbSol = 0 def est_valide(chessboard, row, col): """ Vérifie si placer une dame à la position (row, col) sur l'échiquier est valide. """ # Vérifie la colonne for i in range(row): if chessboard[i] == col or \ chessboard[i] - i == col - row or \ chessboard[i] + i == col + row: return False return True def placer_dame(chessboard, row): """ Place une dame sur l'échiquier, une ligne à la fois, en utilisant la récursivité et le backtracking. """ size = len(chessboard) if row == size: # Toutes les dames sont placées avec succès afficher_solution(chessboard) return for col in range(size): if est_valide(chessboard, row, col): # Place la dame et continue avec la ligne suivante chessboard[row] = col placer_dame(chessboard, row + 1) # Backtrack : retirer la dame pour essayer une autre colonne chessboard[row] = -1 def afficher_solution(chessboard): """ Affiche une solution du problème des huit dames. """ global nbSol nbSol = nbSol + 1 print("----------------------------------") print("Solution n° "+str(nbSol)+"\n") for row in range(len(chessboard)): line = "" for col in range(len(chessboard)): if chessboard[row] == col: line += "D " else: line += ". " print(line) print("\n") def resolution_huit_dames(): """ Initialise et lance le processus de résolution du problème des huit dames. """ size = 8 # taille de l'échiquier chessboard = [-1] * size # initialise un tableau pour l'échiquier placer_dame(chessboard, 0) # Lancer la résolution du problème des huit dames resolution_huit_dames()