Aux échecs, la dame est capable de se déplacer dans toutes les directions.
{width="25%" }
{width="25%" }
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.
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 listes
La disposition valide ci-dessus sera par exemple représentée en machine par :
🐍 Script Python
# colonne 0 1 2 3 4 5 6 7valide=[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).
La liste ci-dessous représente une disposition dans un échiquier de taille \(n=3\) :
🐍 Script Python
# colonne 0 1 2invalide=[1,2,0]
Cette seconde disposition est invalide car deux dames sont sur une même diagonale (aux colonnes d'indices 0 et 1).
Vous devez écrire la fonction disposition_valide qui prend en argument une liste disposition contenant n valeurs et renvoie le booléen répondant à la question « la disposition proposée satisfait-elles le problème des n dames ? ».
On garantit que les valeurs présentes dans la liste disposition sont des numéros de lignes valides (compris entre 0 et n-1 inclus l'un et l'autre).
Aide (1)
Pour vérifier qu'il n'y a qu'une seule dame par ligne, on utilisera un tableau de booléens, initialement tous égaux à False.
On lira ensuite les numéros de lignes fournis dans la disposition : si le tableau contient un False à cet indice, cela signifie que la ligne n'est pas encore occupée. Dans le cas contraire...
Aide (2)
La vérification des diagonales peut se faire astucieusement en jouant sur les indices. En effet, si deux dames sont sur une même diagonale, la de leurs numéros de lignes et celle de leurs numéros de colonnes sont égales.
Par exemple, dans la disposition [2,4,1,6,3,5,7,0], la troisième (indice 2) et la cinquième (indice 4) dames sont sur la même diagonale : 4-2 est égal à abs(3-1).
La valeur absolue permet de plus de vérifier en une seule condition les diagonales haut-droite et les bas-droite.
Exemples
On utilise les échiquiers valide et invalide définis plus haut.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)