Aller au contenu

Problème des huit dames⚓︎

Aux échecs, la dame est capable de se déplacer dans toutes les directions.

Mouvement des dames

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 :

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.

🐍 Script Python
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 :

🐍 Script Python
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 liste echiquier et l'indice d'une ligne i et renvoie la liste correspondant à cette ligne dans l'échiquier,

  • donne_colonne : prend en argument une liste echiquier et l'indice d'une colonne j et renvoie la liste correspondant à cette colonne dans l'échiquier,

  • donne_diagonale_NE : prend en argument une liste echiquier et les coordonnées d'une case (ligne i et colonne j) 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 liste echiquier 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 :

🐍 Console 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 :

Lignes Colonnes

Diagonales NE Diagonale SE

Exemples

On utilise les échiquiers valide et invalide définis plus haut.

🐍 Console Python
>>> 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
###
# 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# Tests supplémentairesbksl-nlvalidepy-und2 = [bksl-nl [0, 0, 0, 0, 1, 0, 0, 0],bksl-nl [0, 1, 0, 0, 0, 0, 0, 0],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, 0, 0, 0, 0, 1, 0, 0],bksl-nl [1, 0, 0, 0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlvalidepy-und3 = [[1]]bksl-nlinvalidepy-und2 = [[1, 0], [1, 1]]bksl-nlbksl-nlfor i, ligne in enumerate(validepy-und2):bksl-nl assert donnepy-undligne(validepy-und2, i) == lignebksl-nlfor j in range(len(validepy-und2)):bksl-nl assert donnepy-undcolonne(validepy-und2, j) == [ligne[j] for ligne in validepy-und2]bksl-nlassert donnepy-unddiagonalepy-undSE(validepy-und2, 0, 0) == [0, 1, 0, 0, 0, 0, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undSO(validepy-und2, 1, 7) == [0, 0, 0, 0, 0, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undNE(validepy-und2, 7, 3) == [0, 0, 0, 0, 0]bksl-nlassert donnepy-unddiagonalepy-undNO(validepy-und2, 7, 7) == [0, 0, 0, 0, 0, 0, 1, 0]bksl-nlassert donnepy-unddiagonalepy-undSE(invalidepy-und2, 0, 0) == [1, 1]bksl-nlassert donnepy-unddiagonalepy-undSO(invalidepy-und2, 1, 0) == [1]bksl-nlassert donnepy-unddiagonalepy-undNE(invalidepy-und2, 0, 1) == [0]bksl-nlassert donnepy-unddiagonalepy-undNO(invalidepy-und2, 0, 0) == [1]bksl-nlassert dispositionpy-undvalide(validepy-und2)bksl-nlassert dispositionpy-undvalide(validepy-und3)bksl-nlassert not dispositionpy-undvalide(invalidepy-und2)bksl-nlbksl-nlinvalidepy-und3 = [[0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 1, 0], [0, 0, 0, 0]]bksl-nlinvalidepy-und4 = [[0, 1, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0]]bksl-nlinvalidepy-und5 = [[0, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]]bksl-nlinvalidepy-und6 = [[0, 0, 1, 0], [0, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0]]bksl-nlbksl-nlassert not dispositionpy-undvalide(invalidepy-und3)bksl-nlassert not dispositionpy-undvalide(invalidepy-und4)bksl-nlassert not dispositionpy-undvalide(invalidepy-und5)bksl-nlassert not dispositionpy-undvalide(invalidepy-und6)bksl-nlbksl-nl 5/5

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-nlNone

A

Z

Retour en haut de la page