1
1. Problema damelor — enunt si idee
Problema damelor (n-queens): Plaseaza n dame pe o tabla de sah n×n astfel incat nicio doua dame sa nu se atace. Doua dame se ataca daca se afla pe aceeasi linie, coloana sau diagonala.
Solutie valida pentru n=4 (output real, Python):
Solutia 1: col=[1, 3, 0, 2] . D . . . . . D D . . . . . D . Solutia 2: col=[2, 0, 3, 1] . . D . D . . . . . . D . D . .
Total: 2 solutii pentru 4x4. (Pentru 8x8 exista 92 solutii.)
Idee backtracking: Punem exact o dama pe fiecare linie (linia = pasul curent). La linia
k incercam fiecare coloana 0..n-1. Verificam daca plasarea e valida fata de toate damele deja puse. Daca da, continuam recursiv cu linia k+1. Daca nu gasim nicio coloana valida, revenim la linia precedenta.
Conditia de validitate — dama de pe linia
linie in coloana coloana este invalida daca exista o linie anterioara l cu:
col[l] == coloana— aceeasi coloanaabs(col[l] - coloana) == abs(l - linie)— pe aceeasi diagonala
2
2. Implementare dame in Python
# Problema damelor - backtracking # col[i] = coloana damei de pe linia i (0-indexat) def dame(n): col = [0] * n # solutia curenta rezultate = [] def valid(linie, coloana): for l in range(linie): if col[l] == coloana: # aceeasi coloana return False if abs(col[l] - coloana) == abs(l - linie): # diagonala return False return True def back(linie): if linie == n: rezultate.append(col[:]) # copie a solutiei return for c in range(n): if valid(linie, c): col[linie] = c back(linie + 1) col[linie] = 0 # revenire back(0) return rezultate # Test n=4 sol = dame(4) print(f"Dame 4x4: {len(sol)} solutii") for s in sol: print(s) # Test n=8 sol8 = dame(8) print(f"Dame 8x8: {len(sol8)} solutii")
Output real (rulat cu python):
Dame 4x4: 2 solutii [1, 3, 0, 2] [2, 0, 3, 1] Dame 8x8: 92 solutii
Complexitate: In cel mai rau caz, arborele de cautare are nn noduri, dar conditia de validitate taie radical ramurile. Complexitate reala: aproximativ O(n!) ramuri explorate, cu un factor de taiere semnificativ in practica.
3
3. Implementare dame in C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
La profilul mat-info intensiv, acelasi algoritm se scrie in C++ cu tablouri statice globale si functie recursiva. Diferente fata de Python: tipuri explicite (int, bool), tablouri de marime fixa, abs() din <cstdlib>.
#include <iostream> #include <cstdlib> using namespace std; int n; int col[10]; // col[i] = coloana damei pe linia i int nr_sol = 0; bool valid(int linie, int coloana) { for (int l = 0; l < linie; l++) { if (col[l] == coloana) return false; if (abs(col[l] - coloana) == abs(l - linie)) return false; } return true; } void back(int linie) { if (linie == n) { nr_sol++; if (nr_sol <= 2) { cout << "Solutia " << nr_sol << ": "; for (int i = 0; i < n; i++) cout << col[i] << " "; cout << "\n"; } return; } for (int c = 0; c < n; c++) { if (valid(linie, c)) { col[linie] = c; back(linie + 1); col[linie] = 0; // revenire } } } int main() { n = 4; cout << "Dame 4x4:\n"; back(0); cout << "Total solutii: " << nr_sol << "\n"; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
Dame 4x4: Solutia 1: 1 3 0 2 Solutia 2: 2 0 3 1 Total solutii: 2
Acelasi rezultat ca versiunea Python. In C++, variabilele globale int col[10] si int nr_sol sunt initializate automat cu 0. Functia back() le acceseaza direct la orice nivel al recursiei, fara a le transmite ca parametri.
4
4. Rezolvarea labirintului prin backtracking
Problema labirintului: Intr-o matrice n×m, celulele sunt libere (0) sau pereti (1). Gaseste toate drumurile de la coltul stanga-sus
(0,0) la coltul dreapta-jos (n-1,m-1), miscandu-te in cele 4 directii (sus, jos, stanga, dreapta).
Labirint 4x4 (0=liber, 1=perete):
0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0
Start: (0,0), Stop: (3,3)
Idee: La fiecare pas, incercam cele 4 directii posibile. Conditia de taiere: iesim din matrice, dam de un perete sau am mai vizitat celula asta pe drumul curent. Cand ajungem la destinatie, salvam drumul. La revenire, eliberam celula din
vizitat.
# Labirint backtracking - gaseste toate drumurile def labirint(grid): n = len(grid) m = len(grid[0]) vizitat = [[False]*m for _ in range(n)] drum = [] solutii = [] dx = [-1, 1, 0, 0] # sus, jos, stanga, dreapta dy = [0, 0, -1, 1] def back(x, y): if x < 0 or x >= n or y < 0 or y >= m: return # iesit din matrice if grid[x][y] == 1 or vizitat[x][y]: return # perete sau deja vizitat vizitat[x][y] = True drum.append((x, y)) if x == n-1 and y == m-1: solutii.append(drum[:]) # drum complet - salvam else: for i in range(4): back(x + dx[i], y + dy[i]) # exploreaza vecini drum.pop() vizitat[x][y] = False # revenire back(0, 0) return solutii grid = [ [0, 0, 1, 0], [1, 0, 0, 0], [1, 0, 1, 0], [0, 0, 0, 0] ] sol = labirint(grid) print(f"Labirint 4x4: {len(sol)} solutii") for i, s in enumerate(sol): print(f" Solutia {i+1}: {s}")
Output real (rulat cu python):
Labirint 4x4: 2 solutii Solutia 1: [(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)] Solutia 2: [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)]
Varianta "prima solutie": Daca vrei doar un drum (nu toate), adauga un flag
gasit = [False] si opreste explorarea dupa prima solutie: if gasit[0]: return. Aceasta varianta este mult mai eficienta cand drumul exista.
Complexitate: In cel mai rau caz (matrice fara pereti), O(4n·m) — fiecare celula are 4 directii. In practica, conditia
vizitat[][] limiteaza drastic numarul de stari.
5
5. Colorarea unui graf cu k culori
Problema colorarii grafului: Dat un graf cu n noduri si o lista de muchii, gaseste toate modurile de a atribui fiecarui nod una din k culori, astfel incat nodurile vecine sa aiba culori diferite.
Graf exemplu: patrat (4 noduri, 4 muchii)
1 -- 2 | | 4 -- 3 Muchii: 1-2, 2-3, 3-4, 4-1
Idee backtracking: Coloram nodurile in ordine 1, 2, ..., n. La fiecare nod incercam culorile 1..k. Verificam daca niciun vecin deja colorat nu are aceeasi culoare. Daca toate nodurile sunt colorate valid, avem o solutie.
# Colorarea unui graf - backtracking def colorare(n, adj, k): culoare = [0] * (n + 1) # culoare[i] = culoarea nodului i solutii = [] def valid(nod, c): for vecin in adj[nod]: if culoare[vecin] == c: return False return True def back(nod): if nod > n: solutii.append(culoare[1:n+1][:]) return for c in range(1, k + 1): if valid(nod, c): culoare[nod] = c back(nod + 1) culoare[nod] = 0 # revenire back(1) return solutii # Graf: patrat 1-2-3-4-1 n = 4 adj = {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [3, 1]} sol2 = colorare(n, adj, 2) print(f"Colorare patrat cu 2 culori: {len(sol2)} solutii") for s in sol2: print(s) sol3 = colorare(n, adj, 3) print(f"Colorare patrat cu 3 culori: {len(sol3)} solutii")
Output real (rulat cu python):
Colorare patrat cu 2 culori: 2 solutii [1, 2, 1, 2] [2, 1, 2, 1] Colorare patrat cu 3 culori: 18 solutii
Interpretare: Patatrul are numarul cromatic = 2 (e bipartit, 4 noduri in ciclu par). Cu 2 culori exista exact 2 colorari distincte. Cu 3 culori avem 18 colorari (mai multe optiuni, dar strict mai multe — culorile sunt numere, deci [1,2,1,2] si [2,1,2,1] si [1,3,1,3] etc. sunt distincte).
Complexitate: O(kn) in cel mai rau caz (k culori, n noduri). Conditia de validitate taie ramurile atunci cand un vecin colorat blocheaza o culoare. Pentru grafuri dense, taierea e mai agresiva.
6
6. Tipare comune si comparatie intre aplicatii
Toate cele trei probleme urmeaza acelasi sablon backtracking. Diferentele sunt doar in ce reprezinta "starea curenta", "candidatii" si "conditia de validitate":
Comparatie: dame vs labirint vs colorare
DAME LABIRINT COLORARE
-----------------------------------------------------------------
Stare curenta col[linie] (x, y) culoare[nod]
Parametru back linie (0..n-1) (x, y) coordonate nod (1..n)
Candidati coloane 0..n-1 4 directii (dx,dy) culori 1..k
Caz de baza linie == n (n-1, m-1) nod > n
Conditie valid coloana+diag. in matrice, vecini !=c
liber, nevizitat
Revenire col[linie]=0 pop drum, culoare[nod]=0
vizitat[x][y]=F
Complexitate ~O(n!) ~O(4^(n*m)) ~O(k^n)
-----------------------------------------------------------------
Retine structura universala:
- Caz de baza: solutia e completa → salveaza/afiseaza,
return - Iterare candidati: pentru fiecare candidat posibil la pasul curent
- Verificare validitate: daca candidatul e valid in contextul curent
- Avansare: aplica candidatul, apeleaza recursiv cu pasul urmator
- Revenire: anuleaza candidatul (resetezi la 0 / False / scoate din drum)
Nota BAC: La subiectele de tip BAC III (clasa XI, backtracking), se cere de obicei: (a) completarea functiei back() sau valid(), (b) urmarirea manuala pentru un n mic, (c) numarul de solutii. Stii sa raspunzi la toate trei dupa aceasta lectie.