Discussion :

[patrick974]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[SpiceGuid]

Le bon point c'est que l'algorithme est correct (en supposant le trouve_place qui va bien).

Le mauvais point c'est que la complexité est en O(n^n) alors que si tu permutais les entiers de 1 à n la complexité serait de O(n!) ce qui serait relativement moins catastrophique