solution non récursive au problème des N reines
Bonjour tout le monde,
je cherche a implémenter une solution non récursive du problème des N reines. J'ai donc commencé par essayer d'écrire un alogrithme (en pseudo code). Je voudai être sur que mon algorithme tient la route avant de commencer à coder. Pouriez vous me dire ce que vous en pensez s'il vous plaît. Si je pouvais valider l'algorithme avant de commencer à coder, je suis que je perdrai beaucoup moins de temps.
Je suppose que je dispose d'une structure "Echiquier" qui garde les positions des reines sur l'échiquier.
Je suppose que je dispose d'une structure "Reine" qui enrregistre ses coordonnées sur l'echiquier.
Voici mon algorithme :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
t : tableau de n reines
i : indice de parcours du tableau t
i <- 0
while(true) :
____ // on suppose que la recherche de coordonées commence a partir de la valeur des coordonnées courantes de la reine (les coordonnées etant mises à zéro à l'initialisation d'une reine)
____ found <- Echiquier.trouve_place( t[ i ] )
____ si non( found ) :
____ ____ i <- i-1 // pas de solution trouvée, on revient en arrière
____ ____ Echiquier.supprimer( t[ i ] )
____ si found :
____ ____ si i = n-1 :
____ ____ ____ // solution trouvé : effet de board
____ ____ ____ i <- i-1 // on revient en arrière, pour chercher une autre solution
____ ____ sinon :
____ ____ ____ si i = 0 et t[i].y = n-1 :
____ ____ ____ ____ // toute les solutions ont été trouvées
____ ____ ____ ____ // fin de exété avec succès, sortir de la boucle
____ ____ ____ sinon : // une reine a été placée
____ ____ ____ ____ i <- i+1
// fin de l'algorithme |
Voila, j'espere que ce pseudo code est assez clair. Si vous voulez avoir certaines precisions, demandez moi :)
N'hésiter pas à apporter des critiques.
Merci, au revoir.
