Backtracking generalizat (în plan)

Backtracking în plan se utilizează pentru acele probleme la care pe fiecare componentă a vectorului soluţie se reţin două sau mai multe valori. Astfel, există două posibilităţi de a memora soluţia:

1. sub forma unei matrice cu două linii şi mai multe coloane. (pe fiecare coloană se vor memora câte două elemente – corespunzătoare componentei k)

2. sub forma unui vector ale cărui element sunt de tip structură.

Problema 1. (Calul pe tabla de şah)Se consideră o tablă de şah de dimensiune N x N şi un cal plasat în colţul din stânga sus. Se cere să

se afişeze toate posibilităţile de mutare a acestei piese de şah, astfel încât să treacă o singură dată prin fiecare pătrat al tablei.

Ex. Pentru N = 5. Primele soluţii sunt:

Solutia: 1 : (1,1) (3,2) (5,1) (4,3) (3,1) (5,2) (4,4) (2,5) (1,3) (2,1) (4,2) (5,4) (3,3) (1,2) (2,4) (4,5) (5,3) (4,1) (2,2) (1,4) (3,5) (2,3) (1,5) (3,4) (5,5) Solutia: 2 : (1,1) (3,2) (5,1) (4,3) (3,1) (5,2) (4,4) (2,5) (1,3) (2,1) (3,3) (1,2) (2,4) (4,5) (5,3) (4,1) (2,2) (1,4) (3,5) (5,4) (4,2) (2,3) (1,5) (3,4) (5,5) Solutia: 3 : (1,1) (3,2) (5,1) (4,3) (3,1) (5,2) (3,3) (1,2) (2,4) (4,5) (5,3) (4,1) (2,2) (1,4) (3,5) (5,4) (4,2) (2,1) (1,3) (2,5) (4,4) (2,3) (1,5) (3,4) (5,5)

Soluţia nr. 1 se memorează în matricea V astfel:1 3 5 4 . . . . . . 51 2 1 3 . . . . . . 5

Semnificaţia vectorului soluţieV[1][k] = linia pe care se află calul după k-1 mutăriV[2][k] = coloana pe care se află calul după k-1 mutări

Obţinerea valorilor pentru o componentă XkPentru rezolvarea problemei se utilizează doi vectori auxiliari: X şi Y cu ajutorul cărora se vor obţine

cele 8 posibilităţi de mutare a unei piese.

Dacă la un moment dat calul se află pe linia “L”, coloana “C”, atunci el poate fi mutat în 8 poziţii:1. Linia: L – 1 Coloana : C – 22. Linia: L + 1 Coloana : C – 23. Linia: L + 2 Coloana : C – 14. Linia: L + 2 Coloana : C + 15. Linia: L + 1 Coloana : C + 26. Linia: L – 1 Coloana : C + 27. Linia: L – 2 Coloana : C + 18. Linia: L – 2 Coloana : C – 1

const X[ ]= { 3, -1, 1, 2, 2, 1, -1, -2, -2};const Y[ ]= { 3, -2, -2, -1, 1, 2, 2, 1, -1};

Noile poziţii pe care poate fi plasat calul se obţin astfel:for (int p=1; p<= 8; p++){

V[1][k] = V[1][k-1] + X[p];V[2][k] = V[2][k-1] + Y[p];

}

Condiţii de continuare ( Funcţia Valid )- Calul să nu părăsească tablă de şah

if ((V[1][k]<1) || (V[1][k]>N) || (V[2][k]<1) || (V[2][k]>N) )return 0;

- Nu mutăm calul pe o poziţie deja parcursă

for (int i=1; i<= k-1; i++)if ((V[1][i]==V[1][k]) && (V[2][i]==V[2][k]) )

return 0;

Condiţia de soluţie finală ( Funcţia Soluţie )- s-au parcurs N x N poziţii

return (k==N*N);

Tipărirea soluţiilor ( Funcţia Tipar )- se tipăreşte matricea pe coloane

for (int i=1 ;i<=k; i++)G << "(" << V[1][i]<< ","<<V[2][i]<< ") ";

REZOLVARE COMPLETĂconst X[]= { 3, -1, 1, 2, 2, 1, -1, -2, -2};const Y[]= { 3, -2, -2, -1, 1, 2, 2, 1, -1};int V[3][100], N, nr_sol=0;int Valid (int k)

