Le problème des n reines

Publié le 12/02/17

Le problème des huit reines est bien connu.

1. Généralisation au cas de n reines

On se propose ici de programmer avec Python (et de visualiser avec le package turtle) la recherche de(s) solutions au « problème des n reines » (placer n reines sur un échiquier n\times n de telle sorte qu’aucune d’elle ne soit en prise avec une autre.

La première chose est de réfléchir à la structure de données qui nous permettra de modéliser les positions actuelles des reines déjà placées sur l’échiquier.

On convient de numéroter les reines (et les colonnes de l’échiquier) de 0 à n-1.
On placera la reine n°j dans la colonne n°j, avec 0\le j\le n-1.

Soit Q la liste de longueur n des numéros de ligne des reines. Dire que Q[j]=i, c’est dire que la reine n°j est placée sur la case n°i de la colonne n°j.
On conviendra que valeur Q[j]=-1 signifie que la reine n°j n’est pas encore posée sur l’échiquier.

2. Présentation de l’algorithme

L’idée générale de l’algorithme est la suivante:

  • On commence par placer la reine de la colonne 0, puis celle de la colonne 1, etc.
  • Dans la colonne n°j, on place la reine n°j sur la ligne 0, puis la ligne 1, etc.
  • Quand on place la reine n°j en ligne i (ce qui revient à poser Q[j]=i) il convient de vérifier si elle n’est pas « en prise » avec l’une des reines déjà placées sur l’échiquier.

La fonction suivante répond False si la reine n°j (actuellement placée dans la ligne Q[j] de la colonne j) est en prise avec l’une des reines des colonnes précédentes.

C’est la fonction place qui est chargée d’effectuer la pose d’une reine. Et lorsque la reine posée en colonne j n’est pas en prise avec les précédentes, alors on passe (récursivement) à la reine suivante.

On tient une solution quand on est amené à vouloir placer la reine n°n (qui n’existe pas!). Dans ce cas on ajoute la liste Q (qui contient la description de la solution) à la liste sols.

La fonction suivante produit un affichage sommaire d’une solution.

Par exemple:

2. La fonction principale

Voici maintenant la fonction principale.
Son seul argument est la taille de l’échiquier (par défaut 8).

Voici quelques-unes des 92 solutions lorsque n=8:

3. Programmation avec le module turtle de Python

On peut améliorer l’aspect visuel du programme en utilisant le module turtle de Python.

On trouvera à cette adresse une archive contenant le programme qui m’a permis d’obtenir les images suivantes. Ce programme est vraiment une création personnelle, donc c’est améliorable, mais je n’ai pas trop le temps, etc. etc. et comme dit Donald Knuth:

Premature optimization is the root of all evil

Voici la 75ème solution du problème des huit reines :
reines8x8-075

Voici une animation des 92 solutions du problème des huit reines :
leshuitreines

Voici la première solution du problème des 12 reines :
les12reines

Et voici la première solution du problème des 23 reines (j’ai changé l’affichage!) :
les23reines