De multe ori, în aplicaţii
apar probleme în care se cere găsirea unor soluţii
de forma x=x1x2…xn, unde xi
aparţine Ai, i=1,…,n, în care x1...xn trebuie să
îndeplinească anumite condiţii. Am putea să generăm toate
combinaţiile posibile de valori şi apoi
să le alegem doar pe cele
convenabile.[...]
Astfel, dacă de exemplu ne propunem să generăm toate cuvintele formate cu literele a, b, c, aşa încât fiecare
literă să apară o singură dată, combinaţiile posibile sunt în
număr de 27, dintre care convin doar 6.
Tehnica Backtracking propune generarea soluţiei prin completarea vectorului x în ordinea x1x2...xn şi are la bază un principiu „de bun simţ”: dacă se constată că având o combinaţie
parţială de forma v1v2...vk-1 (unde
v1, ..., vk-1 sunt valori deja fixate), dacă alegem pentru xk
o valoare vk şi combinaţia rezultată
nu ne permite
să ajungem la o soluţie, se renunţă la această valoare şi se încearcă o alta (dintre cele
netestate în această etapă).
Într-adevăr, oricum am
alege celelalte valori, dacă una
nu corespunde nu putem avea
o soluţie.

(Adaptat după Manualul de Informatică, clasa a X-a, Livia Ţoca, Andreea-Ruxanda
Demco, Cristian Opincaru, Adrian Sindile)