Greșeli Frecvente la BAC

EXISTA(k) trebuie să returneze 1 atâta vreme cât mai există valori neexplorate. Dacă domeniul este {1, 2, …, n}, condiția corectă este x[k] < n — mai există cel puțin o valoare (n) de testat. Scriind x[k] <= n, algoritmul va permite și x[k]=n+1 (ieșit din domeniu), generând valori invalide.

int EXISTA(int k) {
    // domeniu {1..n}
    if (x[k] <= n) return 1;
    else return 0;
}

int EXISTA(int k) {
    // domeniu {1..n}
    if (x[k] < n) return 1;
    else return 0;
}

VALID(k) verifică compatibilitatea valorii x[k] cu valorile anterior plasate la pozițiile 1..k−1. Dacă bucla merge până la k inclusiv, va compara x[k] cu el însuși — ceea ce va returna mereu 0 (fals) pentru orice problemă de unicitate, blocând complet algoritmul.

int VALID(int k) {
    for (int i=1; i<=k; i++)
        if (x[i]==x[k]) return 0;
    return 1;
}

int VALID(int k) {
    for (int i=1; i<k; i++)
        if (x[i]==x[k]) return 0;
    return 1;
}

La N-Regine, VALID trebuie să verifice trei condiții: coloana (x[i] ≠ x[k]), diagonala principală (|x[i] − x[k]| ≠ |i − k|) și antidiagonala (aceeași condiție prin valoarea absolută — ea acoperă ambele diagonale). Mulți elevi verifică doar coloana, generând soluții invalide.

int VALID(int k) {
    for(int i=1; i<k; i++)
        if(x[i]==x[k])
            return 0; // fără diagonale
    return 1;
}

int VALID(int k) {
    for(int i=1; i<k; i++)
        if(x[i]==x[k] ||
           abs(x[i]-x[k])==abs(i-k))
            return 0;
    return 1;
}

În schema iterativă BCK, funcția SOLUTIE(k) este apelată după ce x[k] a primit o valoare validă. La momentul apelului, k este nivelul curent (ultima poziție completată). Deci pentru un vector de n elemente, soluția este completă când k == n. Scriind k == n+1, soluția completă nu e niciodată detectată.

int SOLUTIE(int k) {
    if (k == n+1) return 1;
    else return 0;
}

int SOLUTIE(int k) {
    if (k == n) return 1;
    else return 0;
}

Când SOLUTIE(k) returnează 1, k este nivelul ultimei poziții completate (k == n). Funcția TIPAR(k) trebuie să afișeze elementele de la 1 la k inclusiv. Mulți elevi scriu i < k (sau i <= k-1), omițând ultimul element.

void TIPAR(int k) {
    for(int i=1; i<k; i++)
        cout << x[i] << " ";
    cout << endl;
}

void TIPAR(int k) {
    for(int i=1; i<=k; i++)
        cout << x[i] << " ";
    cout << endl;
}

Ramura else k-- din BCK este mecanismul de revenire (backtrack). Fără ea, când domeniul unui nivel se epuizează, algoritmul intră în buclă infinită — k rămâne pe același nivel și EXISTA va returna mereu 0, fără a avansa sau reveni.

while (k > 0)
    if (EXISTA(k)) {
        x[k]++;
        if (VALID(k)) {
            if (SOLUTIE(k)) TIPAR(k);
            else { k++; INIT(k); }
        }
    }
    // else lipseste → k nu se decrementează

while (k > 0)
    if (EXISTA(k)) {
        x[k]++;
        if (VALID(k)) {
            if (SOLUTIE(k)) TIPAR(k);
            else { k++; INIT(k); }
        }
    } else k--;   // backtrack!

În implementarea recursivă a permutărilor, vectorul used[] marchează ce valori au fost deja folosite. La revenirea din recursie (backtrack), marcajul trebuie resetat — altfel elementul rămâne marcat ca folosit și nu va mai putea fi plasat în alte poziții, generând soluții incomplete sau deloc.

void back(int k) {
    for(int v=1; v<=n; v++) {
        if (used[v]) continue;
        x[k] = v;
        used[v] = true;
        if (k==n) tipar();
        else back(k+1);
        // used[v] = false; — LIPSEȘTE
    }
}

void back(int k) {
    for(int v=1; v<=n; v++) {
        if (used[v]) continue;
        x[k] = v;
        used[v] = true;
        if (k==n) tipar();
        else back(k+1);
        used[v] = false;  // backtrack
    }
}