Scrivere un programma che consenta di disporre otto regine su una scacchiera di 8x8 celle senza che nessuna metta sotto scacco un'altra .

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
}