⚙️ Ce este Backtracking?
Backtracking este o tehnică algoritmică de tip „încearcă și renunță" — algoritmul construiește o soluție pas cu pas, iar atunci când constată că o alegere curentă nu poate duce la o soluție validă, revine la pasul anterior și încearcă o altă variantă.
🔍
Explorare
Încearcă sistematic toate variantele posibile din starea curentă.
✅
Validare
La fiecare pas verifică dacă alegerea respectă condițiile problemei.
↩️
Revenire
Dacă o cale e blocată, anulează ultimul pas și încearcă alt drum.
🎯
Soluție
Găsește una sau toate soluțiile valide, garantat complet.
📐 Schema standard BKT (iterativă)
Forma canonică predată în liceu și folosită la BAC. Algoritmul folosește șase funcții cu roluri bine definite și o buclă principală while(k > 0).
INIT(k)
Inițializează x[k] cu valoarea de dinaintea primului element al domeniului (de obicei 0 sau valmin−1).
EXISTA(k)
Verifică dacă mai există valori netestate în domeniu pentru poziția k. Returnează 1 dacă x[k] poate fi incrementat.
VALID(k)
Verifică dacă valoarea aleasă pentru poziția k este compatibilă cu valorile deja plasate la pozițiile 1..k−1.
SOLUTIE(k)
Returnează 1 atunci când vectorul soluție este complet — de obicei când k == n.
TIPAR(k)
Afișează soluția completă. Bucla de afișare iterează i = 1..k (inclusiv poziția curentă).
BCK()
Funcția principală: pornește de la k=1, apelează INIT, apoi intră în bucla
while care alternează avansare și revenire.
// Schema iterativă BCK — forma generală
void BCK() {
int k = 1;
INIT(k);
while (k > 0)
if (EXISTA(k)) {
x[k]++;
if (VALID(k)) {
if (SOLUTIE(k)) TIPAR(k);
else { k++; INIT(k); }
}
} else k--;
}
🔄 Recursiv vs Iterativ
Schema recursivă
void back(int k) {
for (int v = 1; v <= n; v++) {
x[k] = v;
if (valid(k)) {
if (k == n) tipar();
else back(k+1);
}
}
}
// apel: back(1);
Stiva de apeluri gestionează revenirea. Mai lizibilă, preferată în implementări moderne.
Schema iterativă (BAC)
// INIT/EXISTA/VALID/SOLUTIE/TIPAR
void BCK() {
int k = 1; INIT(k);
while (k > 0)
if (EXISTA(k)) {
x[k]++;
if (VALID(k)) {
if (SOLUTIE(k))
TIPAR(k);
else { k++; INIT(k); }
}
} else k--;
}
Explicit, fără apeluri recursive. Forma cerută la BAC în România. Revenirea se face prin
k--.⏱ Complexitate
Permutări (n elemente)
O(n · n!)
Submulțimi (n elemente)
O(n · 2ⁿ)
Colorare graf (k culori)
O(kⁿ)
N-Regine (n×n tablă)
O(n!)
Pruning-ul (tăierea ramurilor invalide) reduce drastic numărul de stări explorate în practică față de cazul cel mai rău.
✅ Când se aplică BKT?
✓
Există un concept de soluție parțială care se construiește incremental
✓
Se poate testa rapid dacă o soluție parțială poate duce la o soluție completă
✓
Se cer toate soluțiile sau prima soluție validă
✗
Nu e potrivit când se cere soluția optimă — folosești programare dinamică sau greedy
✗
Nu e eficient dacă nu există constrângeri — degenerează în forță brută
🌳 Arborele de decizie
BKT construiește implicit un arbore de decizie parcurs în adâncime (DFS). Fiecare nod reprezintă o stare parțială a soluției; arcele reprezintă alegerile posibile. Ramurile ce violeaza constrângerile sunt tăiate fără a fi explorate.
🌱
Rădăcină
Starea inițială — nicio alegere făcută încă.
🌿
Noduri interne
Soluții parțiale. Fiecare nivel = o poziție din vectorul soluție.
🍀
Frunze valide
Soluții complete. TIPAR() afișează soluția.
✂️
Pruning
VALID() = fals → ramura e abandonată imediat.
Lecții disponibile
01
Lecția 01 · Aplicație
DrumExpress
Găsește toate rutele posibile între 10 orașe din România. Algoritmul BKT calculează fiecare drum și îl vizualizează pe hartă interactivă cu date reale.
02
Lecția 02 · Combinatorică
N-Regine
Plasează N regine pe o tablă de șah N×N astfel încât nicio regină să nu atace alta. Simulare animată BKT cu tablă interactivă 4×4–6×6.
03
Lecția 03 · Permutări
Generare de Permutări
Generează toate cele 6 permutări ale șirului [1,2,3] prin BKT. Animație cu poziții, pool de elemente disponibile și toate permutările găsite.
04
Lecția 04 · Puzzle
Sudoku Solver
Rezolvă un Sudoku 9×9 real prin Backtracking pur. Vizualizează fiecare plasare și revenire în timp real, cu statistici despre numărul de pași.
05
Lecția 05 · Graf
Turul Calului
Găsește un tur complet al unui cal de șah pe o tablă 5×5 — vizitează toate cele 25 de celule exact o dată. Animație BKT cu traseu colorat și SVG.
06
Lecția 06 · Parcurgere
Bila pe Teren
O bilă pleacă dintr-o parcelă interioară și se poate mișca spre parcele vecine cu înălțime mai mică. Găsim toate căile spre marginea terenului prin BKT.
07
Lecția 07 · Grafuri
Colorarea Hărții
Colorăm o hartă de 9 regiuni poligonale cu 4 culori astfel încât nicio două regiuni vecine să nu aibă aceeași culoare. Teorema celor 4 culori în acțiune.
08
Lecția 08 · Labirint
Labirint — Toate Ieșirile
Un șoricel pornește din centrul unui labirint 7×7 și caută toate căile posibile spre ieșire. Algoritmul BKT explorează sistematic fiecare ramură, revenind când se blochează.
09
Lecția 09 · Cifre
Cifre Distincte
Generează toate numerele formate din cifre distincte a căror sumă este n. BKT construiește numărul poziție cu poziție, tăind ramurile în care suma deja depășește n.
!
Ghid · BAC Backtracking
Greșeli Frecvente la BAC
Cele 8 greșeli clasice din schema BKT: INIT greșit, EXISTA cu condiție inversă, VALID fără diagonale, k-- lipsă și altele — cu cod greșit vs. corect.
Q
Chestionar · Evaluare
Test Backtracking
15 întrebări din toate categoriile: teorie, adevărat/fals, trasare algoritm, complexitate, cod și aplicații practice.
Despre BKT Hub
Ce este?
BKT Hub este o platformă educațională care prezintă algoritmul Backtracking prin aplicații interactive și exemple concrete. Fiecare lecție abordează o problemă clasică cu o implementare completă.
Creatori
GR
Gavrilescu Razvan-Cristian
GR
Gavrilescu Robert Stefan