Aller au contenu

Le problème des reines

Description

Comment placer \(N\) reines sur un échiquier \(N \times N\) sans qu'aucune ne puisse en menacer une autre ?

Illustration de Samuel Velasco pour Quanta Magazine.

Une reine menace toutes les cases de sa ligne, de sa colonne et de ses deux diagonales. Deux reines ne doivent donc partager ni ligne, ni colonne, ni diagonale.

Pour \(N = 8\), il existe 92 solutions. Pour \(N = 2\) et \(N = 3\), il n'en existe aucune.

Ce problème se résout exactement comme le sudoku vu en cours : on fait un choix, on poursuit la résolution avec ce choix, on annule le choix. C'est du backtracking (retour sur trace).

Rendu attendu

  • Un compte rendu qui reprend les questions une par une, dans l'ordre, avec pour chacune la réponse (explication, pseudocode, tableau de mesures ou extrait de code selon la question).

  • Un fichier .py contenant l'ensemble du code dans sa version finale : afficher, est_compatible et placer. Le code doit s'exécuter sans erreur et chaque fonction doit être commentée.

Représentation d'une solution

Puisque deux reines ne peuvent pas être sur la même ligne, une solution contient exactement une reine par ligne. On va donc construire la solution ligne après ligne : pour la ligne \(0\), on choisit la colonne où placer la reine ; puis pour la ligne \(1\), on choisit sa colonne ; et ainsi de suite jusqu'à la ligne \(N - 1\).

  1. Avec cette façon de procéder, quelles sont les contraintes qu'il reste à vérifier à chaque choix ?

On représente une solution (partielle ou complète) par une liste reines de longueur \(N\), où reines[i] est la colonne de la reine de la ligne i, et -1 si la ligne n'est pas encore remplie.

  1. Soit la solution suivante pour \(N = 4\). Donner la liste reines qui représente cette solution avec la représentation décrite ci-dessus.

    . R . .
. . . R
R . . .
. . R .

  2. Écrire la fonction afficher(reines) qui affiche l'échiquier avec R pour une reine et . pour une case vide, comme ci-dessus.

Résolution par backtracking

  1. Écrire la fonction est_compatible(reines, ligne, colonne) qui renvoie True si on peut placer une reine en (ligne, colonne) sans qu'elle soit menacée par les reines déjà placées dans les lignes 0 à ligne - 1.

    Indice

    Les cases (i, j) et (k, l) sont en diagonale si abs(i - k) == abs(j - l).

  2. Écrire le pseudocode de la fonction placer(reines, ligne) sur le modèle de remplir(grille) vu en cours. Identifier clairement :

    • le ou les cas de base ;
    • le cas récursif ;
    • l'endroit où l'on fait un choix et celui où l'on annule le choix.

  3. Traduire ce pseudocode en Python. La fonction doit simplement afficher chaque solution trouvée.

    def placer(reines, ligne):
    # à compléter

    Ça marche ?

    Vérifier le programme sur \(N = 4\) (2 solutions), puis sur \(N = 8\) (92 solutions).

  4. Modifier la fonction pour qu'elle renvoie le nombre de solutions au lieu de les afficher.

Expérimentation

  1. Ajouter une variable globale pour compter le nombre d'appels à placer, remise à zéro avant chaque résolution.

  2. Compléter le tableau suivant en mesurant le temps d'exécution avec time.perf_counter() :

    Nombre de reines Nombre de solutions Nombre d'appels à placer Temps (s)
    4
    5
    6
    7
    8
    9
    10
    11
    12

  3. Tracer deux graphiques en fonction de \(N\) : le nombre d'appels à placer, et le temps d'exécution. Quelle est l'allure de ces courbes ? Que devient cette allure avec une échelle logarithmique sur l'axe vertical ?

  4. Ajouter sur le graphique du nombre d'appels les courbes de \(N^N\) et de \(N!\). Que constate-t-on, et comment l'expliquer ?

  5. Quel est le nombre maximal d'appels à placer en cours en même temps ?