TD 3 : Récursivité (suite)




Les méthodes de tous les exercices doivent être écrites dans les classes fournies en annexe (telecharger ces classes) .


Le problème des reines est un classique qui illustre un certain type d'algorithme appelé algorithme à rétro-parcours (backtracking en anglais, qui veut dire revenir sur ses pas). Etant donné un échiquier comprenant n × n cases (n ³ 1), on désire y placer n reines de telle sorte qu'aucune reine ne soit en prises avec d'autres, en suivant les déplacements autorisés dans le jeu d'échecs. On dit alors que les reines sont libres (on rappelle que dans le jeu d'échecs, les reines se déplacent d'un nombre quelconque de cases sur les lignes, les colonnes et les diagonales).


EXERCICE 1

 Donnez deux valeurs de n pour lesquelles il n'y a pas de solution au problème des reines.

L'algorithme qui cherche une solution procède par énumération de toutes les possibilités. On remarque que chaque colonne de l'échiquier doit nécessairement contenir une et une seule reine. En décidant qu'on numérote les lignes, les colonnes et les reines de l'échiquier de 0 à n-1, on peut reformuler le problème de la façon suivante : étant donné un échiquier de taille n (donc de n × n cases), calculer une solution, soit un n-uplet (l0,l1,...,ln-1) tel que pour tout i, 0 £ i £ n-1, la reine i soit en ligne li et en colonne i, de telle façon qu'aucune reine ne soit en prise avec aucune autre. Par exemple, en donnant à la case en haut à gauche de l'échiquier les coordonnées (0,0), les quintuplets (1,4,2,0,3) et (3,1,4,2,0) sont des solutions pour n = 5.

Pour trouver une solution au problème des reines, on commence par placer la reine 0 en ligne 0 et en colonne 0. On cherche ensuite une ligne pour la reine 1 qui est en colonne 1, et ainsi de suite. Lors du placement de la reine k, si aucune ligne ne convient, on revient à la reine k-1 à qui on essaie d'attribuer une nouvelle ligne. On revient en arrière pour modifier un placement déjà effectué, d'où le nom d'algorithme avec retour en arrière (ou backtracking).

EXERCICE 2

 Déduisez des indications précédentes un algorithme récursif informel qui calcule une solution et illustrez son fonctionnement en donnant toutes les solutions pour n = 4. Appliquez cet algorithme aux deux valeurs de n pour lesquelles il n'y a pas de solution et essayez d'en déduire un critère général indiquant l'absence de solution au problème des reines.

A un instant donné du déroulement de l'algorithme précédent, l'échiquier contient k reines et peut être représenté par le k-uplet (l0,l1,...,lk-1) où li est la ligne de la reine i qui se trouve en colonne i. Aux différents états de l'échiquier correspondent des k-uplets que l'on peut comparer entre eux avec un ordre total, l'ordre lexicographique (noté £). Par exemple, on a les relations : (0) £ (0,0) £ (0,2,0) £ (0,3) £ (0,3,0) £ (0,3,0,1) £ (0,3,2) £ (0,4)

EXERCICE 3

 En utilisant les remarques précédentes et en comparant les états successifs de l'échiquier avec l'ordre lexicographique, donnez l'entête, la précondition, la postrelation et le variant de la méthode récursive .

EXERCICE 4

 En utilisant la classe EchiquierDeReines décrite en annexe, écrivez les méthodes uneSolution de la classe Reines, qui calculent récursivement une solution au problème des reines. Vous devez utiliser uniquement les méthodes de la classe publique EchiquierDeReines et aucune des méthodes de la sous-classe privée GestionOccupationEchiquier.

EXERCICE 5

 Donnez la complexité de la méthode uneSolution.

EXERCICE 6

 Inspirez-vous de la méthode uneSolution pour écrire la méthode toutesLesSolutions de la classe Reines, qui calcule toutes les solutions possibles au problème des reines. Quel est la complexité de cette nouvelle méthode ?

EXERCICE 7

 En utilisant les méthodes de la classe privée GestionOccupationEchiquier ainsi qu'une structure de données connue, donnez les attributs et écrivez les méthodes de la classe EchiquierDeReines.

EXERCICE 8

 Trouvez une représentation judicieuse pour les instances de la classe GestionOccupationEchiquier et donnez les attributs et le corps de toutes les méthodes de cette classe.

This document was translated from LATEX by HEVEA.