{if ((V[1][k]<1) || (V[1][k]>N) || (V[2][k]<1) || (V[2][k]>N) )

return 0;for (int i=1; i<= k-1; i++)

if ((V[1][i]==V[1][k]) && (V[2][i]==V[2][k]) )return 0;

return 1;}int Solutie (int k){

return (k==N*N);}fstream G("01_cal.out", ios::out);void Tipar (int k){

G << endl<< "Solutia: "<< ++nr_sol<< " : ";for (int i=1 ;i<=k; i++)

G << "(" << V[1][i]<< ","<<V[2][i]<< ") ";}void Cal (int k){

for (int p=1; p <= 8; p++){

V[1][k] = V[1][k-1] + X[p];V[2][k] = V[2][k-1] + Y[p];if (Valid (k))

if (Solutie(k))Tipar(k);

elseCal (k+1);

}}void main (void){ cout << "Dimensiune Tabla: "; cin >> N; V[1][1]=1; V[2][1]=1; Cal (2);}

Problema 2. ( Problema Bilei)Un teren este reprezentat sub forma unei matrice A cu N linii şi M coloane. Elementul A[i][j]

reprezintă cota unei porţiuni din teren. Se presupune că o bilă se găseşte pe o porţiune de coordonate (p,q) având o anumită cotă. Se cere să se precizeze toate traseele pe care le poate parcurge bila ca ea să iasă din teren ştiind că se poate deplasa în orice porţiune învecinată cu o cotă strict inferioară cotei terenului pe care se găseşte bila.

Exemplu:3 36 5 49 8 210 10 132 2

Solutia: 1 : (2,2) (2,3) Solutia: 2 : (2,2) (1,3) Solutia: 3 : (2,2) (1,3) (2,3) Solutia: 4 : (2,2) (1,2) Solutia: 5 : (2,2) (1,2) (2,3) Solutia: 6 : (2,2) (1,2) (1,3) Solutia: 7 : (2,2) (1,2) (1,3) (2,3) Solutia: 8 : (2,2) (1,1) Solutia: 9 : (2,2) (1,1) (1,2) Solutia: 10 : (2,2) (1,1) (1,2) (2,3) Solutia: 11 : (2,2) (1,1) (1,2) (1,3) Solutia: 12 : (2,2) (1,1) (1,2) (1,3) (2,3)

const X[]={ 2, 0, 1, 1, 1, 0, -1, -1, -1 };const Y[]={ 2, -1, -1, 0, 1, 1, 1, 0 , -1 };int V[3][100], nr_sol=0, A[10][10], N, M, p, q;int Valid (int k)

{

if ( (V[1][k]<1) || (V[2][k]<1) || (V[1][k]>N) || (V[2][k]>M))return 0;

if (k>1)if ( A[V[1][k]][V[2][k]] >= A[V[1][k-1]][V[2][k-1]])

return 0;for (int i=1; i<=k-1; i++)

if ((V[1][k]==V[1][i]) && (V[2][k]==V[2][i]))return 0;

return 1;}int Solutie (int k){

return ( (V[1][k] == 1)||(V[1][k] == N)||(V[2][k] == 1)||(V[2][k] == M) );}fstream G ("02_bila.out", ios::out);void Tipar (int k){

G << endl<< "Solutia: "<< ++nr_sol<< " : ";for (int i=1 ;i<=k; i++)

G << "(" << V[1][i]<< ","<<V[2][i]<< ") ";}void Bila (int k){

for (int p=1; p<= 8; p++){

V[1][k] = V[1][k-1] + X[p];V[2][k] = V[2][k-1] + Y[p];if (Valid (k)){

if (Solutie(k))Tipar(k);

Bila (k+1); }

}}void main (void){

Citire(); V[1][1]=p; V[2][1]=q; Afisare(); Bila (2); G.close();}

Problema 3. (Problema Labirintului)Un labirint este memorat sub forma unei matrice binare cu semnificaţia: 1 = perete şi 0 = culoar.

Se dă o poziţie de plecare din labirint şi se cer toate posibilităţile de ieşire din labirint mergând numai pe culoare şi fără a trece de două ori prin acelaşi loc.

Exemplu:5 61 0 1 1 1 11 0 1 0 0 01 1 0 1 1 01 0 1 0 1 11 0 1 1 1 14 4

Solutia: 1 : (4,4) (3,3) (4,2) (5,2) Solutia: 2 : (4,4) (3,3) (2,4) (2,5) (3,6) Solutia: 3 : (4,4) (3,3) (2,4) (2,5) (3,6) (2,6) Solutia: 4 : (4,4) (3,3) (2,4) (2,5) (2,6) Solutia: 5 : (4,4) (3,3) (2,4) (2,5) (2,6) (3,6) Solutia: 6 : (4,4) (3,3) (2,2) (1,2)

const X[]={ 2, 0, 1, 1, 1, 0, -1, -1, -1 };const Y[]={ 2, -1, -1, 0, 1, 1, 1, 0 , -1 };int V[3][100], nr_sol=0, A[10][10], N, M, p, q;int Valid (int k){

if ( (V[1][k]<1) || (V[2][k]<1) || (V[1][k]>N) || (V[2][k]>M))return 0;

if (k>1)if (A[V[1][k]][V[2][k]]==1)

return 0;for (int i=1; i<=k-1; i++)

if ((V[1][k]==V[1][i])&& (V[2][k]==V[2][i]))return 0;

return 1;}

