Informatica 2 Liceo Scientifico Scienze Applicate/Backtracking: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: corregge errori ortografici comuni |
m Bot: Correggo errori comuni (tramite La lista degli errori comuni V 1.0) |
||
Riga 1:
{{Informatica 2 Liceo Scientifico Scienze Applicate}}
== Il problema delle 8 Regine==
Ilproblema delle otto regine è un problema che consiste nel trovare come posizionare otto regine su una scacchiera 8x8 in modo che nessuna regina possa catturarne un'altra. Quindi se posiziono una regina in una casella (r,c) non posso posizionarne un'altra sulla stessa colonna (c) o stessa riga (r) o sulle due diagonali associate (r+c=k) e (r-c=k)
Il problema rientra nella categoria del backtracking e in questa soluzione usa la ricorsione.<br>
Riga 21:
Naturalmente riesco a posizionare una regina riga r, colonna c, solo se col[c], diagavanti[r+c] e diagindetro[r-c+7] sono tutte libere.
se lo sono, le occupo e lancio la funzione ricorsiva regina(r+1) che si preoccupa di sistemare un'ulteriore regina (sulla riga successiva).
Quando la funzione ricorsiva regina(r+1) termina togliamo la regina riga r colonna c da col[c]
la soluzione (posiziono 8 regine) la registro nel vettore sol, in cui l'indice della cella è il numero della riga dove ho posizionato la regina e il valore della cella con quell'indice rappresenta la colonna dove ho posizionato la regina.
la condizione di terminazione della funzione ricorsiva avviene quando si tenta di posizionare la nona regina regina(8)
== Versione animata della soluzione ricorsiva ==
|