Backtracking Avansat C++ — Probleme Complexe

Recapitulare: Ce este Backtracking?

Backtracking este o tehnică de explorare exhaustivă care construiește soluția pas cu pas și revine (backtrack) atunci când constată că soluția curentă nu poate fi completată.

Schelet general:

Copiază
1void backtrack(stare) {
2    if (solutie_completa(stare)) {
3        afisare_solutie();
4        return;
5    }
6    for (fiecare_alegere posibila) {
7        if (este_valid(alegere)) {
8            aplica(alegere);
9            backtrack(stare_noua);
10            elimina(alegere);  // BACKTRACK!
11        }
12    }
13}

Problema Celor N-Regine

Problema: Plasează N regine pe o tablă de șah N×N astfel încât nicio regină să nu se atace.

Copiază
1#include <bits/stdc++.h>
2using namespace std;
3int n, col[100], diag1[200], diag2[200];
4int sol[100];
5int count_sol = 0;
6
7void nRegine(int rand) {
8    if (rand == n + 1) {
9        count_sol++;
10        if (count_sol <= 3) {  // afișăm primele 3 soluții
11            for (int i = 1; i <= n; i++) cout << sol[i] << " ";
12            cout << "\n";
13        }
14        return;
15    }
16    for (int c = 1; c <= n; c++) {
17        if (!col[c] && !diag1[rand+c] && !diag2[rand-c+n]) {
18            sol[rand] = c;
19            col[c] = diag1[rand+c] = diag2[rand-c+n] = 1;
20            nRegine(rand + 1);
21            col[c] = diag1[rand+c] = diag2[rand-c+n] = 0;  // backtrack
22        }
23    }
24}
25
26int main() {
27    cin >> n;
28    nRegine(1);
29    cout << "Total solutii: " << count_sol << "\n";
30}

Rezolvare Sudoku cu Backtracking

Copiază
1bool esteValid(int grid[9][9], int rand, int col, int num) {
2    // verificare rând
3    for (int j = 0; j < 9; j++)
4        if (grid[rand][j] == num) return false;
5    // verificare coloană
6    for (int i = 0; i < 9; i++)
7        if (grid[i][col] == num) return false;
8    // verificare bloc 3×3
9    int startR = rand - rand % 3, startC = col - col % 3;
10    for (int i = 0; i < 3; i++)
11        for (int j = 0; j < 3; j++)
12            if (grid[startR+i][startC+j] == num) return false;
13    return true;
14}
15
16bool solveSudoku(int grid[9][9]) {
17    for (int i = 0; i < 9; i++) {
18        for (int j = 0; j < 9; j++) {
19            if (grid[i][j] == 0) {
20                for (int num = 1; num <= 9; num++) {
21                    if (esteValid(grid, i, j, num)) {
22                        grid[i][j] = num;
23                        if (solveSudoku(grid)) return true;
24                        grid[i][j] = 0;  // backtrack
25                    }
26                }
27                return false;  // nicio valoare nu funcționează
28            }
29        }
30    }
31    return true;  // grila complet rezolvată
32}

Rezolvare Labirint (Flood Fill + Backtracking)

Copiază
1int labirint[100][100];
2bool viz[100][100];
3int n, m;
4int dx[] = {-1, 1, 0, 0};
5int dy[] = {0, 0, -1, 1};
6
7bool rezolvaLabirint(int x, int y, int destX, int destY) {
8    if (x == destX && y == destY) {
9        cout << "Am ajuns la destinatie!\n";
10        return true;
11    }
12    for (int d = 0; d < 4; d++) {
13        int nx = x + dx[d], ny = y + dy[d];
14        if (nx >= 0 && nx < n && ny >= 0 && ny < m
15            && labirint[nx][ny] == 0 && !viz[nx][ny]) {
16            viz[nx][ny] = true;
17            if (rezolvaLabirint(nx, ny, destX, destY)) return true;
18            viz[nx][ny] = false;  // backtrack
19        }
20    }
21    return false;
22}

Optimizare Backtracking: Pruning

Pruning = tăierea ramurilor care nu pot duce la soluții valide.

Copiază
1// Exemplu: generare submulțimi cu sumă dată
2void submultimi(int arr[], int n, int idx, int targetSum, int curSum, vector<int>& current) {
3    if (curSum == targetSum) {
4        for (int x : current) cout << x << " ";
5        cout << "\n";
6        return;
7    }
8    // PRUNING: dacă suma curentă depășește target, nu continuăm
9    if (curSum > targetSum || idx == n) return;
10    
11    // Include arr[idx]
12    current.push_back(arr[idx]);
13    submultimi(arr, n, idx+1, targetSum, curSum + arr[idx], current);
14    current.pop_back();
15    
16    // Exclude arr[idx]
17    submultimi(arr, n, idx+1, targetSum, curSum, current);
18}

Colorarea unui Graf (Graph Coloring)

Copiază
1int culori[100], nrCulori;
2vector<int> adj[100];
3
4bool esteValidColorare(int nod, int culoare) {
5    for (int vecin : adj[nod])
6        if (culori[vecin] == culoare) return false;
7    return true;
8}
9
10bool coloreaza(int nod, int n) {
11    if (nod > n) return true;
12    for (int c = 1; c <= nrCulori; c++) {
13        if (esteValidColorare(nod, c)) {
14            culori[nod] = c;
15            if (coloreaza(nod + 1, n)) return true;
16            culori[nod] = 0;  // backtrack
17        }
18    }
19    return false;
20}

Backtracking-ul avansat este esential la BAC informatica (subiect III) si la titularizare (algoritmică avansată).