Benvenuto in Megistone   Click to listen highlighted text! Benvenuto in Megistone Powered By GSpeech
Benvenuto in Megistone   Click to listen highlighted text! Benvenuto in Megistone Powered By GSpeech
Stampa

Scrivere un programma che consenta di disporre otto regine su una scacchiera di 8x8 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 8x8 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 
}

Click to listen highlighted text! Powered By GSpeech