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

Jump to navigation Jump to search
nessun oggetto della modifica
(Nuova pagina: {{Informatica 2 Liceo Scientifico Scienze Applicate}} == Il problema delle 8 Regine== Ilproblema delle otto regine è un problema che consiste nel trovare come posizionare otto regi...)
 
== 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.
Il problema rientra nella categoria del backtracking e in questa soluzione usa la ricorsione.<br>
 
[[File:Https://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Chessboard480.svg/312px-Chessboard480.svg.png|riquadrato|8 regine]]
<br>
 
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)
 
== Versione animata della soluzione ricorsiva ==
[[File:Eight-queens-animation.gif]]
 
Questa animazione usa il [[backtracking]] per risolvere il problema. Una regina è posizionata in una colonna che non genera conflitto. Se la colonna non viene trovata il programma ritorna all'ultimo stato positivo e viene provata una differente colonna.
 
== Programma in C soluzione ricorsiva ==
 
<source lang=php>
 
 
{{Avanzamento|30100%|4 marzo 2020}}
 
[[Categoria:Informatica 2 Liceo Scientifico Scienze Applicate|Backtracking]]
Utente anonimo

Menu di navigazione