Differenze tra le versioni di "Informatica 2 Liceo Scientifico Scienze Applicate/Backtracking"

m
Bot: corregge errori ortografici comuni
m (Update syntaxhighlight tags - remove use of deprecated <source> tags)
m (Bot: corregge errori ortografici comuni)
 
{{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) , questo perchèperché la regina può mangiare in orizzontale, in verticale e lungo le due diagonali.
Il problema rientra nella categoria del backtracking e in questa soluzione usa la ricorsione.<br>
 
Nella soluzione proposta i vettori (di bool, true=libera,false =occupata da una regina) sono dichiarate come variabili globali, evitando di doverle passare come parametri alla funzione ricorsiva "regina".
 
Per la verità il vettore delle righe non viene dichiarato, perchèperché senza perdità di generalità (non si perdono soluzioni) l'r-sima regina sarà posizionata nella riga r (8 regine 8 righe, una per riga), la funzione regina(r) utilizza solo posizionamenti della regina sulla riga r, quindi la funzione regina(r) andrà ad analizzare il posizionamento della regina r-esima al variare della colonna da 0 a 7.
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] , diagavanti[r+c] e diagonaleindietro[r-c+7] perchèperché sulla stessa riga vogliamo provare a sistemare la regina anche sulle colonne successive.
 
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.
7 783

contributi