7. TP - NReines

7.1. Introduction

Solution pour N=7

Voici le nombre solutions en fonction de $N$ :

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.

On génère toutes les permutations possibles et on compte le nombre de diagonales positives et négatives :

• les diagonales positives correspondent à : $y + x$
• les diagonales négatives correspondent à : $y - x$

Par exemple, pour $N=4$, on trouvera une solution si $\text"diag_pos"$ et $\text"diag_neg"$ sont de taille $4$, cela signifie qu'il n'y a aucune reine en prise sur les diagonales :

ys=(0, 1, 2, 3)
xs=(1, 3, 0, 2)
diag_pos = {1, 4, 2, 5}   # aussi appelée diagonale droite
diag_neg = {-2, 1, -1, 2} # aussi appelée diagonale gauche

Exemples de solution et non solution pour N=4

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

• initialement la matrice est composée de 0
• placer une reine sur l'échiquier consiste à assigner à la case correspondante la valeur de la reine (variant entre 1 et $N×N$)
• on commence par la reine en ordonnée 1 (en fait ligne 0 en Python), puis 2 (ligne 1 en Python), 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.

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.

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 positives (orange) et négatives (vert) en fonction des indices qui commencent à 1 ou à 0 pour $x$ et $y$.

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)

7.3. Résultats

Voici quelques résultats sur AMD Ryzen 5 5600G. Vous pouvez comparez ces temps à ceux que vous obtenez sur les machines des salles de TP.

On a donc 5 implantations :

• 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 : remplissage des cases en prises de l'échiquier (récursif avec retour arrière)
• méthode 4 : utilisation de tableaux qui modélisent les colonnes et diagonales (récursif avec retour arrière)
• méthode 5 : implantation en C++ de la méthode 4

On constate que concernant l'implantation en Python, la méthode 4 est la plus rapide. Cependant, cette même méthode, implantée en C++ (méthode 5) est encore bien plus rapide.