# Informatica 2 Liceo Scientifico Scienze Applicate/Backtracking

Informatica 2 Liceo Scientifico Scienze Applicate
Copertina Tutti i moduli · Sviluppo
* Linguaggi di programmazioneInformatica 2 Liceo Scientifico Scienze Applicate/Linguaggi di programmazione
* Compilare un programmaInformatica 2 Liceo Scientifico Scienze Applicate/Compilare un programma
* CiaoMondoInformatica 2 Liceo Scientifico Scienze Applicate/CiaoMondo
* AreaRettangoloInformatica 2 Liceo Scientifico Scienze Applicate/AreaRettangolo
* AreaTrapezioInformatica 2 Liceo Scientifico Scienze Applicate/AreaTrapezio
** Compito1Informatica 2 Liceo Scientifico Scienze Applicate/Compito1
* Programmazione ImperativaInformatica 2 Liceo Scientifico Scienze Applicate/Programmazione Imperativa
* Diagrammi di FlussoInformatica 2 Liceo Scientifico Scienze Applicate/Diagrammi di Flusso
* Operatori AritmeticiInformatica 2 Liceo Scientifico Scienze Applicate/Operatori Aritmetici
* Istruzione ifInformatica 2 Liceo Scientifico Scienze Applicate/Istruzione if
** Esercizio Equazione 2^ gradoInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Equazione 2^ grado
** Esercizio Calcola lo ScontoInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Calcola lo Sconto
** Esercizio Calcola lo Sconto2Informatica 2 Liceo Scientifico Scienze Applicate/Esercizio Calcola lo Sconto2
* Operatori LogiciInformatica 2 Liceo Scientifico Scienze Applicate/Operatori Logici
** Esercizio x interno all'intervalloInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio x interno all'intervallo
** Esercizio x esterno all'intervalloInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio x esterno all'intervallo
* Istruzione switchInformatica 2 Liceo Scientifico Scienze Applicate/Istruzione switch
** Esercizio Scelta EquazioneInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Scelta Equazione
* Altre Istruzioni di Scelta o DiramazioneInformatica 2 Liceo Scientifico Scienze Applicate/Altre Istruzioni di Scelta o Diramazione
* Istruzioni di RipetizioneInformatica 2 Liceo Scientifico Scienze Applicate/Istruzioni di Ripetizione
** Es (do-while) Indovina il numeroInformatica 2 Liceo Scientifico Scienze Applicate/Es (do-while) Indovina il numero
** Es (while) La nonna è stancaInformatica 2 Liceo Scientifico Scienze Applicate/Es (while) La nonna è stanca
** Es (for) Somma di 5 numeriInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Somma di 5 numeri
** Es (for) Analisi sequenza datiInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Analisi sequenza dati
** Es (for) Sequenze NumericheInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Sequenze Numeriche
** Es (for) SupermarketInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Supermarket
** Es (while) Bisca ClandestinaInformatica 2 Liceo Scientifico Scienze Applicate/Es (while) Bisca Clandestina
* Compito2Informatica 2 Liceo Scientifico Scienze Applicate/Compito2
* I vettoriInformatica 2 Liceo Scientifico Scienze Applicate/I vettori
** Es Usiamo i vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es Usiamo i vettori
** Es2 Usiamo i vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es2 Usiamo i vettori
** Es3 Supermarket con vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es3 Supermarket con vettori
** Compito dic 2019Informatica 2 Liceo Scientifico Scienze Applicate/Compito dic 2019
** BubbleSortInformatica 2 Liceo Scientifico Scienze Applicate/BubbleSort
** Ricerca DicotomicaInformatica 2 Liceo Scientifico Scienze Applicate/Ricerca Dicotomica
* Matrici e ArrayInformatica 2 Liceo Scientifico Scienze Applicate/Matrici e Array
** Es matrici battaglia navaleInformatica 2 Liceo Scientifico Scienze Applicate/Es matrici battaglia navale
** Es matrici 1Informatica 2 Liceo Scientifico Scienze Applicate/Es matrici 1
** Es matrici 2Informatica 2 Liceo Scientifico Scienze Applicate/Es matrici 2
* PuntatoriInformatica 2 Liceo Scientifico Scienze Applicate/Puntatori
* StructInformatica 2 Liceo Scientifico Scienze Applicate/Struct
** Es Bubble Sort con StructInformatica 2 Liceo Scientifico Scienze Applicate/Es Bubble Sort con Struct
* FunzioniInformatica 2 Liceo Scientifico Scienze Applicate/Funzioni
* Funzioni Void e non VoidInformatica 2 Liceo Scientifico Scienze Applicate/Funzioni Void e non Void
** esercizi1 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi1 funzioni
** esercizi2 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi2 funzioni
** esercizi3 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi3 funzioni
* BacktrackingInformatica 2 Liceo Scientifico Scienze Applicate/Backtracking
* TemplateInformatica 2 Liceo Scientifico Scienze Applicate/Template
* FileInformatica 2 Liceo Scientifico Scienze Applicate/File
** File di TestoInformatica 2 Liceo Scientifico Scienze Applicate/File di Testo
** File BinariInformatica 2 Liceo Scientifico Scienze Applicate/File Binari
** File RecordsInformatica 2 Liceo Scientifico Scienze Applicate/File Records
** Es FilesInformatica 2 Liceo Scientifico Scienze Applicate/Es Files
* Esercizi VacanzeInformatica 2 Liceo Scientifico Scienze Applicate/Esercizi Vacanze
** Esercizi1Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi1
** Esercizi2Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi2
** Esercizi3Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi3
* Olimpiadi Informatica
** NobileChimicoInformatica 2 Liceo Scientifico Scienze Applicate/NobileChimico
** Sunnydale
** MappaAnticaInformatica 2 Liceo Scientifico Scienze Applicate/MappaAntica
Modifica il sommario

## 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.
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: uno per dire se la riga da 0 a 7 è occupata o no da una regina uno per dire se la colonna da 0 a 7 è occupata o no da una regina uno per dire se la diagonale (in avanti) da 0 a 14 è occupata o no da una regina uno per dire se la diagonale (in indietro) da 0 a 14 è occupata o no da una regina
si ricorda che la diagonale k in avanti è costituita dalle sole celle la cui sooma degli indici è uguale a k, ad esempio la diagonale 3 ha come celle (0,3) (1,2) (2,1) e (3.0). In modo analogo per le diagonali all'indietro che sono costituite dalle sole celle di indici i,j con i-j=k con k che individua il numero della diagonale, essendo i-j una espressione che può assumere nel caso della scacchiera valori da -7 a +7 e avendo intenzione di usare k=i-j come indice del vettore (che nel c possono essere solo positivi si decide per individuare l'indice del vettore l'espressione k=i-j+7, cosi da avere sempre indici non negativi.
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é 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é 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.
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

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.