[C] Algoritmo di Backtraking per 8 Regine

[LarsSalazar]

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.

[Skull260287]

E' una guerra vero? Anche io sto combattendo in altra direzione, ma ce la faremo!

[LarsSalazar]

Proprio tu non mi dovevi rispondere smanettone del cavolo :ciauz:
pensa al tu delay di stampa.... io intanto ho tanto di quel materiale per la relazione che non ne hai neanche idea... solo per la mia funzione posso riempire qualcosa come 6 pagine.... senza mettere grafici.

Altri aiuti ? :zizi:

[Skull260287]

Originariamente inviato da LarsSalazar
Proprio tu non mi dovevi rispondere smanettone del cavolo :ciauz:
pensa al tu delay di stampa.... io intanto ho tanto di quel materiale per la relazione che non ne hai neanche idea... solo per la mia funzione posso riempire qualcosa come 6 pagine.... senza mettere grafici.

Altri aiuti ? :zizi:

Delay risolto con la mia testa :) 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.

[alka]

Il forum non è una chat: utilizzate un servizio di messaggistica istantanea per le chiacchiere, o una banale email, che secondo me sono strumenti più appropriati.