Problème des huit dames⚓︎
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é. Selon la taille de l'échiquier, on pourra placer plus ou moins de dames.
Ces échiquiers seront représentés en machine par des listes de listes contenant :
0
si la case correspondante est vide,1
si elle contient une dame.
Exemple
La liste ci-dessous représente la disposition valide donnée plus haut.
valide = [
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0]
]
La liste ci-dessous représente une disposition dans un échiquier de taille 3 :
invalide = [
[0, 0, 1],
[1, 0, 0],
[0, 1, 0]
]
Cette seconde disposition est invalide car deux dames sont sur une même diagonale (cases invalide[1][0]
et invalide[2][1]
).
Vous devez écrire différentes fonctions :
-
donne_ligne
: prend en argument une listeechiquier
et l'indice d'une lignei
et renvoie la liste correspondant à cette ligne dans l'échiquier, -
donne_colonne
: prend en argument une listeechiquier
et l'indice d'une colonnej
et renvoie la liste correspondant à cette colonne dans l'échiquier, -
donne_diagonale_NE
: prend en argument une listeechiquier
et les coordonnées d'une case (lignei
et colonnej
) et renvoie la liste correspondant à la diagonale débutant dans la case indiquée et dirigée vers le haut à droite ↗ (au nord-est, "NE"), -
donne_diagonale_NO
: identique à la précédente mais la diagonale est dirigée vers le haut à gauche ↖ (au nord-ouest, "NO"), -
donne_diagonale_SE
: identique à la précédente mais la diagonale est dirigée vers le bas à droite ↘ (au sud-est, "SE"), -
donne_diagonale_SO
: identique à la précédente mais la diagonale est dirigée vers le bas à gauche ↙ (au sud-ouest, "SO"), -
disposition_valide
: prend en argument une listeechiquier
et renvoie le booléen répondant à la question "les dames satisfont-elles le problème des huit dames ?".
Aide (1)
Une fois les différentes lignes, colonnes et diagonales récupérées, on pourra vérifier qu'elles ne contiennent pas plus d'une dame en utilisant la fonction sum
de Python :
>>> sum([0, 0, 0, 1, 0, 0, 1, 0])
2
On rappelle à ce titre que les dames sont signalées dans la grille par des valeurs 1
et les cases vides par des 0
.
Aide (2)
On pourra (mais ce n'est pas une obligation) effectuer les vérifications illustrées par les figures suivantes :
Exemples
On utilise les échiquiers valide
et invalide
définis plus haut.
>>> donne_ligne(valide, 0)
[0, 0, 0, 1, 0, 0, 0, 0]
>>> donne_colonne(valide, 2)
[0, 0, 1, 0, 0, 0, 0, 0]
>>> donne_diagonale_NE(valide, 4, 0)
[0, 0, 1, 0, 0]
>>> donne_diagonale_NO(valide, 1, 1)
[0, 0]
>>> donne_diagonale_SE(valide, 0, 0)
[0, 0, 1, 0, 0, 0, 0, 0]
>>> donne_diagonale_SO(valide, 3, 7)
[1, 0, 0, 0, 0]
>>> disposition_valide(valide)
True
>>> disposition_valide(invalide)
False
def donnepy-undligne(echiquier, i):bksl-nl ...bksl-nlbksl-nlbksl-nldef donnepy-undcolonne(echiquier, j):bksl-nl ...bksl-nlbksl-nlbksl-nldef donnepy-unddiagonalepy-undNE(echiquier, i, j):bksl-nl ...bksl-nlbksl-nlbksl-nldef donnepy-unddiagonalepy-undNO(echiquier, i, j):bksl-nl ...bksl-nlbksl-nlbksl-nldef donnepy-unddiagonalepy-undSE(echiquier, i, j):bksl-nl ...bksl-nlbksl-nlbksl-nldef donnepy-unddiagonalepy-undSO(echiquier, i, j):bksl-nl ...bksl-nlbksl-nlbksl-nldef dispositionpy-undvalide(echiquier):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlvalide = [bksl-nl [0, 0, 0, 1, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0, 0, 1, 0],bksl-nl [0, 0, 1, 0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0, 0, 0, 1],bksl-nl [0, 1, 0, 0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 1, 0, 0, 0],bksl-nl [1, 0, 0, 0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0, 1, 0, 0],bksl-nl]bksl-nlbksl-nlinvalide = [[0, 0, 1], [1, 0, 0], [0, 1, 0]]bksl-nlbksl-nlassert donnepy-undligne(valide, 0) == [0, 0, 0, 1, 0, 0, 0, 0]bksl-nlassert donnepy-undcolonne(valide, 2) == [0, 0, 1, 0, 0, 0, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undNE(valide, 4, 0) == [0, 0, 1, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undNO(valide, 1, 1) == [0, 0]bksl-nlassert donnepy-unddiagonalepy-undSE(valide, 0, 0) == [0, 0, 1, 0, 0, 0, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undSO(valide, 3, 7) == [1, 0, 0, 0, 0]bksl-nlassert dispositionpy-undvalide(valide)bksl-nlassert not dispositionpy-undvalide(invalide)bksl-nlbksl-nldef donnepy-undligne(echiquier, i):bksl-nl return echiquier[i]bksl-nlbksl-nlbksl-nldef donnepy-undcolonne(echiquier, j):bksl-nl return [ligne[j] for ligne in echiquier]bksl-nlbksl-nlbksl-nldef donnepy-unddiagonalepy-undNE(echiquier, i, j):bksl-nl n = len(echiquier)bksl-nl resultat = []bksl-nl while i >= 0 and j < n:bksl-nl resultat.append(echiquier[i][j])bksl-nl i -= 1bksl-nl j += 1bksl-nl return resultatbksl-nlbksl-nlbksl-nldef donnepy-unddiagonalepy-undNO(echiquier, i, j):bksl-nl resultat = []bksl-nl while i >= 0 and j >= 0:bksl-nl resultat.append(echiquier[i][j])bksl-nl i -= 1bksl-nl j -= 1bksl-nl return resultatbksl-nlbksl-nlbksl-nldef donnepy-unddiagonalepy-undSE(echiquier, i, j):bksl-nl n = len(echiquier)bksl-nl resultat = []bksl-nl while i < n and j < n:bksl-nl resultat.append(echiquier[i][j])bksl-nl i += 1bksl-nl j += 1bksl-nl return resultatbksl-nlbksl-nlbksl-nldef donnepy-unddiagonalepy-undSO(echiquier, i, j):bksl-nl n = len(echiquier)bksl-nl resultat = []bksl-nl while i < n and j >= 0:bksl-nl resultat.append(echiquier[i][j])bksl-nl i += 1bksl-nl j -= 1bksl-nl return resultatbksl-nlbksl-nlbksl-nldef dispositionpy-undvalide(echiquier):bksl-nl n = len(echiquier)bksl-nl # Les lignes et les colonnesbksl-nl for indice in range(n):bksl-nl if sum(donnepy-undligne(echiquier, indice)) > 1:bksl-nl return Falsebksl-nl if sum(donnepy-undcolonne(echiquier, indice)) > 1:bksl-nl return Falsebksl-nlbksl-nl # Les diagonalesbksl-nl for indice in range(n - 1):bksl-nl if sum(donnepy-unddiagonalepy-undNE(echiquier, n - 1, indice)) > 1:bksl-nl return Falsebksl-nl if sum(donnepy-unddiagonalepy-undSE(echiquier, indice, 0)) > 1:bksl-nl return Falsebksl-nl for indice in range(1, n - 1):bksl-nl if sum(donnepy-unddiagonalepy-undNE(echiquier, indice, 0)) > 1:bksl-nl return Falsebksl-nl if sum(donnepy-unddiagonalepy-undSE(echiquier, 0, indice)) > 1:bksl-nl return Falsebksl-nlbksl-nl return Truebksl-nlbksl-nlbksl-nl# Testsbksl-nlvalide = [bksl-nl [0, 0, 0, 1, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0, 0, 1, 0],bksl-nl [0, 0, 1, 0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0, 0, 0, 1],bksl-nl [0, 1, 0, 0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 1, 0, 0, 0],bksl-nl [1, 0, 0, 0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0, 1, 0, 0],bksl-nl]bksl-nlbksl-nlinvalide = [[0, 0, 1], [1, 0, 0], [0, 1, 0]]bksl-nlbksl-nlassert donnepy-undligne(valide, 0) == [0, 0, 0, 1, 0, 0, 0, 0]bksl-nlassert donnepy-undcolonne(valide, 2) == [0, 0, 1, 0, 0, 0, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undNE(valide, 4, 0) == [0, 0, 1, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undNO(valide, 1, 1) == [0, 0]bksl-nlassert donnepy-unddiagonalepy-undSE(valide, 0, 0) == [0, 0, 1, 0, 0, 0, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undSO(valide, 3, 7) == [1, 0, 0, 0, 0]bksl-nlassert dispositionpy-undvalide(valide)bksl-nlassert not dispositionpy-undvalide(invalide)bksl-nlbksl-nl
A
Le problème des huit dames est un classique de la programmation. La vérification que la disposition est valide n'est que la surface du problème : la vraie difficulté est de générer l'ensemble des dispositions valides !
Les quatre fonctions donne_diagonale
permettent de choisir le type de vérifications que l'on souhaite effectuer. On choisit dans le corrigé de tester :
- les diagonales orientées au nord-est débutant sur une case du bord gauche (sauf sur la première ligne car la "diagonale" ne comprend alors qu'une seule case) ou du bord inférieur (sauf sur la dernière colonne pour la même raison),
- les diagonales orientées au sud-est débutant sur une case du bord gauche (sauf sur la dernière ligne) ou du bord supérieur (sauf sur la dernière colonne).
Dans la fonction disposition_valide
, on vérifie successivement que chaque ligne, colonne et diagonale contient au maximum une dame. Si ce n'est pas le cas, on renvoie
immédiatement False
. Si tous les tests sont passés avec succès, la grille est valide : on renvoie True
.
Version fonctionnelle⚓︎
Il est possible d'écrire une version plus fonctionnelle de disposition_valide
en utilisant la fonction all
qui renvoie True
si tous les booléens contenus dans la liste passée en argument sont égaux à True
:
def disposition_valide(echiquier):
n = len(echiquier)
return all(sum(donne_ligne(echiquier, indice)) <= 1 for indice in range(n)) \
and all(sum(donne_colonne(echiquier, indice)) <= 1 for indice in range(n)) \
and all(sum(donne_diagonale_NE(echiquier, n - 1, indice)) <= 1 for indice in range(n - 1)) \
and all(sum(donne_diagonale_SE(echiquier, indice, 0)) <= 1 for indice in range(n - 1)) \
and all(sum(donne_diagonale_NE(echiquier, indice, 0)) <= 1 for indice in range(1, n - 1)) \
and all(sum(donne_diagonale_SE(echiquier, 0, indice)) <= 1 for indice in range(1, n - 1))
Z