Modul 02 — Backtracking: problemele clasice

Trei familii de probleme — exact ca în programă

Toate folosesc schema din M01; diferă doar ce înseamnă sol[k] și cum validezi.

👑 Perechi cu poziție

Poziția k ARE sens: la regine, k = linia și x[k] = coloana; la colorare, k = țara și x[k] = culoarea. Soluția = succesiune de perechi (k, x[k]).

➕ Valori parțiale

Cari după tine un „subtotal": partițiile unui număr, plata unei sume cu monede. Validarea folosește suma de până acum — dacă ai depășit, tai ramura PE LOC.

🏆 Optim

Nu vrei toate soluțiile, ci pe CEA MAI BUNĂ: comis-voiajorul. Generezi complet, dar reții minimul — și tai ramurile deja mai scumpe decât el.

Antrenament BAC — 59 de grile de generare

Toate cele 59 de grile, exact ca la BAC, grupate pe modele. Apasă pe o categorie ca să-i deschizi întrebările, apoi alege un răspuns — verde = corect, roșu = greșit, plus explicația.

Cum le rezolvi rapid la BAC: identifică modelul (permutări / aranjamente / combinări / produs cartezian), scrie primele câteva soluții „de mână" respectând ordinea lexicografică, apoi numără sau sari direct la poziția cerută. Toate răspunsurile de mai sus sunt verificate cu program.

Problema Bonus — colorarea cu 4 culori

Prima problemă de implementare. Avem 4 culori: Albastru, Galben, Verde, Roșu. Cum colorăm regiunile unor figuri astfel încât două regiuni vecine să NU aibă aceeași culoare?

🗺️ Mai întâi, vezi principiul animat — harta cu 4 țări, 3 culori

Țara k primește culoarea sol[k]; vecinii nu pot avea aceeași culoare. Vecinătățile: A–B, A–C, B–C, B–D, C–D.

apasă Pas — țara A încearcă prima culoare 👆

Ordinea culorilor contează: algoritmul încearcă mereu culorile în aceeași ordine fixă — roșu → verde → albastru. Fiecare țară ia PRIMA culoare disponibilă; dacă un vecin o blochează, trece la următoarea din ordine. De-asta soluțiile ies mereu în ordine lexicografică.

Observă economia: A și B fixate → C respinge primele culori din prima încercare. Validarea timpurie taie subarbori întregi — exact „eliminarea pe parcurs a traseelor necorespunzătoare" din programă.

A — Albastru G — Galben V — Verde R — Roșu

Modelarea (ca la orice problemă de backtracking): poziția k = o regiune de colorat; sol[k] = culoarea ei (1..4 = A, G, V, R); validarea = niciun vecin deja colorat nu are aceeași culoare. Vecinătățile le ținem într-o matrice vecin[i][k].

🤔 Încearcă tu: 4 culori per regiune, validarea = niciun vecin colorat nu are aceeași culoare. Scrie valid() și bt().

▶ Codul rulează pe un exemplu mic — 3 regiuni care se ating toate (triunghi: 1-2, 1-3, 2-3) — și găsește TOATE colorările, nu doar prima (exact ca backtracking-ul adevărat: după o soluție, revine și caută următoarea). Urmărește în același timp linia de cod și harta:

C++ — se execută

1int sol[20], n; // sol[k] = culoarea regiunii k

2int vecin[20][20]; // 1 dacă se ating

3char nume[] = " AGVR"; // 1=A,2=G,3=V,4=R

