TD/TP
N°1 : Le problème des n reines
Il s'agit de placer n reines sur un échiquier (n x n) sans qu'elles se menacent. Deux reines ne doivent pas se trouver sur la même ligne, sur la même colonne ou sur la même diagonale. Vous écrirez votre programme en Java.
Si on considère un échiquier 8 x 8, il y a 92 solutions, mais seulement 12 qui ne peuvent pas être obtenues les unes à partir des autres par symétrie ou rotation.
1 R - - - - - - - |
1 R - - - - - - - |
2 - R - - - - - - |
2 - R - - - - - - |
2 - R - - - - - - |
2 - R - - - - - - |
2 - R - - - - - - |
2 - R - - - - - - |
2 - R - - - - - - |
|
3 - - R - - - - - |
3 - - R - - - - - |
La méthode utilisé consiste à écrire un algorithme
récursif capable de retourner en arrière, on parle souvent
de backtracking . Pour cela il faut se souvenir des choix qui
ont été faits précédemment. Les algorithmes
à retour arrière procèdent pas essais/erreurs. Le
schéma général consiste à décomposer
le processus d'essais et erreurs en tâches partielles. Souvent ces
tâches s'expriment naturellement de façon récursives
et consistent en l'exploration d'un nombre fini de sous tâches. On
peut voir tout ce processus comme un processus de recherche qui construit
peu à peu et parcourt en l'élaguant un arbre des sous tâches.
En général, celui-ci croît très vite, souvent
de manière exponentielle, en fonction d'un paramètre donné.
Fréquemment l'arbre de recherche doit être élagué
à l'aide d'heuristique.
Pour écrire l'algorithme, on s'inspirera de ce qui a été
présenté en cours.
L'objectif de ce TP est donc de mettre en œœuvre une technique de recherche
Une méthode naïve consiste à placer une reine sur la
première ligne, puis la deuxième ligne .... la nième
ligne et à choisir une colonne en utilisant le backtracking lorsque
cela n'est plus possible. Votre premier programme
devra tout d'abord trouver une solution et calculer le nombre de retour
en arrière, puis ensuite calculer toutes les solutions et calculer
le nombre total de retour arrière. Vous modifierez ensuite votre
algorithme afin d'utiliser les rotations et les symétries.
On ne cherche plus maintenant toutes les solutions, mais une solution
et à faire croître n.
Lors de la résolution du problème on développe un
arbre et ainsi à chaque nœud il faut déterminer, quelle variable
il faut fixer et quelle valeur il faut lui donner ? On parle d'ordre de
selection. Ces choix peuvent se faire soit de façon statique donc
à l'avance soit de façon dynamique en cours de résolution.
Nous avons utilisé la première démarche, dans le premier
algorithme, en traitant le problème par ordre d'apparition des variables
de la plus petite valeur à la plus grande.
L'ordre de sélection intervient à la fois sur le choix
des variables et sur le choix des valeurs. Ainsi l'ordre de sélection
des variables influence la topologie de l'arbre de recherche et de ce fait
sa taille.
L'ordre de sélection des valeurs quant à lui est souvent
moins important s'il est nécessaire de parcourir tout l'arbre de recherche.
En effet, il n'affecte que l'ordre dans lequel les branches sont explorées
et donc dans lequel les solutions sont trouvées, cependant si on
cherche une seule solution voire la meilleure solution cet ordre prend
toute sont importance.
Deux grands principes régissent l'ordre de sélection
:
Cette approche cherche à déterminer le plus rapidement possible
les sous arbres qui conduisent à aucune solution. On s'occupe donc
de la partie la plus difficile en priorité puisque celle-ci ne le
deviendra pas moins lors de la résolution du problème. Plusieurs
heuristiques peuvent suivre cette démarche :
Si l'heuristique est idéale elle nous donne directement une solution
sans backtracking, c'est malheureusement très rarement le cas. Le
plus souvent les heuristiques s'inspirent de la structure particulière
du problème et on tente de maximiser une estimation des chances
de réussite.
Vous devez appliquer les différentes heuristiques
présentées et déterminer sur quel(s) principe(s) elles
reposent. Vous mesurerez en faisant varier n : le nombre de backtracking
pour obtenir une solution ainsi que le temps CPU consommé. Vous
comparerez ensuite les différentes heuristiques.
Cette première heuristique est celle exposée en cours, qui
consiste à placer une reine par ligne de la première à
la dernière ligne et de choisir la colonne qui laisse le plus grand
nombre de cases libres pour les lignes du dessous.
On place toujours une reine par ligne de la première à la
dernière ligne et on choisit la colonne qui occupe le plus la ligne
suivante. De cette façon on cherche à diminuer au maximum
le degré des nœuds de l'arbre de façon locale et on peut donc
espérer que le nombre total de nœuds dans l'arbre sera plus faible.
Cela nous donne pour 8 reines l'échiquier suivant où les chiffres
en rouge représentent les reines posées. Ainsi la première
colonne de la première ligne laisse 6 colonnes disponibles pour la
deuxième ligne.
6 5 5 5 5 5 5 6
- - - 4 4 3 3 4
2 - 2 - - - - 2
- - 3 - - - 2 -
- - - 1 1 - - -
- - - - - - - 1
- - 1 - - - - -
- - - - 1 - - -
L'énumération s'est faite dans l'ordre naturel des lignes
on peut modifier cet ordre en énumérant les variables des plus
contraintes aux moins contraintes. De ce fait l'ordre sur les lignes se fait
maintenant en fonction de celles ayant le moins de positions libres. Une dernière
amélioration de cette heuristique consiste à placer une reine
obligatoirement dans une colonne lorsqu'elle n'a plus qu'une position de
libre. Vous pourrez également tester que si on combine le critère
de choix sur les lignes et les colonnes (i.e. on s'intéresse aux variables
les plus contraintes à la fois sur les lignes et le colonne) cela
fonctionne mal.
Cette liste n'est pas exhaustive et vous renvoie simplement sur quelques
sites.