7. TP - NReines

7.1. Introduction

Le problème des N-reines consiste à placer sur un échiquier de $N × N$ cases, $N$ reines, une reine par colonne (ou par rangée) de manière à ce qu'aucune reine ne soit en prise avec une autre.

Ce problème a été posé en 1848 par un joueur d'échecs allemand, Max Bezzel, pour $N = 8$.

n-reines, n-queens
Solution pour N=7

Voici le nombre solutions en fonction de $N$ :

Problème des N_reines, nombre de solutions
N	Solutions
2	0
3	0
4	2
5	10
6	4
7	40
8	92
9	352
10	724
11	2680
12	14200

Exercice 7.1

La complexité de ce problème est de l'ordre de $O(N!)$. Si on raisonne simplement, on a $N$ possibilités de choix pour la première reine, puis $N-1$ (en fait $N-2$) pour la seconde, etc.

7.2. Résolution

Nous allons étudier plusieurs algorithmes de résolution du problème, à savoir :

méthode 1 : utilisation des permutations
méthode 2 :utilisation d'un échiquier et vérification des prises (récursif avec retour arrière)
méthode 3 :utilisation remplissage des cases en prises de l'échiquier (récursif avec retour arrière)
méthode 4 :utilisation de tableaux qui modélise les colonnes et diagonales (récursif avec retour arrière)

7.2.1. Méthode des permutations

Une première méthode issue du livre Python 3, les Fondamentaux du langage, Sébastien Chazallet, Editions ENI (page 428), utilise les permutations et vérifie que deux reines ne sont pas en prise en comparant le nombre d'éléments dans chaque ensemble de diagonales.

La méthode est concise et intéressante d'un point de vue intellectuel mais totalement inefficace car il faut tester chaque permutation, soit $N!$. Pour s'en convaincre, on consultera la section Résultats

n_reines_v1.py

from itertools import permutations
import time
 
nbr_permutations = 0
 
# méthode de résolution
# basée sur les permutations
def resoudre(n):
  global nbr_permutations
  columns = range(n)
  for board in permutations(columns):
    nbr_permutations = nbr_permutations + 1
    s1 = set(board[i] + i for i in columns)
    s2 = set(board[i] - i for i in columns)
    if n == len(set(board[i] + i for i in columns)) == len(set(board[i] - i for i in columns)):
      yield board
      
 
# nombre de reines
N = 6
t1 = time.time()
ns = len(list(resoudre(N)))
t2 = time.time()
print("reines=", N)
print("permutations=", nbr_permutations)
print("solutions=", ns)
print("temps de calcul=", t2-t1)
 
 
 

7.2.2. Méthode des prises sur l'échiquier

Le principe est simple : on modélise l'échiquier sous forme d'une matrice de $N$ par $N$ entiers.

initialiement la matrice est composée de 0
placer une reine sur l'échiquier consiste à assigner à la case correspondante la valeur de la reine (variant de 1 à $N$)
on commence par la reine en ordonnée 1, puis 2, etc
à chaque étape on vérifie qu'il n'y a pas de prise :
- avec une reine située sur une ordonnée inférieure
- avec une diagonale positive supérieure
- avec une diagonale négative supérieure

Attention, en Python, le premier indice d'une liste sera 0 et non pas 1.

Sur la figure précédente, la reine en ligne 5, colonne 2 est en prise avec deux autres reines.

Exercice 7.2

Implantez la résolution en utilisant la méthode par vérification des prises. Créez un fichier appelé nreines_v2.py doté d'une méthode main qui vérifiera si un paramètre donnant la taille de l'échiquier est présent.

On utilisera une matrice échiquier de dimension $N× N$ cases intialisées à 0 ainsi que les méthodes suivantes :

trouve_les_solutions(echiquier, y:int) -> None qui recherche toutes les solutions au problème, on passe en paramètre l'échiquier et le numéro de la ligne ou placer la reine
existe_conflit(echiquier, y, x) -> bool qui vérifie que la reine en position $(y,x)$ sur l'échiquier n'est pas en prise avec une reine située sur un $y' < y$

Concernant trouve_les_solutions(echiquier, y:int), il s'agit d'un sous-programme récursif pour lequel si $y >= N$ on a trouvé une solution. Si $y < N$, il faut tester toutes les possibilités de placement pour $x$ variant de 1 à $N$ (où plutôt variane de 0 à $N-1$).

Pour la fonction existe_conflit(echiquier, y, x) il faut vérifier qu'il n'y a pas de reine sur la colonne où on place la reine (c'est à dire $x$), sur la diagonale gauche ($y' = y -1$ et $x'= x-1$) et sur la diagonale droite ($y' = y -1$ et $x'= x+1$).

7.2.3. Méthode de remplissage des prises de l'échiquier

Dans cette variante, dès qu'on place une reine, on affecte les cases de l'échiquier concernées par une prise de manière à indiquer quelles cases sont inutilisables par la suite pour le positionnement des reines suivantes.

Exercice 7.3

Créez un fichier nreines_v3.py et implantez la résolution en utilisant la méthode par remplissage des prises. Il faudra créer deux méthodes place_reine(echiquier,y,x) et supprime_reine(echiquier,y,x).

7.2.4. Méthode des tableaux colonnes et diagonales

Au lieu d'utiliser un échiquier de $N$ par $N$ cases, on utilise trois tableaux d'entiers :

un tableau de $N+1$ cases qui représente les rangées
un tableau de $2N+1$ cases qui représentent les diagonales droites (positives) occupées
un tableau de $2N+1$ cases qui représentent les diagonales gauches (négatives) occupées

Diagonales positive (orange) et négatives (vert)

Ces tableaux sont initialisés à True . Dés qu'on place une reine $y$ dans la colonne $x$, on positionne à $y$ la rangee et la diagonale correspondante :

rangees$[x]$ à False
droite$[y+x]$ à False
gauche$[N+y-x]$ à False
on peut placer une reine en $(y,x)$ si (range$[x]$ and droite$[y+x]$ and gauche$[N+y-x]$ == True)

Exercice 7.4

Implantez la résolution en utilisant la méthode par tableaux rangées et diagonales (droite et gauche) dans le fichier fichier nreines_v4.py .

7.3. Résultats

Voici un tableau comparatif des temps d'exécution des méthodes pour la résolution du problème des N-reines pour $N=12$ :

Problème des N_reines (N=12), temps d'exécution en secondes
Méthode	Intel Core i7-4790 @ 3.60GHz	AMD Ryzen 1700X @3.40 Ghz
méthode 1 (permutations)	(29m40s) 1780	(33m56s) 2036
méthode 2 (prises échiquier)	33,4	50,1
méthode 3 (remplissage échiquier)	15,3	22,2
méthode 4 (tableaux)	3,7	6,0
méthode 4 (en C++)	0,5	0,6

Vous pouvez comparez ces temps à ceux que vous obtenez sur les machines des salles de TP.

Page de Jean-Michel Richer