Problème des huit dames (2)⚓︎
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-dessous 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é.
Pour satisfaire au problème, une disposition sur un échiquier de taille \(n\) doit compter exactement \(n\) dames.
Sachant qu'il n'y a au maximum qu'une seule dame par colonne, on peut se contenter de coder en machine l'indice de sa ligne. Ainsi, la disposition valide ci-dessus sera 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).
La liste ci-dessous représente une disposition dans un échiquier de taille 3 :
# colonne 0 1 2
invalide = [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 et renvoie le booléen répondant à la question "les dames satisfont-elles le problème des huit dames ?".
Les conditions à vérifier pour satisfaire le problème sont les suivantes :
-
il ne doit y avoir exactement qu'une dame par colonne (cette condition est assurée par la structure de données utilisée),
-
il ne doit y avoir exactement qu'une dame par ligne,
-
il ne doit y avoir exactement qu'une dame par diagonale (les petites et les grandes diagonales, dirigées vers le nord-est ou vers le sud-est).
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 différence 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 nord-est et les sud-est.
Exemples
On utilise les échiquiers valide et invalide définis plus haut.
>>> disposition_valide(valide)
True
>>> disposition_valide(invalide)
False
def dispositionpy-undvalide(disposition):bksl-nl n = len(disposition)bksl-nlbksl-nl # Vérifications des lignesbksl-nl lignespy-undoccupees = [...] py-str ...bksl-nl for ligne in disposition:bksl-nl if ...[...]:bksl-nl return Falsebksl-nl else:bksl-nl ...[...] = ...bksl-nl bksl-nl # Vérification des diagonalesbksl-nl for j1 in range(n - 1):bksl-nl for j2 in range(j + 1, n):bksl-nl if abs(... - ...) == (... - ...):bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nl# Testsbksl-nl# colonne 0 1 2 3 4 5 6 7bksl-nlvalide = [6, 4, 2, 0, 5, 7, 1, 3]bksl-nlbksl-nl# colonne 0 1 2bksl-nlinvalide = [1, 2, 0]bksl-nlinvalidepy-und2 = [2, 4, 1, 5, 3, 6, 0, 7]bksl-nlbksl-nlassert dispositionpy-undvalide(valide)bksl-nlassert not dispositionpy-undvalide(invalide)bksl-nlassert not dispositionpy-undvalide(invalidepy-und2)bksl-nlbksl-nldef dispositionpy-undvalide(disposition):bksl-nl n = len(disposition)bksl-nlbksl-nl # Vérifications des lignesbksl-nl lignespy-undoccupees = [False] py-str nbksl-nl for ligne in disposition:bksl-nl if lignespy-undoccupees[ligne]:bksl-nl return Falsebksl-nl else:bksl-nl lignespy-undoccupees[ligne] = Truebksl-nlbksl-nl # Vérification des diagonalesbksl-nl for j1 in range(n - 1):bksl-nl for j2 in range(j1 + 1, n):bksl-nl if abs(disposition[j2] - disposition[j1]) == (j2 - j1):bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nl# Testsbksl-nl# colonne 0 1 2 3 4 5 6 7bksl-nlvalide = [6, 4, 2, 0, 5, 7, 1, 3]bksl-nlbksl-nl# colonne 0 1 2bksl-nlinvalide = [1, 2, 0]bksl-nlinvalidepy-und2 = [2, 4, 1, 5, 3, 6, 0, 7]bksl-nlbksl-nlassert dispositionpy-undvalide(valide)bksl-nlassert not dispositionpy-undvalide(invalide)bksl-nlassert not dispositionpy-undvalide(invalidepy-und2)bksl-nlbksl-nl
A
Commentaires⚓︎
{{ IDE('exo_corr') }}
La vérification de la présence d'une seule dame par ligne utilise le tableau de booléens décrit dans l'énoncé.
Concernant les diagonales on utilise le test if abs(disposition[j2] - disposition[j1]) == (j2 - j1): où j1 et j2 sont les indices des colonnes étudiées (j2 > j1). Supposons que les dames des colonnes 3 et 7 soient sur la même diagonale orientée vers le nord-est. L'écart j2 - j1 entre les indices des colonnes doit alors être égal à l'écart en valeur absolue* entre les indices des lignes concernés.
Z