BACKTRACKING
Metoda Backtraking se aplică problemelor în care soluția poate fi reprezentată sub forma unui vector
x =
unde S este mulțimea soluțiilor problemei și S = 
, și 
sunt mulțimi finite, având câte 
elemente.
Pentru fiecare problemă, se dau relații între componentele vectorului x, care sunt numite condiții interne; soluțiile posibile (care satisfac condițiile interne) se numesc soluții rezultat. Metoda de generare a tuturor soluțiilor posibile și apoi de determinare a soluțiilor rezultat, prin verificarea îndeplinirii condițiilor interne, necesită foarte mult timp.
- se alege prima valoare din
şi i se atribuie lui x[1] ; - se presupun generate elementele x[1]…x[st-1], cu valori din
; pentru generarea lui x[st] se alege primul element din 
disponibil şi, pentru valoarea aleasă, se testează îndeplinirea condiţiilor de continuare.
Pot apărea urmatoarele situaţii :
a) x[st] îndeplineşte condiţiile de continuare. Dacă s-a ajuns la soluţia finală (st = n), atunci se afişează soluţia obţinută. Dacă nu s-a ajuns la soluţia finală, se trece la generarea elementului următor, x [st+1];
b) x[st] nu îndeplineşte condiţiile de continuare. Se încearcă următoarea valoare disponibila din Sst. Dacă nu se găseşte nici o valoare în Sst care să îndeplinească condiţiile de continuare, se revine la elementul x[st-1] şi se reia algoritmul pentru o nouă valoare a acestuia. Algoritmul se încheie când au fost luate în considerare toate elementele lui S1.
Metoda Backtraking este o tehnică de programare aplicabilă algoritmilor care oferă mai multe soluții și are ca rezultat obținerea tuturor soluțiilor problemei. Fiecare soluție se memorează într-o structură de date de tip stivă implementată cu ajutorul unui vector. Deci fiecare soluție poate fi pusă sub forma unui vector.
Într-un algoritm Backtraking ne interesează toate soluțiile posibile. Pentru a obține fiecare soluție finală se completează stiva nivel cu nivel, trecând astfel prin niște soluții parțiale. Pentru a fi luate în considerare, atât soluțiile finale, cât și cele parțiale, trebuie să îndeplinească anumite condiții numite condiții de validare. O soluție care îndeplinește o astfel de condiție se numește soluție validă.
Toate configurațiile stivei ce reprezintă soluții finale sunt alcătuite din elementele aceleiași mulțimi bine definite pe care o numim mulțimea soluțiilor. Fiecare nouă soluție parțială se obține prin completarea soluției parțiale precedente cu încă o nivel pe stivă. La fiecare nivel se pun valori din mulțimea soluțiilor care nu au fost încercate, până când se obține o soluție validă. În acest moment, se trece la nivelul următor în stivă, pentru a completa mai departe soluția, reluând încercările pe noul nivel.
La un moment dat, pe un anumit nivel nu mai există nici o valoare neîncercată din mulțimea valorilor problemei. În acest caz, se face un pas înapoi în stivă, la nivelul anterior, și se reia căutarea cu valorile rămase neîncercate pe acest nivel anterior.
Respectivul nivel a mai fost vizitat, dar l-am abandonat după ce am pus o valoare care a generat o soluție validă. Deci, este posibil să fi rămas aici valori neîncercate. Dacă nici pe acest nivel nu mai avem valori neîncercate, mai facem un pas înapoi în stivă. Mecanismul revenirilor a determinat denumirea de metodă Backtraking.
Plecând de la nivelul 1 și repetând algoritmul până când pe toate nivelele au fost încercate toate valorile din mulțimea valorilor, se obțin soluții finale care se tipăresc.
Vom implementa metoda Backtraking iterativ, folosind o funcţie unică, aplicabilă oricărei probleme, care determină dacă soluţia este acceptabilă din punctul de vedere al problemei concrete – am numit-o funcţia bun().
Sarcina rezolvitorului este să scrie explicit - pentru fiecare problemă - această funcție.
O posibilă implementare este următoarea:
Pentru datele de intrare
n =3
m[1] = 3
m[2] = 4
m[3] = 2
se obţin rezultatele:
O variantă on-line poate fi experimentată la 
Faptul că, în lipsa unor restricţii concrete (definite prin if – urile urmate de return 0), funcţia bun() întoarce totdeauna valoarea 1, face ca programul să genereze produsul cartezian 
.
Orice problemă concretă se rezolvă, atunci, prin simpla modificare (de obicei uşoară şi intuitivă) a funcţiei bun(), de aşa natură încât aceasta să întoarcă valoarea 0 pentru soluţiile inacceptabile pentru cazul concret, fără nici o modificare a programului principal
Există cazuri în care toate mulţimile 
au acelaşi număr de elemente
caz în care funcţia main() se modifică uşor, pentru a evita citirea repetată a aceleiaşi valori:
Pentru datele de intrare
n = 2
m = 3
se obţin rezultatele:
O variantă on-line poate fi experimentată la 
Mai mult, există cazuri în care toate mulţimile Si au acelaşi număr de elemente, şi anume n (egal cu dimensiunea problemei)
caz în care funcţia main() se poate simplifica şi mai mult, variabila m dispărând cu totul
Pentru datele de intrare
n = 3
se obţin rezultatele:
O variantă on-line poate fi experimentată la 
După cum am mai menţionat, metoda backtracking furnizează toate soluţiile unei probleme.
Dacă este necesară o singură soluţie (oarecare), algoritmul poate fi oprit după prima afişare.
Pentru a determina soluţia optimă (dintr-un anumit punct de vedere, precizat de problemă), vom genera cu metoda backtracking toate soluţiile şi vom reţine dintre acestea doar soluţia cea mai bună (problemă clasică de tip maxim). Aceasta presupune să nu afişăm fiecare soluţie ci, în momentul obţinerii unei noi soluţii, o vom compara cu soluţia precedentă (din punctul de vedere cerut în problema concretă); în cazul în care soluţia curentă este mai bună,vom reţine această soluţie.
EXEMPLE DE PROBLEME REZOLVATE PRIN BACKTRACKING
A. Generarea produsului cartezian
Nici o modificare nu este necesară în funcţia bun; programul construieşte în mod nativ produsul cartezian.
O variantă on-line poate fi experimentată la
B. Generarea permutărilor unei mulţimi
Suntem în situaţia particulară m[1] = m[2] = … = m[n] = n;
Funcţia bun() se modifică după cum urmează:
O variantă on-line poate fi experimentată la 
C. Generarea arnajamentelor de n luate câte k
Studiind atent semantica parametrilor n şi k din expresia 
, observăm că dimensiunea problemei de backtracking este k (deoarece fiecare aranjament va avea câte k componente) ce pot fi selectate din n posibilităţi. Deci, ceea ce este notat cu n în formula 
este variabila m din programul de backtracking, iar ceea ce este notat cu k în aceeaşi formulă, este variabila n din programul nostru.
Funcţia bun() este aceeaşi ca la generarea permutărilor
Ca un exemplu, pentru a genera 
, va trebui să luăm n=2 şi m=6.
O variantă on-line poate fi experimentată la 
D. Generarea combinărilor de n luate câte k
Studiind atent semantica parametrilor n şi k din expresia 
, observăm că dimensiunea problemei de backtracking este k (deoarece fiecare combinare va avea câte k componente) ce pot fi selectate din n posibilităţi. Deci, ceea ce este notat cu n în formula 
, este variabila m din programul de backtracking, iar ceea ce este notat cu k în aceeaşi formulă, este variabila n din programul nostru.
Funcţia bun() devine
Ca un exemplu, pentru a genera 
, va trebui să luăm n=3 şi m=5.
O variantă on-line poate fi experimentată la 
E. Problema aşezării turnurilor pe o tablă de şah
Se cere să se aşeze n turnuri pe o tablă de şah de dimensiune (n × n), fără ca acestea să se atace reciproc.
Suntem în situaţia particulară m[1] = m[2] = … = m[n] = n;
Funcţia bun() este:
şi putem observa uşor că suntem exact în aceeaşi situaţie ca în cazul generării permutărilor!
O variantă on-line poate fi experimentată la 
F. Problema aşezării nebunilor pe o tablă de şah
Se cere să se aşeze n nebuni pe o tablă de şah de dimensiune (n × n), fără ca aceştia să se atace reciproc.
Suntem în situaţia particulară m[1] = m[2] = … = m[n] = n;
Situaţia este mult mai complicată şi mai puţin intuitivă decât în cazul problemei aşezării turnurilor …
Funcţia bun() este atunci:
O variantă on-line poate fi experimentată la 
G. Problema aşezării damelor pe o tablă de şah
Se cere să se aşeze n dame pe o tablă de şah de dimensiune (n × n), fără ca acestea să se atace reciproc.
Suntem în situaţia particulară m[1] = m[2] = … = m[n] = n;
Se observă că această problemă este echivalentă cu rezolvarea simultană a problemelor de aşezare a turnurilor si a celei de aşezare a nebunilor; ca urmare, funcţia bun() este:
O variantă on-line poate fi experimentată la 
H. Problema comis-voiajorului
Deşi este o problemă tipică de backtracking, problema va fi tratată în secţiunea Structuri/ListeStiveCozi/Liste/Liste dublu înlănţuite, deoarece abordarea este acolo mai complexă, implicând şi posibilităţi avasate de reprezentare grafică