Salve, il problema che mi si e' posto difronte e' quello di implementare un algoritmo per il posizionamento di N regine su una scacchiera NxN evitando che esse si tengano sotto scacco.
Ho approntato uno pseudocodice, ma c'e' qualcosa che non mi torno... so che il problema non e' dei piu' semplici e ringrazio tutti quelli che mi vorranno dare una mano.
Size = Numero di regine
Riga = Indice di riga
Col = Indice di colonna
N.B. La funzione sara' ricorsiva quindi bisogna tenere ben presente come si utlizza lo stack in questi casi.
Int IdxColV; //Indice di colonna della regina precendente.
if (Riga < Size)
.{
...if ( Col < Size )
....if ( Valido ) //Controlla se la regina posizionata in quella cella e' sotto scacco oppure no
.....{
.......Mark //Funzione che setta a +1 tutte le celle guardate dalla regina posizionata
.......Richiamo su Riga+1 e IdxColV = Col
.....}
....else
......Richiamo sulla stessa riga incrementando Col di 1
...else
....{
......UnMark //Decrementa di 1 le celle guardate dalla regina in posizione IdxColV
......Richiamo su stessa Riga ma con Col+1
....}
...Non ci sono soluzioni
..}
else
.Ho trovato una soluzione.
Il dubbio che mi sorge e' il seguente:
con una strutturazione del genere le soluzione create saranno tutte?
Ecco alcuni risultati di cio' che si deve ottenere:
Num Regine = 1 Soluzioni = 1
Num Regine = 2 Soluzioni = 0
Num Regine = 3 Soluzioni = 0
Num Regine = 4 Soluzioni = 2
Num Regine = 5 Soluzioni = 10
Num Regine = 6 Soluzioni = 4
Num Regine = 7 Soluzioni = 40
Num Regine = 8 Soluzioni = 92
Num Regine = 9 Soluzioni = 352
e così via dicendo. Il problema ha soluzioni che crescono di numero in modo esponenziale.
Grazie a tutti.
Ora sono alle prese con altri problemi di standard con linux, sto facendo dei test di stabilità e compilazione....Sorry per l'Off Topic tra amici.
