🌳 Backtracking

Capitolul 3 — Căutare exhaustivă cu revenire, permutări, combinări, problema reginelor

BacktrackingN-ReginePermutăriLabirintCombinări
📖 12 min
0
↩

Ce este Backtracking?

🌀 Analogie: Backtracking = Labirint

Imaginează-ți că ești într-un labirint și trebuie să găsești ieșirea:

  • Mergi pe un drum → dacă ajungi la un blocaj, dai înapoi (backtrack)
  • Încerci altă direcție → dacă și aceea e blocată, dai înapoi din nou
  • Continui până găsești ieșirea sau ai încercat toate drumurile

Backtracking-ul construiește soluția pas cu pas, și dacă o decizie duce la un eșec, se întoarce și încearcă altă variantă.

Backtracking este o tehnică algoritmică de căutare exhaustivă sistematică cu posibilitatea de a reveni (backtrack) atunci când o soluție parțială nu poate fi extinsă la o soluție completă validă.

Idee: Construim soluția element cu element. La fiecare pas, verificăm dacă alegerea curentă respectă restricțiile. Dacă nu, revenim și încercăm altă valoare.
Generare

Generăm toate soluțiile posibile (permutări, combinări, submulțimi)

Optimizare

Găsim soluția optimă care respectă anumite restricții

Decizie

Verificăm dacă există cel puțin o soluție (labirint, sudoku)

Complexitate: De obicei exponențială O(n!) sau O(2ⁿ). Se folosește pentru n mic (< 20-25).
📋

Șablonul general Backtracking

void backtracking(int nivel) {
    if (solutie_completa(nivel)) {
        afiseazaSolutie();
        return;
    }
    for (fiecare valoare posibila v) {
        if (esteValid(nivel, v)) {
            stiva[nivel] = v;         // alege valoarea
            backtracking(nivel + 1); // explorează mai departe
            stiva[nivel] = 0;         // BACKTRACK — dezalege
        }
    }
}
Alegeți o valoare pentru poziția curentă
Verificați dacă valoarea respectă restricțiile (funcția esteValid)
Recurgeți — apelați backtracking pentru nivelul următor
Reveniți (backtrack) — dezalegeți valoarea și încercați alta
Pn

Generarea permutărilor

Generăm toate aranjamentele posibile ale elementelor {1, 2, ..., n}. Numărul de permutări = n!

int n, st[20];
bool folosit[20];

void permutari(int nivel) {
    if (nivel == n + 1) {
        for (int i = 1; i <= n; i++)
            cout << st[i] << " ";
        cout << endl;
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (!folosit[v]) {
            st[nivel] = v;
            folosit[v] = true;
            permutari(nivel + 1);
            st[nivel] = 0;         // backtrack
            folosit[v] = false;   // backtrack
        }
    }
}
Exemplu n=3: Generează 3! = 6 permutări: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
Cnk

Generarea combinărilor

Generăm toate submulțimile de câte k elemente din {1, 2, ..., n}. Numărul de combinări = C(n,k) = n! / (k! × (n-k)!)

int n, k, st[20];

void combinari(int nivel, int startVal) {
    if (nivel == k + 1) {
        for (int i = 1; i <= k; i++)
            cout << st[i] << " ";
        cout << endl;
        return;
    }
    for (int v = startVal; v <= n; v++) {
        st[nivel] = v;
        combinari(nivel + 1, v + 1);  // elementele cresc strict
        st[nivel] = 0;
    }
}
Exemplu n=4, k=2: C(4,2)=6 combinări: (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)
Diferența față de permutări: La combinări ordinea nu contează (1,2) = (2,1), iar fiecare element apare cel mult o dată. Pornind din startVal = v+1 asigurăm ordinea crescătoare și evităm duplicatele.
2ⁿ

Generarea submulțimilor

Generăm toate submulțimile (inclusiv mulțimea vidă) ale unei mulțimi cu n elemente. Numărul total = 2ⁿ.

int n;

