Esercizio No. 12 Funzioni

Scrivere un programma che consenta di disporre otto regine su una scacchiera di 8×8 celle senza che nessuna metta sotto scacco un’altra.
Soluzione:

Gli algoritmi di backtracking, sono algoritmi che trovano la soluzione di specifici problemi, senza seguire una regola computazionale fissa; essi procedono per tentativi.

Generalmente si decompone il procedimento in vari obiettivi parziali come nel caso degli algoritmi di ricerca , inoltre si fa uso di funzioni ricorsive, cioè, funzioni che invocano loro stesse; nel caso il tentativo effettuato non sia andato a buon fine.

Il problema delle otto regine è un classico esempio di uso dei metodi per tentativi.

Fu studiato, ma non completamente risolto da Gauss nel 1850, anche perchè la caratteristica di questi problemi è che ‘sfuggono’ a soluzioni analitiche.

In breve: otto regine devono essere disposte su una scacchiera di 8×8 celle senza che nessuna metta sotto scacco un’altra.

Scegliamo una opportuna rappresentazione dei dati, poiché è noto dalle regole degli scacchi che una regina può mangiare tutti i pezzi che si trovano nella sua colonna, nella sua riga o su una delle sue diagonali, si deduce che ogni colonna potrà contenere una ed una sola regina. 
Dovendo operare con 8 regine, 8 righe ed 8 colonne, è pressoché obbligatorio dichiarare la costante 

const int n = 8;

Per controllare se una regina non si trova sotto scacco di altre già precedentemente piazzate si elabora la seguente funzione

bool sicura(int regina, int riga){ 
for (int i = 0; i < regina; i++){ 
   // ricava la posizione della regina nella riga iesima 
   int xriga = T[i]; 
   //stessa riga o stessa diagonale 
   if (xriga == riga || xriga == riga – (regina – i) || 
   xriga == riga + (regina – i)) 
   return false; } 
return true; 
}//fine sicura() 

int regina è una variabile che identifica la k-esima regina delle 8 totali
int riga è il valore della riga dove si è deciso di piazzare la regina.
Se la regina si trova sotto scacco viene restituito false altrimenti true e il pezzo viene considerato in una posizione sicura.
Il programma procede per colonne su ognuna delle quali viene disposta una regina, la riga viene individuata dalla seguente funzione:

void tenta(int k){ 
   if (k < n){ 
      for (int i = 0; i < n; i++) 
         if (sicura(k, i)){ T[k] = i; tenta(k + 1); }//fine if 
}else{ 
   for (int i = 0; i < n; i++) cout << T[i] ; 
   cout << endl; 
}//fine else 
}//fine tenta() 

Viene usato il vettore T[k] che memorizza la colonna dove si trova la k-esima regina, poi per tentativi si esplorano tutte le righe dalla 0 alla 7 ( n-1 ) dove sia possibile posizionare il pezzo. 
Se il pezzo finisce in una posizione sicura, si passa alla regina successiva con l’istruzione

tenta(k + 1);

ovviamente ci sarà una regina per ogni colonna ( n=8 ) l’intera procedura viene avviata dal main() con l’istruzione

tenta(0);

e con 0 si intende la regina con indice 0 in colonna 0. 
Per ogni colonna saranno possibili diverse combinazioni qui rappresentiamo solo le prime 10 soluzioni
0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4
0 6 3 5 7 1 4 2
0 6 4 7 1 3 5 2
1 3 5 7 2 0 6 4
1 4 6 0 2 7 5 3
1 4 6 3 0 7 5 2
1 5 0 6 3 7 2 4
se consideriamo la prima soluzione che parte dalla colonna 0:

Una soluzione ovvia, sarebbe stata quella di rappresentare la scacchiera con una matrice quadrata; ma un esame più attento rivela che questa rappresentazione rende più difficile controllare la disponibilità delle posizioni. Considerando che questa operazione è quella più frequentemente eseguita è stato necessario scegliere una rappresentazione che permetta di verificare le posizioni nel modo più semplice possibile.

#include < iostream > 
using namespace std; 
const int n = 8; 
int T[n];//vettore rappresentativo delle 8 righe 

// Controlla se la posizione è sicura 
bool sicura(int regina, int riga){ 
   // Controlla se ogni regina precedente alla attuale 
   // non si trovi sulla stessa riga o su una delle diagonali 
   for (int i = 0; i < regina; i++){ 
   // ricava la posizione della regina nella riga iesima 
   int xriga = T[i]; 
   // stessa riga o stessa diagonale 
   if (xriga==riga || 
       xriga == riga – (regina – i) || 
       xriga == riga + (regina – i)) 
    return false; 
} 
return true; 
}//fine sicura() 

void tenta(int k){ 
if (k < n){ 
   for (int i = 0; i < n; i++) 
   // prima di inserire la k-esima regina in una riga 
   // controlla se la posizione scelta è sicura 
      if (sicura(k, i)){ 
      T[k] = i; 
      tenta(k + 1);// posiziona un’altra regina 
    }//fine if 
}else{ 
// le n=8 regine sono posizionate (stampa) 
   for (int i = 0; i < n; i++) cout << T[i] << ” “; 
   cout << endl; 
}//fine else 
}//fine tenta 

main(){ 
   tenta(0);//regina iniziale in colonna 0 
}