Outils pour utilisateurs
Table des matières
⚠ Problème des huit reines
Le but de ce TP est d'écrire un programme qui donnera une façon de placer huit reines sur un échiquier de taille 8x8 de façon à ce qu'aucune reine ne soit en prise avec une autre.
Prérequis
Avoir préparé les algorihtmes en TD ou avoir une partie de la correction à disposition.
Travail à rendre
- Fichier final :
login_reines.py - Fichier PDF contenant les réponses aux quelques questions posées.
Programmation
Structure de données
Afin de ne pas perdre en généralité, nous ferons en sorte que le programme soit très facilement adaptable pour un échiquier de taille quelconque. À cet effet, vous devrez penser à ne pas utiliser de valeurs numériques correspondant à la taille de l'échiquier, mais à utiliser la fonction ''len(…).
Sur un échiquier de taille NxN, pour qu'aucune reine ne soit en prise avec une autre, il faut nécessairement qu'il y ait une reine par ligne. Par conséquent, l'échiquier peut être représenté par une liste de taille N, indiquant dans l'ordre la colonne dans laquelle la reine de chaque ligne est placée. Ce point n'était pas évident.
ech
Dans le cas ci-dessus, la représentation de l'échiquier est donc :
<code>
[0,2,1,4,6,5,3,2]
</code>
==== Programme principal ====
Nous allons à présent écrire le programme principal, puis nous écrirons plus tard les fonctions annexes.
Le programme principal consiste à initialiser la position des reines sur l'échiquier (toutes à gauche), puis, tant qu'il existe une reine en prise avec une reine placée au dessus, à passer à la position suivante en bougeant cette reine d'un cran vers la droite.
Nous avons donc besoin ( est la liste représentant la position des reines sur l'échiquier) :
* d'une fonction : suivant(ech,r) qui passe à la position suivante en bougeant la reine r de l'échiquier ech
* et d'une fonction prise(ech) qui renvoie l'indice (la ligne) de la première reine en prise avec une reine placée au dessus sur l'échiquier ech.
Commencez par écrire la fonction principale (main()) en Python, en supposant les fonctions annexes fonctionnelles. Lorsque vous utilisez une fonction qui n'est pas encore écrire, il est utile de :
- écrire le prototype de la fonction
- écrire sa docstring détaillée au moment où on définit la tâche que devra accomplir la fonction
Pour vous aider voici l'algorithme de la fonction principal :
- ech = toutes les reines en position initiale
- tant qu'il y a des reines en prise :
- r=indice de la première reine en prise (fonction
prise) - déplacer la reine r (fonction
suivant)
Cet algorithme n'est pas tout à fait complet, mais il devrait vous aider.
==== Fonctions auxiliaires====
Nous allons à présent écrire la fonction prise(ech) qui renvoie l'indice de la première reine en prise.
En supposant qu'on dispose d'une fonction enprise(ech,i,j) qui indique en renvoyant respectivement True ou False si les reines des lignes i et j sont ou pas en prise, écrivez le code de la fonction prise(ech).
À présent , ajoutez la fonction enprise(ech,i,j) (normalement, vous avez déjà écrit son prototype et sa docstring n'est-ce pas…) qui teste si les deux reines i et j sont en prise.
Il nous reste à écrire la fonction qui modifie l'échiquier, de façon à passer à la position suivante en déplaçant la reine r : suivant(ech,r). Rappelons (ou pas…) qu'il est pratique d'écrire ici une fonction récursive qui avancera la reine r, testera si elle est sortie de l'échiquier et dans ce cas, la remettre à sa position initiale (première colonne), puis exécutera suivant(ech,r-1).
Écrivez la fonction suivant(ech,r)
===== Tests ===== Vous êtes normalement en mesure de tester le programme.
Testez votre programme avec 8 reines, et corrigez le éventuellement.
Modifiez l'échiquier pour qu'il n'ait plus que 4x4 cases. Votre programme fonctionne-t-il encore ? Si ce n'es pas le cas, corrigez.
Essayez d'obtenir les réponses pour un échiquier 3x3. Que se passe-t-il ?
Pour palier ce problème il faut que nous sachions si oui ou non, toutes les positions ont été explorées. Lorsque la reine de la première ligne est déplacée et sort de l'échiquier, la fonction suivant(ech,r) la remet en première colonne et exécute l'appel suivant(ech,r-1) avec r qui vaut 0 (première ligne de l'échiquier). C'est donc par exemple en décelant les appels à suivant(ech,-1)'' que l'on saura que tout l'échiquier a été exploré.
Réalisez la modification pour éviter le plantage du programme dans le cas d'un échiquier 3x3.
Cette modification va nous permettre, plutôt que d'afficher uniquement le premier résultat trouvé et sortir, d'afficher toutes les solutions possibles. Modifiez votre code dans ce sens.
Combien y a t il de solutions pour un échiquier de taille 4x4, 5x5, 6x6, 8x8 et 10x10 ?
Outils de la page