void submultimi(int nivel) {
    // Afișăm submulțimea curentă (elementele cu st[i]=1)
    cout << "{";
    bool primul = true;
    for (int i = 1; i <= n; i++)
        if (st[i] == 1) {
            if (!primul) cout << ",";
            cout << i;
            primul = false;
        }
    cout << "} ";

    if (nivel == n + 1) return;

    // Fiecare element poate fi inclus (1) sau exclus (0)
    st[nivel] = 1; submultimi(nivel + 1);
    st[nivel] = 0; submultimi(nivel + 1);
}
Exemplu n=3: 2³=8 submulțimi: {}, {3}, {2}, {2,3}, {1}, {1,3}, {1,2}, {1,2,3}
♛

Problema celor N Regine

Problemă: Plasați N regine pe o tablă de șah N×N astfel încât nicio regină să nu amenințe alta (nu există două regine pe aceeași linie, coloană sau diagonală). 
int n, col[15];  // col[i] = coloana reginei de pe linia i

bool esteValid(int linie, int coloana) {
    for (int i = 1; i < linie; i++) {
        if (col[i] == coloana) return false;  // aceeași coloană
        if (abs(col[i] - coloana) == abs(i - linie)) return false;  // diagonală
    }
    return true;
}

void regine(int linie) {
    if (linie == n + 1) {
        afiseazaSolutie();
        return;
    }
    for (int c = 1; c <= n; c++) {
        if (esteValid(linie, c)) {
            col[linie] = c;
            regine(linie + 1);
            col[linie] = 0;  // backtrack
        }
    }
}
NSoluții distincteSoluții fundamentale
421
5102
641
89212
1072492
🎬

Demo animat — 4 Regine

Vizualizează cum algoritmul backtracking plasează reginele una câte una, detectează conflictele și revine pentru a încerca alte variante.

Normal
Se încearcă Conflict Plasată ♛ = Regină
🔀

Backtracking în labirint

Problemă: Găsiți o cale de la poziția de start la ieșire într-un labirint reprezentat ca matrice. 0 = liber, 1 = perete. 
int lab[10][10], viz[10][10];
int n, m;  // dimensiuni
int dx[] = {-1, 0, 1, 0};  // sus, dreapta, jos, stânga
int dy[] = { 0, 1, 0, -1};

bool labirint(int x, int y, int xf, int yf) {
    if (x == xf && y == yf) return true;  // am ajuns!

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx>=0 && nx<n && ny>=0 && ny<m && !viz[nx][ny] && lab[nx][ny]==0) {
            viz[nx][ny] = 1;         // marcăm ca vizitat
            if (labirint(nx, ny, xf, yf)) return true;
            viz[nx][ny] = 0;         // backtrack — ștergem marcajul
        }
    }
    return false;
}
📝

Probleme tip BAC — backtracking

Problemă 1 (BAC clasic): Generați toate șirurile de n cifre (0-9) care nu conțin două cifre identice consecutive.
Soluție: 
int st[20], n;
void generate(int nivel) {
    if (nivel == n + 1) { /* afișare */ return; }
    for (int c = 0; c <= 9; c++) {
        if (nivel == 1 || st[nivel-1] != c) {  // nu e identic cu precedentul
            st[nivel] = c;
            generate(nivel + 1);
        }
    }
}
Problemă 2: Generați toate partiționările unui număr n ca sumă de numere naturale distincte.
Soluție: 
int st[30], n;
void partitii(int nivel, int suma, int minVal) {
    if (suma == n) { /* afișare st[1..nivel-1] */ return; }
    for (int v = minVal; v <= n - suma; v++) {
        st[nivel] = v;
        partitii(nivel + 1, suma + v, v + 1);
    }
}
// Apel: partitii(1, 0, 1)
Tip examen: Când scrieți backtracking la BAC, arătați clar:
1. Funcția de validare (condiție de continuare)
2. Cazul de bază (soluție completă)
3. Pasul de backtrack (dezalegere)
💪

Exerciții interactive — testează cunoștințele