Algoritmul general de backtracking

În pagina despre backtracking am văzut ideea metodei: construim soluția pas cu pas și ne întoarcem când rămânem fără opțiuni. Această idee se traduce foarte natural într-un subprogram recursiv, în care fiecare apel se ocupă de o singură poziție a soluției. Chiar dacă în materia de Bacalaureat nu este inclus și acest algoritm, este bine de observat construcția algoritmului.

Aproape orice algoritm de backtracking are aceeași formă: o funcție care primește poziția curentă k, încearcă pe rând valorile candidate și, pentru fiecare valoare validă, fie afișează soluția completă, fie se autoapelează pentru poziția următoare.

void back(int k) {
    for (fiecare valoare candidat v pentru pozitia k)
        if (v este valida) {
            sol[k] = v;            // alegem valoarea
            if (solutia este completa)
                afiseaza();
            else
                back(k + 1);       // avansam la pozitia urmatoare
            // la revenire, alegerea se anuleaza si incercam urmatoarea valoare
        }
}

Trei ingrediente apar mereu: valorile candidate pe care le încercăm, condiția de validare care spune dacă o alegere este acceptabilă și pasul înapoi, prin care anulăm alegerea curentă pentru a încerca alta.

Să implementăm exemplul din pagina anterioară: generarea numerelor de 4 cifre cu cifre impare distincte.

#include <iostream>
using namespace std;

int cifre[] = {1, 3, 5, 7, 9}; // valorile candidate
int sol[5];                    // sol[1..4], cifrele alese
bool folosit[10];              // folosit[c] = cifra c este deja in solutie

void back(int k) {
    for (int i = 0; i < 5; i++) {
        int c = cifre[i];
        if (!folosit[c]) {            // conditie: cifra distincta
            sol[k] = c;
            folosit[c] = true;        // marcam alegerea
            if (k == 4) {             // solutie completa (4 cifre)
                for (int j = 1; j <= 4; j++) cout << sol[j];
                cout << ' ';
            } else
                back(k + 1);          // alegem cifra urmatoare
            folosit[c] = false;       // pasul inapoi: eliberam cifra
        }
    }
}

int main() {
    back(1);
    return 0;
}

Programul afișează, în ordine crescătoare, toate cele 120 de numere: 1357 1359 1375 ... 9751 9753.

Să urmărim cum se regăsesc cele trei ingrediente:

• valorile candidate sunt cifrele din vectorul cifre, încercate în ordine crescătoare;
• condiția de validare este !folosit[c]: alegem o cifră doar dacă nu a fost deja folosită, ceea ce asigură cifre distincte;
• pasul înapoi este linia folosit[c] = false;: după ce am explorat toate soluțiile care încep cu alegerea curentă, eliberăm cifra pentru a o putea folosi pe altă poziție.

Apelul back(1) pornește construcția de la prima poziție. Când k ajunge la 4, soluția are toate cele patru cifre și o afișăm; altfel, ne adâncim cu un nivel prin back(k + 1).

Scheletul de mai sus se adaptează la multe probleme: schimbăm valorile candidate, condiția de validare și momentul în care considerăm soluția completă, păstrând aceeași structură recursivă cu pas înapoi. Backtracking devine astfel un tipar pe care, odată înțeles, îl putem aplica la generarea permutărilor, a combinărilor sau la probleme clasice precum așezarea damelor pe tabla de șah.