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

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