4bool valid(int k) {

5 for (int i = 1; i < k; i++)

6 if (vecin[i][k] && sol[i] == sol[k])

7 return false;

8 return true;

10void afisare() {

11 for (int i=1;i<=n;i++) cout<<nume[sol[i]];

12 cout << '\n';

13}

14void bt(int k) {

15 for (int c = 1; c <= 4; c++) { // 4 culori, în ordine

16 sol[k] = c;

17 if (valid(k)) {

18 if (k == n) afisare();

19 else bt(k + 1);

20 }

21 }

22} // bt(1);

exemplul — se colorează

AGVR

apasă „Pas" 👆

Python — aceeași logică

1nume = " AGVR"

2def valid(k, sol):

3 for i in range(1, k):

4 if vecin[i][k] and sol[i]==sol[k]:

5 return False

6 return True

7def afisare(sol):

8 print(''.join(nume[sol[i]] for i in range(1,n+1)))

9def bt(k, sol):

10 for c in range(1, 5): # 4 culori, în ordine

11 sol[k] = c

12 if valid(k, sol):

13 if k == n: afisare(sol)

14 else: bt(k+1, sol)

15sol=[0]*(n+1); bt(1, sol)

De ce e „prima" problemă de implementare: e cel mai curat exemplu de schemă backtracking pe o problemă reală — 4 candidați (culorile) per poziție, o singură condiție de validare (vecinii). Schimbi doar numărul de culori sau matricea vecinilor și rezolvi orice hartă. Recunoști aici exact schema din M01.

🎨 Simulator — colorează colțurile figurilor

Sunt de rezolvat 5 figuri. La fiecare, colorează colțurile (țările) cu cele 4 culori astfel încât colțuri vecine să NU fie identice. Alege o figură, apoi rulează backtracking-ul pas cu pas:

A — Albastru G — Galben V — Verde R — Roșu

alege o figură și apasă „Pas" 👆

Observă: la figura 2 (triunghi) și 3 (pătrat cu diagonale = toate colțurile vecine) ai nevoie de mai multe culori — la pătratul cu diagonale, toate 4 colțurile fiind vecine între ele, îți trebuie fix 4 culori diferite!

Legătură: harta cu 4 țări de sus și cele 5 figuri sunt exact aceeași problemă — colorarea unui graf. Se schimbă doar vecinătățile (matricea vecin[][]) și numărul de culori.

Problema reginelor — tabla animată (n = 4)

4 regine pe tabla 4×4, fără să se atace: linia k primește regina în coloana x[k]. Validare: coloană diferită ȘI diagonale libere.

apasă Pas — regina liniei 1 își caută coloana 👆

1bool valid(int k) { // sol[i] = coloana reginei de pe linia i

2 for (int i = 1; i < k; i++)

3 if (x[i] == x[k] || // aceeași coloană

4 abs(x[i] - x[k]) == k - i) // aceeași diagonală!

5 return false;

6 return true;

Perla validării: două regine stau pe aceeași diagonală exact când |x[i] − x[k]| == k − i — diferența coloanelor egală cu diferența liniilor. O linie de cod, toată geometria tablei.

Colorarea hărții — 4 țări, 3 culori

Țara k primește culoarea x[k]; vecinii nu pot avea aceeași culoare. Vecinătățile: A–B, A–C, B–C, B–D, C–D.

apasă Pas — țara A încearcă prima culoare 👆

Observă economia: A și B fixate → C respinge două culori din prima încercare. Validarea timpurie taie subarbori întregi — exact „eliminarea pe parcurs a traseelor necorespunzătoare" pe care programa o cere comparată cu verificarea la final.

Valori parțiale: plata unei sume cu monede

În câte moduri plătești suma S cu monede de 1, 2 și 5 lei? Soluția crește NEDESCRESCĂTOR (ca la combinări!) și cară suma parțială.

1int m[] = {1, 2, 5};

2void bt(int k, int suma) {

3 if (suma == S) { afisare(k); return; }

4 for (int i = 0; i < 3; i++)

5 if (m[i] >= sol[k-1] && // nedescrescător

6 suma + m[i] <= S) { // nu depășesc!

7 x[k] = m[i];

8 bt(k + 1, suma + m[i]); // valoarea parțială

9 }

10}

S =

Cele două tăieri: „nedescrescător" elimină permutările aceleiași plăți (1+2 = 2+1); „suma + m[i] ≤ S" oprește ramura ÎNAINTE să depășească. Fără ele, același răspuns — dar de sute de ori mai multe apeluri.

Problema de optim: comis-voiajorul

Croaziera din programă: vizitezi fiecare insulă O dată, doar pe trasee acceptate, și revii la plecare — cu cost total MINIM.

Cum se schimbă schema

Soluția = o permutare a orașelor (deci schema de la M01!), cu trei adaosuri: ① validare: există drum acceptat între sol[k−1] și x[k] · ② valoarea parțială: costul acumulat · ③ la soluție completă NU afișezi — COMPARI: if (cost < minim) minim = cost;

Tăierea de aur: dacă deja cost ≥ minim, abandonezi ramura — orice continuare ar fi și mai scumpă.

1void bt(int k, int cost) {

2 if (cost >= minim) return; // tăierea!

3 if (k == n + 1) {

4 // + drumul de întoarcere la start

5 minim = min(minim, cost + d[sol[n]][sol[1]]);

6 return;

7 }

8 for (fiecare oras v nevizitat)

9 if (exista drum x[k-1] → v)

10 { x[k] = v; bt(k+1, cost + d[x[k-1]][v]); }

11}

Punte spre Faza 2: „traseu care vizitează fiecare oraș o dată și revine" are un nume matematic — CICLU HAMILTONIAN, iar orașele + drumurile formează un GRAF. Îl botezăm oficial în Modulul 06. Backtracking-ul tocmai a explorat primul tău graf!

Verificare rapidă

Cinci întrebări — în stil BAC.

Fișa de sinteză

Problemele clasice, condensate.

Regine: k = linia, x[k] = coloana; valid: x[i] ≠ x[k] și |x[i]−x[k]| ≠ k−i (diagonala).

Colorare: k = țara, x[k] = culoarea; valid: diferită de TOȚI vecinii deja colorați.

Plata sumei / partiții: soluție nedescrescătoare + suma parțială cărată în parametru; tai când depășești.

Optim (comis-voiajor): la soluție completă compari cu minimul; tai ramurile cu cost ≥ minim.

Rețeta de modelare: întreabă mereu — ce e k? ce e x[k]? Poziția are semnificație (linie, țară, pas de traseu).

Validarea timpurie bate verificarea finală: aceleași soluții, exponențial mai puține apeluri.

Exersează: pe pbinfo.ro, categoria „Metoda Backtracking" — regine, colorări, partiții; apoi reformulează fiecare cu cele 4 întrebări din M01 înainte de a scrie cod.