Problème des huit dames (3)
Aux échecs, la dame est capable de se déplacer dans toutes les directions.
Le problème des huit dames consiste à placer \(8\) dames sur un échiquier classique (\(8\) lignes et \(8\) colonnes) de façon à ce qu'aucune d'entre elles ne soit menacée par une autre. Ainsi il n'y a qu'une seule dame par ligne, colonne ou diagonale. La figure ci-dessus (à droite) illustre une disposition valide.
On considère dans cet exercice des « échiquiers » de taille \(n \ge 1\) variable. On garantit que l'échiquier est bien carré. Selon la taille de l'échiquier, on pourra placer plus ou moins de dames.
Le problème considéré dans cet exercice consiste donc à placer exactement \(n\) dames dans un échiquier de \(n \times n\) cases de façon à ce qu'aucune d'entre elles ne soit menacée par une autre.
Le but de l'exercice est de déterminer le nombre de dispositions valides pour un échiquier de taille \(n\).
Puisqu'une disposition des dames valides doit comporter exactement une dame par colonne on peut se contenter, pour chaque colonne, de ne garder trace que de la ligne sur laquelle se trouve l'unique dame de cette colonne.
Cette représentation du problème prend la forme d'une liste de n éléments dans laquelle l'élément d'indice j est égal à l'indice i de la ligne sur laquelle se trouve la dame.
Exemples de liste
La disposition valide ci-dessus sera par exemple représentée en machine par :
# colonne 0 1 2 3 4 5 6 7
valide = [6, 4, 2, 0, 5, 7, 1, 3]
On peut lire que la dame de la première colonne (indice 0) est située sur la \(7\)-ème ligne (indice 6).
On fournit une fonction est_coherente qui prend en paramètres la taille d'un échiquier ainsi qu'une une disposition et vérifie que cette disposition incomplète satisfait, à ce stade, le problème des huit dames. La fonction renvoie le booléen correspondant.
Cette fonction est déjà importée dans l'éditeur, vous pouvez l'utiliser directement.
Utilisation de la fonction est_coherente
>>> est_coherente(5, [0]) # une seule dame → cohérent
True
>>> est_coherente(5, [0, 0]) # deux dames sur la même ligne → incohérent
False
>>> est_coherente(5, [2, 0, 3, 1])
True
Code de la fonction est_coherente
Pour information, on fournit le code de la fonction est_coherente :
def est_coherente(n ,disposition):
# Vérifications des lignes
nb_dames_placees = len(disposition)
lignes_occupees = [False] * n
for ligne in disposition:
if lignes_occupees[ligne]:
return False
else:
lignes_occupees[ligne] = True
# Vérification des diagonales
for j_1 in range(nb_dames_placees - 1):
for j_2 in range(j_1 + 1, nb_dames_placees):
if abs(disposition[j_2] - disposition[j_1]) == (j_2 - j_1):
return False
return True
La fonction récursive compte_valides prend en paramètre la taille de l'échiquier n ainsi qu'une disposition en cours de construction disposition et renvoie le nombre de dispositions valides solutions au problème de taille \(n\) construites sur la base de celle passée en argument.
Cette fonction fonctionne de la façon suivante :
-
si la taille de la disposition est égale à la taille de l'échiquier, cela signifie que l'on a déterminé une solution au problème ;
-
sinon, il reste des dames à placer . On doit compter les dispositions valides que lon peut construire à parti de la disposition actuelle :
-
pour ce faire on ajoute une nouvelle dame dans la disposition sur la première ligne ;
-
si cette disposition est valide on continue l'exploration avec un appel récursif ;
- quel que soit le statut de cette nouvelle disposition, valide ou invalide, une fois testée, on retire la dame ajoutée et on en place une nouvelle suivante ;
- on étudie ainsi toutes les lignes entre
0etn(exclu).
-
La figure ci-dessous illustre une partie de la recherche dans le cas d'un échiquier de taille \(n=4\).
graph TD
R{ } --- A0((0))
R --- A1{1}
R -.- A2((2))
R -.- A3((3))
A1 --- B0((0))
A1 --- B1((1))
A1 --- B2((2))
A1 --- B3{3}
B3 --- C0{0}
B3 -.- C1((1))
B3 -.- C2((2))
B3 -.- C3((3))
C0 --- D0((0))
C0 --- D1((1))
C0 --- D2{2}
C0 -.- D3((3))
style A0 stroke:#a00,stroke-width:4px
style A1 stroke:#0a0,stroke-width:4px
style B0 stroke:#a00,stroke-width:4px
style B3 stroke:#0a0,stroke-width:4px
style C0 stroke:#0a0,stroke-width:4px
style D2 stroke:#0a0,stroke-width:4px
style B0 stroke:#a00,stroke-width:4px
style B1 stroke:#a00,stroke-width:4px
style B2 stroke:#a00,stroke-width:4px
style D0 stroke:#a00,stroke-width:4px
style D1 stroke:#a00,stroke-width:4px
style A2 stroke-dasharray: 5 5
style A3 stroke-dasharray: 5 5
style C1 stroke-dasharray: 5 5
style C2 stroke-dasharray: 5 5
style C3 stroke-dasharray: 5 5
style D3 stroke-dasharray: 5 5Exemples
>>> # Echiquier de dimension n = 3 -> aucune disposition valide
>>> compte_valides(3)
0
>>> # Echiquier de dimension n = 4 -> deux dispositions valides
>>> compte_valides(4)
2
Liste vide par défaut
Lors du premier appel de la fonction compte_valides, on n'a placé aucune dame et la disposition à passer en argument est donc vide.
Plutôt que d'utiliser la valeur par défaut [], on préfère utiliser None et faire :
def compte_valides(n, disposition=None):
if disposition is None:
disposition = []
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)