Problème des huit dames (3)⚓︎
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 \(1 \le n \le 8\) variable.
Pour satisfaire au problème, une disposition sur un échiquier de taille \(n\) doit compter exactement \(n\) dames : une par colonne.
Le but de l'exercice est de déterminer l'ensemble des dispositions valides pour un échiquier de taille \(n\).
On représentera les dispositions des dames à l'aide de listes dont les indices représentent les colonnes de l'échiquier et les valeurs associées l'indice de la ligne sur laquelle est placée la dame de cette colonne.
Exemples
Dans le cas où la taille de l'échiquier est \(n = 5\), [0, 2, 4] est une disposition incomplète (elle compte moins de 5 valeurs). On peut néanmoins lire que l'on a placé une dame dans la colonne 3 (indice 2) et la ligne 5 (valeur 4).
Les dispositions valides seront stockées dans la liste dispositions_valides. Initialement vide, cette liste sera complétée au fil de la recherche.
On fournit une fonction est_valide qui prend en argument une disposition et la taille de l'échiquier et vérifie que cette disposition est valide ou non et renvoie le booléen correspondant.
Exemples
>>> # disposition incomplète, n = 5
>>> est_valide([0, 2, 4], 5)
True
>>> # disposition complète, n = 5
>>> est_valide([2, 0, 4, 1, 3], 5)
False
>>> # disposition complète, n = 4
>>> est_valide([1, 3, 0, 2], 4)
True
Code de la fonction est_valide (pour information)
def est_valide(disposition, n):
# Vérifications des lignes
nb_dames_placees = len(disposition)
lignes_occupees = [False] * n
for ligne in disposition:
if lignes_occupees[ligne]:
return False
else:
lignes_occupees[ligne] = True
# Vérification des diagonales
for j1 in range(nb_dames_placees - 1):
for j2 in range(j1 + 1, nb_dames_placees):
if abs(disposition[j2] - disposition[j1]) == (j2 - j1):
return False
return True
Cette fonction est déjà chargée en mémoire. Il est inutile de la recopier.
La fonction cherche_valides prend en argument une disposition en cours de construction disposition et la taille de l'échiquier n.
Cette fonction fonctionne de la façon suivante :
-
si le nombre de dame placées dans la disposition est égal à la taille de l'échiquier, cela signifie que l'on a déterminé un solution au problème : on la copie dans la liste
dispositions_valides; -
sinon, il reste des dames à placer. On ajoute alors une nouvelle dame dans la disposition sur la première ligne. Si cette disposition est valide on continue l'exploration un appel récursif ;
-
quel que soit le statut de cette nouvelle disposition, valide ou invalide, une fois testée, on retire la dame ajoutée et on en place une nouvelle suivante ;
-
on étudie ainsi toutes les lignes entre 0 et \(n\) (exclu).
La figure ci-dessous illustre une partie de la recherche dans le cas d'un échiquier de taille \(n=4\).
graph TD
R{ } --- A0((0))
R --- A1{1}
R --- A2((2))
R --- A3((3))
A1 --- B0((0))
A1 --- B1((1))
A1 --- B2((2))
A1 --- B3{3}
B3 --- C0{0}
B3 --- C1((1))
B3 --- C2((2))
B3 --- C3((3))
C0 --- D0((0))
C0 --- D1((1))
C0 --- D2{2}
C0 --- D3((3))
style A1 stroke:#0a0,stroke-width:4px
style B3 stroke:#0a0,stroke-width:4px
style C0 stroke:#0a0,stroke-width:4px
style D2 stroke:#0a0,stroke-width:4px
style B0 stroke:#a00,stroke-width:4px
style B1 stroke:#a00,stroke-width:4px
style B2 stroke:#a00,stroke-width:4px
style C1 stroke:#a00,stroke-width:4px
style C2 stroke:#a00,stroke-width:4px
style C3 stroke:#a00,stroke-width:4px
style D0 stroke:#a00,stroke-width:4px
style D1 stroke:#a00,stroke-width:4px
style D3 stroke:#a00,stroke-width:4pxExemples
>>> # Echiquier de dimension n = 3
>>> dispositions_valides = []
>>> cherche_valides([], 3)
>>> dispositions_valides
[]
>>> # Echiquier de dimension n = 4
>>> dispositions_valides = []
>>> cherche_valides([], 4)
>>> dispositions_valides
[[1, 3, 0, 2], [2, 0, 3, 1]]
#--- HDR ---#bksl-nldef estpy-undvalide(disposition, n):bksl-nl # Vérifications des lignesbksl-nl nbpy-unddamespy-undplacees = len(disposition)bksl-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(nbpy-unddamespy-undplacees - 1):bksl-nl for j2 in range(j1 + 1, nbpy-unddamespy-undplacees):bksl-nl if abs(disposition[j2] - disposition[j1]) == (j2 - j1):bksl-nl return Falsebksl-nl return Truebksl-nl#--- HDR ---#bksl-nldef cherchepy-undvalides(disposition, n):bksl-nl nbpy-unddamespy-undplacees = len(...)bksl-nlbksl-nl if nbpy-unddamespy-undplacees == ...: # on a placé toutes les damesbksl-nl ....append(....copy())bksl-nl else: # il reste des dames à placerbksl-nl for ligne in range(...):bksl-nl disposition.append(...)bksl-nl if estpy-undvalide(..., n):bksl-nl cherchepy-undvalides(..., ...)bksl-nl disposition.pop()bksl-nlbksl-nl# Testsbksl-nl# Echiquier de dimension n = 3bksl-nln = 3bksl-nldisposition = [None] py-str nbksl-nldispositionspy-undvalides = []bksl-nlcherchepy-undvalides(0)bksl-nlassert dispositionspy-undvalides == []bksl-nlbksl-nl# Echiquier de dimension n = 4bksl-nln = 4bksl-nldisposition = [None] py-str nbksl-nldispositionspy-undvalides = []bksl-nlcherchepy-undvalides(0)bksl-nlassert sorted(dispositionspy-undvalides) == [[1, 3, 0, 2], [2, 0, 3, 1]]bksl-nlbksl-nldef estpy-undvalide(disposition, n):bksl-nl # Vérifications des lignesbksl-nl nbpy-unddamespy-undplacees = len(disposition)bksl-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(nbpy-unddamespy-undplacees - 1):bksl-nl for j2 in range(j1 + 1, nbpy-unddamespy-undplacees):bksl-nl if abs(disposition[j2] - disposition[j1]) == (j2 - j1):bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nldef cherchepy-undvalides(disposition, n):bksl-nl nbpy-unddamespy-undplacees = len(disposition)bksl-nlbksl-nl if nbpy-unddamespy-undplacees == n: # on a placé toutes les damesbksl-nl dispositionspy-undvalides.append(disposition.copy())bksl-nl else: # il reste des dames à placerbksl-nl for ligne in range(n):bksl-nl disposition.append(ligne)bksl-nl if estpy-undvalide(disposition, n):bksl-nl cherchepy-undvalides(disposition, n)bksl-nl disposition.pop()bksl-nlbksl-nlbksl-nl# Testsbksl-nl# Echiquier de dimension n = 3bksl-nldispositionspy-undvalides = []bksl-nlcherchepy-undvalides([], 3)bksl-nlassert dispositionspy-undvalides == []bksl-nlbksl-nl# Echiquier de dimension n = 4bksl-nldispositionspy-undvalides = []bksl-nlcherchepy-undvalides([], 4)bksl-nlassert sorted(dispositionspy-undvalides) == [[1, 3, 0, 2], [2, 0, 3, 1]]bksl-nlbksl-nl
A
Commentaires⚓︎
{{ IDE('exo_corr') }}
On explore les différentes possibilités avant de revenir en arrière dès que l'on observe que la disposition est invalide. Cette façon de faire classique est appelée backtracking.
Z