Informatica 2 Liceo Scientifico Scienze Applicate/Backtracking: differenze tra le versioni

== 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è la regina può mangiare in orizzontale, in verticale e lungo le due diagonali.

 

Se provate a risolvere il problema probabilmente usate come struttura dati per rappresentare la schacchiera una matrice 8*8, ma c'e' una soluzione più efficiente che impiega 4 vettori:

la condizione di terminazione della funzione ricorsiva avviene quando si tenta di posizionare la nona regina regina(8) , infatti la numerazione delle regine parte da 0 a 7. In questo caso prima di terminare stampa la soluzione trovata (i posizionamenti delle regine da 0 a 7)

 

 

<source lang=php>

 

 

 

[[Categoria:Informatica 2 Liceo Scientifico Scienze Applicate|Backtracking]]