int Solutie (int k){ return ( (V[1][k] == 1) || (V[1][k] == N) || (V[2][k] == 1) || (V[2][k] == M) );}fstream G ("03_labir.out", ios::out);void Tipar (int k){

G << endl<< "Solutia: "<< ++nr_sol<< " : ";for (int i=1 ;i<=k; i++)

G << "(" << V[1][i]<< ","<<V[2][i]<< ") ";}void Labirint (int k){

for (int p=1; p<= 8; p++){

V[1][k] = V[1][k-1] + X[p];V[2][k] = V[2][k-1] + Y[p];if (Valid (k)){

if (Solutie(k))Tipar(k);

Labirint (k+1); }

}}void main (void){

Citire();V[1][1]=p; V[2][1]=q;Afisare();Labirint (2);G.close();

}

Problema 4 (FILL)

Se dă o matrice binară. Valorile 1 delimitează o anumită suprafaţă închisă în cadrul matricei (elementele aparţinând acestei suprafeţe sunt marcate cu 0). Se dau de asemenea coordonatele p şi q ale unui element din matrice, semnificând un punct din interiorul acestei suprafeţe. Se cere să se umple suprafaţa căreia aparţine acel punct. Umplerea se poate face doar pe patru direcţii: sus, jos, stanga, dreapta.

Exemplu:4 50 1 0 1 10 0 1 0 11 0 0 0 10 1 1 1 03 4

1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0

const X[]={ 2, 0, 1, 0, -1 };const Y[]={ 2, -1, 0, 1, 0 };int A[10][10], N, M, p, q;

void Citire (){

fstream F("05_FILL.in", ios::in);F>>N>>M;for (int i=1; i<=N; i++)

for (int j=1; j<=M; j++)F>>A[i][j];

F>>p>>q;F.close();

}fstream G("05_fill.out", ios::out);void Afisare (){

G << endl;for (int i=1; i<=N; i++){

G << endl ;for (int j=1; j<=M; j++)

G << A[i][j]<< " ";}

}int Valid (int x, int y){

return ( (A[x][y]==0) && (x>=1) && (x<=N) && (y>=1) && (y<=N));}

void Fill (int x, int y){

if (A[x][y]==0){

A[x][y] = 1;for (int i=1; i<=4; i++)

if (Valid (x+X[i], y+Y[i]))Fill(x+X[i], y+Y[i]);

}}void main (void){

Citire(); Afisare();Fill(p, q);Afisare(); G.close();}

Problema 5 ( FOTO )O fotografie alb-negru este prezentată sub forma unei matrice binare. Ea înfăţişează unul sau mai

multe obiecte. Porţiunile corespunzătoare obiectului (sau obiectelor ) în matrice au valoarea 0. Porţiunile care nu aparţin obiectelor au valoarea –1. Se cere să se determine numărul de obiecte şi să se coloreze fiecare obiect cu culoare diferită.

Exemplu:5 4-1 -1 0 0 0 -1 -1 0 0 0 0 0-1 0 -1 –1 0 0 0 0

3 obiecte 1 1 0 0 0 1 1 0 0 0 0 0 2 0 3 3 0 0 0 0

const X[]={ 2, 0, 1, 1, 1, 0, -1, -1, -1 };const Y[]={ 2, -1, -1, 0, 1, 1, 1, 0 , 1 };int A[10][10], N, M, culoare=0;

void Citire (){

fstream F("06_FOTO.in", ios::in);F>>N>>M;for (int i=1; i<=N; i++)

for (int j=1; j<=M; j++)F>>A[i][j];

F.close();}fstream G("06_foto.out", ios::out);void Afisare (){

G << endl;for (int i=1; i<=N; i++){

G << endl ;for (int j=1; j<=M; j++)

G << setw(3)<<A[i][j];}

}int Valid (int x, int y){

return ( (A[x][y]==-1) && (x>=1) && (x<=N) && (y>=1) && (y<=N));}void Fill (int x, int y, int culoare){

if (A[x][y]==-1){

A[x][y] = culoare;for (int i=1; i<=8; i++)

if (Valid (x+X[i], y+Y[i]))Fill(x+X[i], y+Y[i], culoare);

}}int Colorare (){

for (int i=1; i<= N; i++)for (int j=1; j<= M; j++)

if (A[i][j]==-1)Fill(i,j, ++culoare);

return culoare;}void main (void){

Citire(); Afisare();cout << endl << endl<< "NR. OBIECTE: " << Colorare(); Afisare(); G.close();

}