Un labirint este codificat printr-o matrice de   elemente ale cărui culoare sunt reprezentate prin elemente egale cu 1, situate în poziţii consecutive pe o aceeaşi linie sau coloană, celelalte elemente fiind 0. O persoană se găseşte în poziţia (i, j) din interiorul labirintului. Se cere afişarea tuturor traseelor de ieşire din labirint care nu trec de mai multe ori prin acelaşi loc.
De fapt, se consideră intrarea prin punctul (1,1) şi ieşirea prin punctul (n,m).

#include <stdio.h>
#include <stdlib.h>

typedef struct punct
{
    int l,c;
}pct;

int a[100][100];

int valid (pct p[100],int k)
{
    if (a[p[k].l][p[k].c]==1)
        return 1;
    else
        return 0;
}

void afis(pct p[100],int k,int n,int m)
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    printf("\n");
}

void back(int k,pct p[100],int n,int m)
{
    int x,pi[]={0,1,0,-1},pj[]={-1,0,1,0};
    for (x=0;x<=3;x++)
    {
        p[k].c=p[k-1].c+pi[x];
        p[k].l=p[k-1].l+pj[x];
        if (valid(p,k))
        {
            a[p[k].l][p[k].c]=2;
            if (p[k].c==m && p[k].l==n)
            {
                afis(p,k,n,m);
            }
            else
            {
                back(k+1,p,n,m);
            }
            a[p[k].l][p[k].c]=1;
        }
    }

}

int main()
{
    FILE *f;
    int i,j,n,m;
    pct p[100];
    f=fopen("in.txt","r");
    fscanf(f,"%d %d",&n,&m);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            fscanf(f,"%d",&a[i][j]);
    for (i=0;i<=m+1;i++)
    {
        a[0][i]=0;
        a[n+1][i]=0;
    }
    for (i=0;i<=n+1;i++)
    {
        a[0][i]=0;
        a[m+1][i]=0;
    }
    for (i=0;i<=n*m;i++)
    {
        p[i].c=0;
        p[i].l=0;
    }
    p[1].c=1;
    p[1].l=1;
    a[1][1]=2;
    back(2,p,n,m);
    return 0;
}

in.txt

5 6
1 0 0 1 0 0
1 1 0 1 0 0
1 1 1 0 0 0
0 1 1 1 0 1
0 0 1 1 1 1

Colorarea grafurilor. Fiind dat un graf neorientat G =(X, Γ) unde X este mulţimea formată din n noduri, iar Γ este mulţimea muchiilor şi un număr de m culori, se cere să se determine toate colorările posibile ale nodurilor grafului folosind cele m culori, astfel încât oricare două noduri adiacente să fie colorate în mod diferit.

#include <stdio.h>
#include <stdlib.h>

int valid(int k,int x[],int a[100][100])
{
    int i;
    for (i=1; i<k; i++)
        if (a[i][k]==1 && x[i]==x[k])
            return 0;
    return 1;
}

void afis(int x[],int n)
{
    int i;
    for (i=1; i<=n; i++)
    {
        printf("%d - %d ",i,x[i]);
    }
    printf("\n");
}

void back(int k,int c,int n,int m,int x[],int a[100][100])
{
    int i;
    for (i=1; i<=c; i++)
    {
        x[k]=i;
        if (valid(k,x,a))
        {
            if (k==n)
                afis(x,k);
            else
                back(k+1,c,n,m,x,a);
        }
    }
}

int main()
{
    int a[100][100],n,m,c,i,j,x[100];
    FILE *f;
    f=fopen("in.txt","r");
    fscanf(f,"%d %d %d",&n,&m,&c);
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            fscanf(f,"%d",&a[i][j]);

    back(1,c,n,m,x,a);
    return 0;
}

in.txt

5 5 3
0 1 0 0 1
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0

Fiind date o tablă de şah de dimensiune   pătrate şi un cal plasat în pătratul din stânga sus al tablei, să se afişeze toate posibilităţile de mutare a calului astfel încât să treacă o singură dată prin fiecare pătrat al tablei.

Problema celor n regine

#include <stdio.h>
#include <stdlib.h>
int r[10],nr=0,n;
void afisare()
{
    int i,j;
    nr++;
    for(i=1; i<n+1; i++)
    {
        for(j=1; j<n+1; j++)
            if(r[i]==j)
                printf("1");
            else printf(".");
        printf("\n");
    }
    printf("\n");
}
int verif(int i)
{
    int j;
    for(j=1; j<i; j++)
        if(r[i]==r[j])
            return 0;
    for(j=1; j<i; j++)
        if(abs(r[i]-r[j])==abs(i-j))
            return 0;
    return 1;
}

void back(int i)
{
    int j;
    for(j=1; j<=n; j++)
    {
        r[i]=j;
        if(verif(i))
            if(i==n)
                afisare();
            else back(i+1);
    }
}

int main()
{
    printf("n=");
    scanf("%d",&n); // n global
    back(1);
    printf("%d solutii",nr);
    printf("\nApasati o tasta pentru terminare");
    getch();
    return 0;
}

Se consideră o mulţime formată din n elemente numere întregi. Să se genereze toate submulţimile acestei mulţimi având proprietatea că suma elementelor lor este egală cu S.

#include <stdio.h>
#include <stdlib.h>
int x[100],n,s,a[100];

void afisare(int n)
{
    int i;
    for(i=1; i<=n; i++)
        printf("%d+",a[x[i]]);
    printf("\b");
    printf("\n");
}

void back(int i, int s)
{
    int j,sr;
    for(j=x[i-1]+1; j<=n; j++)
    {
        x[i]=j;
        sr=s-a[x[i]];
        if(sr==0)
            afisare(i);
        else if(sr)
            back(i+1,sr);
    }
}

int main()
{
    int i;
    printf("n=");
    scanf("%d",&n);
    printf("s=");
    scanf("%d",&s);
    for(i=1; i<=n; i++)
        a[i]=i; // sau citirea elementelor vectorului
    back(1,s);
    printf("\nApasati o tasta pentru terminare");
    getch();
    return 0;
}

Aranjarea pe o tabla de sah n*n a m cai

#include <stdio.h>
#include <stdlib.h>
typedef struct punct{
    int i,j;
    }punct;
punct sol[100];
int x[100],n,m,a[100];

void afisare()
{
    int i;

}

int verif(int k)
{
    int i,j;

}

void back(int k)
{int j;
for(j=1;j<=n;j++)
    {r[k]=j;
    if(verif(k))
        if(i==n)
            afisare();
        else back(k+1);
    }
}

int main()
{
    printf("n=");
    scanf("%d",&n);
    printf("m=");
    scanf("%d",&m);
    back(1);
    printf("\nApasati o tasta pentru terminare");
    getch();
    return 0;
}

Se da un numar n si multimea {1,2,3...n}. Sa se afiseze o submultime de lungime maxima care are proprietatea ca niciun element nu se imparte la niciun altul.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100],x[100],maxi[100],ma=0;

void afisare(int x[],int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[i]%x[j]==0)
        return 0;
return 1;}

void back(int i)
{int j;
for(j=x[i-1]+1;j<=n;j++)
{x[i]=j;
if(verif(i))
    {if(i>ma)
        {ma=i;
    for(int k=1;k<=ma;k++)
        maxi[k]=x[k];
        }
    back(i+1);
    }
   
}
}

int main()
{int i;
cin>>n;
for(i=1;i<=n;i++)
    a[i]=i;
back(1);
afisare(maxi,ma);
}

Un labirint este codificat printr-o matrice L (n x m) ale cărui culoare sunt reprezentate prin elemente egale cu 0 situate in poziţii consecutive pe aceeaşi linie sau aceeaşi coloană. 
O persoană este paraşutată în labirint în poziţia (is, js) din interiorul labirintului. Se cere afişarea tuturor traseelor de ieşire din labirint care nu trec de mai multe ori prin acelaşi loc. 
Ieşirea din labirint se află pe marginea matricei.

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,is,js;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

void citire()
{int i,j;
ifstream f("lab");
f>>n>>m>>is>>js;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>L[i][j];
}


void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<4;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
if(L[inou][jnou]==0 && sol[inou][jnou]==0)

{sol[inou][jnou]=pas;
 if(inou==1 || inou==n || jnou==1 || jnou==m)
 afisare();
 traseu(inou,jnou,pas+1);
 sol[inou][jnou]=0;}
}
}

int main()
{citire();
sol[is][js]=1;
traseu(is,js,2);
cout<<nrsol;
}

Fisier

5 4
3 3
0 0 0 0
1 1 0 1
0 0 0 1
0 1 0 1
0 0 0 1

Solutia I. Hotul are un rucsac cu care poate cara o greutate maxima G. Exista n obiecte carora li se cunoaste greutatea si valoarea. Sa se determine obiectele de valoare maxima <=G.

#include<iostream>
#include<fstream>
using namespace std;
int n,i,G[100],V[100],S[100],REZ[100];
int greutate,vmax;
void afis(int n, int s, int v)
{int k;
for (k=1;k<=n;k++)
cout<<S[k]<<" ";
cout<<"--"<<s<<"--"<<v<<endl;
}

void afiseaza ()
{
for (i=1;i<=n;i++)
if (REZ[i]!=0)
cout<<REZ[i]<<" ";
cout<<" ->> "<<vmax<<endl;
}

void back(int i, int s, int v)
{
int j,k;
for (j=0;j<=1;j++)
{
S[i]=j;
s=s+j*G[i];
v=v+j*V[i];
if (i==n)
{
afis(i,s,v);
if (s<=greutate)
if (v>vmax)
for (k=1;k<=n;k++)
{
REZ[k]=S[k]*V[k];
vmax=v;
}
}
else
if(s<greutate) back(i+1,s,v);
}
}

int main()
{
ifstream fin("rucsac.in");
fin>>n>>greutate;
vmax=-1;
for (i=1;i<=n;i++)
fin>>G[i]>>V[i];
back(1,0,0);
afiseaza();
return 0;
}

Fisier

6 10
3 7
3 4
1 2
1 9
2 4
1 5

Solutia II. Hotul are un rucsac cu care poate cara o greutate maxima G. Exista n obiecte carora li se cunoaste greutatea si valoarea. Sa se determine obiectele de valoare maxima <=G. 

#include<iostream>
#include<fstream>
using namespace std;
int main()
{
int val=0,gr=0,j,V[100],G[100],i,n,greutate,p;
ifstream fin("rucsac.in");
cin>>n>>greutate;
for(i=1;i<=n;i++)
    cin>>G[i]>>V[i];

for(i=1;i<=n;i++)
{    for(j=i+1;j<=n;j++)
        {if(V[j]>V[i])
            {swap(G[i],G[j]);
            swap(V[i],V[j]);}
        if(V[j]==V[i])
            if(G[j]<G[i])
                {swap(G[i],G[j]);
                swap(V[i],V[j]);}
        }
}
      
for(j=1;j<=n;j++)
{
gr=gr+G[j];
if(gr>greutate)
    p=j;
}

for(i=1;i<p;i++)
{val=val+V[i];
cout<<G[i]<<" "<<V[i]<<endl;
}

cout<<"Valoare maxima: "<<val;
return 0;
}

Fisier

6 10
3 7
3 4
1 2
1 9
2 4
1 5

Suma de bani. (bancnotele trebuie sa fie in ordine crescatoare)

#include<iostream>
using namespace std;
int b[100],x[100],nr=0,n,f[100]={0},minim=INT_MAX,mi;

void afisare(int n)
{int i;
for(i=1;i<=n;i++)
    if(x[i])
        cout<<x[i]<<"*"<<b[i]<<" ";
cout<<endl;
nr++;}

int suma(int x[], int n)
{int i,s=0;
for(i=1;i<=n;i++)
    s=s+x[i];
return s;
}

void back(int i,int s,int nrb)
{int j;
if(i==n)
    {if(s%b[i]==0)
        {x[i]=s/b[i];
        afisare(i);
        if(nrb+j<minim)
            {minim=nrb+j;mi=i;
        for(int k=1;k<=i;k++)
            f[k]=x[k];}}
    }
    else{
        for(j=0;j<=s/b[i];j++)
            {x[i]=j;
            if(s==j*b[i])
                {afisare(i);
                if(nrb+j<minim)
                    {minim=nrb+j;mi=i;
                for(int k=1;k<=i;k++)
                    f[k]=x[k];}}
            else back(i+1,s-j*b[i],nrb+j);
            }
        }
    }

int main()
{int i,j,s,nrb=0;
cin>>s>>n;
for(i=1;i<=n;i++)
    cin>>b[i];
back(1,s,0);
cout<<endl<<nr<<" solutii"<<endl;
for(j=1;j<=mi;j++)
    if(f[j])
        cout<<f[j]<<"*"<<b[j]<<" ";
}

Sa se afiseze toate sirurile crescatoare care incep cu n si se termina cu n+k.

#include<iostream>
using namespace std;
int x[100],n,k,nr=0;

int afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
nr++;}

void back(int i)
{int j;
for(j=x[i-1]+1;j<=n+k;j++)
{x[i]=j;
    if(j==n+k)
    afisare(i);
    else back(i+1);
}
}

int main()
{cin>>n>>k;
x[1]=n;
back(2);
}

Sa se afiseze toate submultimile unei multimi care au suma elementelor egala cu o suma data.

#include <iostream>
#include <ctime>
using namespace std;
int x[100],n,s,a[100];

void afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<a[x[i]]<<"+";
cout<<"\b ";
cout<<endl;
}

void back(int i, int s)
{int j,sr;
for(j=x[i-1]+1;j<=n;j++)
{x[i]=j;
sr=s-a[x[i]];
    if(sr==0)
        afisare(i);
    else if(sr)
        back(i+1,sr);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
cout<<"s=";cin>>s;
for(i=1;i<=n;i++)
    cin>>a[i];
back(1,s);
}

Bancnote

#include<iostream>
using namespace std;
int b[100],x[100],nr=0,n;

void afisare(int n)
{int i;
for(i=1;i<=n;i++)
    if(x[i])
        cout<<x[i]<<"*"<<b[i]<<" ";
cout<<endl;
nr++;}

void back(int i,int s)
{int j;
if(i==n)
    {if(s%b[i]==0)
        {x[i]=s/b[i];
        afisare(i);}
    }
    else{
        for(j=0;j<=s/b[i];j++)
            {x[i]=j;
            if(s==j*b[i])
                afisare(i);
            else back(i+1,s-j*b[i]);
            }
        }
    }


int main()
{int i,j,s;
cin>>s>>n;
for(i=1;i<=n;i++)
    cin>>b[i];
back(1,s);
cout<<endl<<nr<<" solutii";
}

Sa se afiseze toate descompunerile unui numar in suma de cifre nenule distincte (partitiile numarului).

#include<iostream>
using namespace std;
int x[100],n;

int afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<"+";
cout<<"\b ";
cout<<endl;}

int verif(int i)
{if(i>1 && x[i]<x[i-1])
    return 0;
return 1;}

void back(int i,int s)
{int j;
for(j=1;j<=s;j++)
{x[i]=j;
    if(x[i]==s)
        afisare(i);
    else back(i+1,s-x[i]);
}
}
       
int main()
{cin>>n;
back(1,n);
}

Ordonate strict crescator

#include<iostream>
using namespace std;
int x[100]={0},n;

int afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<"+";
cout<<"\b ";
cout<<endl;}

int verif(int i)
{if(i>1 && x[i]<x[i-1])
    return 0;
return 1;}

void back(int i,int s)
{int j;
for(j=x[i-1]+1;j<=s;j++)
{x[i]=j;
    if(x[i]==s)
        afisare(i);
    else back(i+1,s-x[i]);
}
}
       
int main()
{cin>>n;
back(1,n);
}

Ordonate crescator (< sau =)

#include<iostream>
using namespace std;
int x[100]={0},n;

int afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<"+";
cout<<"\b ";
cout<<endl;}

int verif(int i)
{if(i>1 && x[i]<x[i-1])
    return 0;
return 1;}

void back(int i,int s)
{int j;
for(j=x[i-1];j<=s;j++)
{x[i]=j;
    if(x[i]==s)
        afisare(i);
    else back(i+1,s-x[i]);
}
}
       
int main()
{cin>>n;
x[0]=1;
back(1,n);
}

1. Fazan

#include<iostream>
using namespace std;
int n,p,x[10],nr=0,c=0,v[100],Sm[100],mx=0;
char a[100][100];

int afisare(int n)
{for(int i=0;i<=n;i++)
    cout<<a[x[i]]<<" ";
nr++;
cout<<endl;}

int verif(int i)
{if(i>1 && strcmp(a[x[i]],a[x[i-1]])==0)
    return 0;
if(i==1 && (a[x[i]][0]!=a[x[i-1]][strlen(a[x[i-1]])-2] || a[x[i]][1]!=a[x[i-1]][strlen(a[x[i-1]])-1]))
    return 0;
for(int j=1;j<i;j++)
    if(x[i]==x[j])
        return 0;
if(i>1 && (a[x[i]][0]!=a[x[i-1]][strlen(a[x[i-1]])-2] || a[x[i]][1]!=a[x[i-1]][strlen(a[x[i-1]])-1]))
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{
    x[i]=j;
    if(verif(i))
        {afisare(i);
    if(i>mx)
    {mx=i;
    for(int k=1;k<=i;k++)
        Sm[k]=x[k];
    }
    if(i<=n)
        back(i+1);
        }
}
}

int main()
{int i,j,nn,k=0;
cin>>n;
for(i=0;i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<endl<<"Cea mai lunga"<<endl;
for(i=0;i<=mx;i++)
    cout<<a[Sm[i]]<<" ";
cout<<"este formatata din "<<mx<<" cuvinte";
cout<<endl<<nr<<" solutii";
}

1.  La un concurs se prezinta n concurenti din m tari. Sa se stabileasca ordinea intrarii in concurs a celor n concurenti astfel incat doi concurenti din aceeasi tara sa nu urmeze unul dupa altul.

#include<iostream>
using namespace std;
int n,x[10],nr=0;

struct concurent{
    int nr;
    char tara[100];
}a[100];

int afisare(int n)
{for(int i=1;i<=n;i++)
    cout<<a[x[i]].nr<<". "<<a[x[i]].tara<<endl;
nr++;
cout<<endl;}

int verif(int i)
{if(strcmp(a[x[i]].tara,a[x[i-1]].tara)==0)
    return 0;
for(int j=1;j<i;j++)
    if(a[x[i]].nr==a[x[j]].nr)
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare(n);
    else back(i+1);
}
}

int main()
{int i,j;
cin>>n;
for(i=1;i<=n;i++)
{a[i].nr=i;
cin>>a[i].tara;
}
back(1);
cout<<nr<<" solutii";
}

2.  Fiind data o multime de n cuburi, fiecare cub fiind caracterizat de lungimea laturii si culoarea sa, sa se scrie un program care sa genereze toate turnurile care se pot forma cu p cuburi astfel incat doua cuburi vecine sa nu aiba aceeasi culoare iar deasupra unui cub sa nu se poata aseza un cub cu latura mai mare.

 #include<iostream>
using namespace std;
int n,p,x[10],nr=0;

struct cub{
    int l;
    char culoare[100];
}a[100];

int afisare(int n)
{for(int i=1;i<=n;i++)
    cout<<a[x[i]].l<<" "<<a[x[i]].culoare<<endl;
nr++;
cout<<endl;}

int verif(int i)
{if(i>1 && strcmp(a[x[i]].culoare,a[x[i-1]].culoare)==0)
    return 0;
for(int j=1;j<i;j++)
    if(x[i]==x[j])
        return 0;
if(i>1 && a[x[i]].l>a[x[i-1]].l)
    return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==p)
        afisare(p);
    else back(i+1);
}
}

int main()
{int i,j;
cout<<"n=";cin>>n;
cout<<"p=";cin>>p;
for(i=1;i<=n;i++)
{cin>>a[i].l>>a[i].culoare;
}
cout<<endl<<"---------"<<endl;
back(1);
cout<<nr<<" solutii";
}

3. Se doreste memorarea mai usoara a unui numar de telefon. Vom asocia fiecarei cifre din numar una din literele de pe aceeasi tasta, de pe telefonul mobil.

a)Sa se afiseze toate  cuvintele care se pot obtine.

b)Sa se afiseze toate cuvintele in care nu exista 2 litere alaturate identice si nu exista 3 consoane alaturate.

Obs: daca numarul de telefon contine cifrele 0 sau 1 afisam un mesaj sau punem 2 caractere, de exemplu * si  !.

#include<iostream>
using namespace std;
int n,p,x[10],nr=0,c=0,v[100];
char a[11][5]={"*","!","abc","def","ghi","jkl","mno","pqrs","tuv","xywz"};

int afisare(int n)
{int k=1;
    for(int i=0;i<n;i++)
        {cout<<a[v[i]][x[i]]<<" ";
        k=k*10;}
nr++;
cout<<endl;}

int verif(int i)
{
    if(x[i]>=strlen(a[v[i]]))
        return 0;
else return 1;
}

void back(int i)
{int j;
for(j=0;j<=3;j++)
{
    x[i]=j;
    if(verif(i))
        if(i==n)
            afisare(n);
        else back(i+1);
}
}

int main()
{int i,j,nn;
cin>>n;
for(i=0;i<n;i++)
    cin>>v[i];
back(0);
cout<<nr<<" solutii";
}

Sa se genereze submultimile multimii {1,2,...,n}

#include<iostream>
using namespace std;
int n,x[10],nr=0;
void afisare(int n)
{for(int i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;nr++;
}

void rec(int i)
{int j;
for(j=x[i-1]+1;j<=n;j++)
{x[i]=j;
afisare(i);
rec(i+1);}}

int main()
{cin>>n;rec(1);
cout<<nr<<" solutii";}

Sa se afiseze elementele produsului cartezian a n multimi. Fiecare multime contine litere mici din alfabet.

#include<iostream>
using namespace std;
int n,nr=0;
char a[10][10],x[10];
void back(int i)
{int j;
for(j=0;j<strlen(a[i]);j++)
{x[i]=a[i][j];
if(i==n)
    {cout<<x+1<<endl;nr++;}
else back(i+1);}
}
int main()
{int i;
cin>>n;
for(i=1;i<=n;i++)
    cin>>a[i];
x[n+1]=NULL;
back(1);
cout<<nr<<" solutii";}

1. Să se genereze toate codurile de lungime n morse formate din '.' şi '-' astfel încât să nu existe două puncte alăturate.

#include<iostream>
using namespace std;
char x[100];
int n,nr=0;
int verif(int i)
{if(i>1 && x[i]=='.' && x[i-1]=='.')
    return 0;
else return 1;
}

void back(int i)
{char j;
for(j='-';j<='.';j=j+'.'-'-')
    {x[i]=j;
if(verif(i))
    if(i==n)
    {    cout<<x+1<<endl;nr++;}
    else back(i+1);
    }
}

int main()
{cin>>n;
x[n+1]=NULL;
back(1);
cout<<endl<<nr<<" solutii";
}

2. Sa se aranjeze 8 regine pe tabla de şah astfel încât acestea să nu se atace. Două regine se atacă dacă sunt situate pe aceeaşi coloană, rând sau diagonală.

#include<iostream>
using namespace std;
int r[10],nr=0;

void afisare()
{int i,j;
nr++;
for(i=1;i<9;i++)
{for(j=1;j<9;j++)
    if(r[i]==j)
        cout<<'.';
    else cout<<'X';
    cout<<endl;}
cout<<endl;}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(r[i]==r[j])
        return 0;
for(j=1;j<i;j++)
    if(abs(r[i]-r[j])==abs(i-j))
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<9;j++)
    {r[i]=j;
    if(verif(i))
        if(i==8)
            afisare();
        else back(i+1);
    }
}

int main()
{
back(1);
cout<<endl<<nr<<" solutii";
}

1. Se citesc n nr nat. Sa se afiseze toate posibilitatile de plasare in fata numerelor a semnelor + sau - astfel incat expresia care se obtine sa aiba valoarea s.

#include<iostream>
using namespace std;
int a[100],x[100],n,s,nr=0;
void afisare()
{int i;
for(i=1;i<=n;i++)
    if(x[i]==1)
        cout<<"+"<<x[i]*a[i];
    else cout<<x[i]*a[i];
cout<<endl;
nr++;
}

int verif(int i)
{int ss=0,j;
if(i!=n)
    return 1;
for(j=1;j<=n;j++)
    ss=ss+(x[j]*a[j]);
if(ss!=s)
    return 0;
return 1;
}

void back(int i)
{int j;
for(j=-1;j<=1;j+=2)
{x[i]=j;
    if(verif(i))
        if(i==n)
            afisare();
        else back(i+1);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
cout<<"s=";cin>>s;
for(int i=1;i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<nr<<" solutii";
}

2. Sa se genereze produsul cartezian {1,2,...,m}x{1,2,...,m} de n ori.

#include<iostream>
using namespace std;
int a[100],x[100],n,m,nr=0;
void afisare()
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
nr++;
}
void back(int i)
{int j;
for(j=1;j<=m;j++)
{x[i]=j;
    if(i==n)
        afisare();
    else back(i+1);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
cout<<"m=";cin>>m;
back(1);
cout<<endl<<nr<<" solutii";
}

3. O persoana a uitat nr de tel. Stie doar ca numarul are 6 cifre, incepe cu 4 si contine 3 cifre de 0, dintre care doua sunt alaturate. Afisati toate variantele.

#include<iostream>
using namespace std;
int x[11],nr=0;
void afisare()
{int i;nr++;
for(i=1;i<7;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{int j,s=0,ok=0;

if(i>=4 && x[i]==0 && x[i-1]==0 && x[i-2]==0)
    return 0;

if(i==6)
{for(j=3;j<7;j++)
    if(x[j]==0 && x[j-1]==0)
        ok=1;
if(ok==0)
    return 0;
for(j=2;j<7;j++)
    if(x[j]==0)
        s++;
    if(s!=3)
        return 0;
}
return 1;
}

void back(int i)
{int j;
for(j=0;j<10;j++)
{x[i]=j;
if(verif(i))
    if(i==6)
        afisare();
    else back(i+1);}
}

int main()
{x[1]=4;
back(2);
cout<<nr;
}

4. Sa se genereze toate palindroamele de lungime n.

#include<iostream>
using namespace std;
int x[11],n,nr=0;
void afisare()
{int i;nr++;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{if(i==1 && x[i]==0)
    return 0;
if(n%2==1)
    if(i>n/2)
        if(x[i]!=x[n-i+1])
            return 0;
if(n%2==0)
    if(i>n/2)
        if(x[i]!=x[n-i+1])
            return 0;
return 1;
}

void back(int i)
{int j;
for(j=0;j<10;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare();
    else back(i+1);}
}

int main()
{
cin>>n;
back(1);
cout<<endl<<nr<<" solutii";
}

1. Sa se genereze toate coadele de 5 cifre cu urmatoarele restrictii: cifrele iau valori de la 1 la 9, numar impar pe ultima pozitie, suma a doua cifre alaturate sa fie minim 4, cifrele sa fie distinct

#include<iostream>
using namespace std;
int x[6],nr=0;
void afisare()
{int i;
for(i=1;i<6;i++)
    cout<<x[i]<<" ";
cout<<endl;
nr++;
}

int verif(int i)
{int j,k,v[100]={0};
if(i==5 && x[i]%2==0)
    return 0;
if(i>1 && x[i]+x[i-1]<4)
    return 0;
if(i==5)
    for(j=1;j<6;j++)
        v[x[j]]++;
for(j=0;j<10;j++)
    if(v[j]>1)
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<10;j++)
{x[i]=j;
if(verif(i))
    if(i==5)
        afisare();
    else back(i+1);
}}

int main()
{back(1);
cout<<endl<<nr;}

2. Sa se genereze toate nr de telefon care incep cu 074 sau 075 (10 cifre), nu contin 3 cifre identice alaturate si contin cel putin doua cifre impare pe ultimele 7 pozitii.

#include<iostream>
using namespace std;
int x[11],nr=0;
void afisare()
{int i;nr++;
for(i=1;i<11;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{int j,s=0;
for(j=1;j<i;j++)
    if(x[i]==x[j])
        return 0;
if(i>4 && x[i]==x[i-1] && x[i-1]==x[i-2])
    return 0;
if(i==10)
{for(j=4;j<11;j++)
    if(x[j]%2==1)
        s++;
    if(s<2)
        return 0;
}
return 1;
}

void back(int i)
{int j;
for(j=0;j<10;j++)
{x[i]=j;
if(verif(i))
    if(i==10)
        afisare();
    else back(i+1);}
}

int main()
{x[1]=0;x[2]=7;x[3]=4;
back(4);
cout<<endl<<endl<<"+++++++++++++++++++"<<endl<<endl<<nr<<endl<<endl;
nr=0;
x[3]=5;back(4);
cout<<endl<<endl<<nr;
}

1. A) Sa se genereze in ordine lexico-grafica cuvintele din multimea a-h cu n litere si care nu contin doua vocale alaturate.

#include<iostream>
using namespace std;
int nr=0,n,x[10];
char a[10]=" abcdefgh";

void afisare(int n)
{int i;
nr++;
for(i=1;i<=n;i++)
    cout<<a[x[i]];
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i] || strchr("aeiou",a[x[i]])!=0 && strchr("aeiou",a[x[i-1]])!=0 && i>1)
        return 0;
    return 1;}

void back(int i)
{int j;
for(j=1;j<=8;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare(n);
    else back(i+1);
}
}

int main()
{cin>>n;
back(1);
cout<<endl<<nr;
}

B) Sa se genereze cuvintele de k litere care incep cu o vocala si se termina cu o consoana.

#include<iostream>
using namespace std;
int nr=0,n,x[10],k;
char a[10]=" abcdefgh";

void afisare(int k)
{int i;
nr++;
for(i=1;i<=k;i++)
    cout<<a[x[i]];
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i])
        return 0;
    if(i==1 && strchr("aeiou",a[x[i]])==0)
        return 0;
    if(i==k && strchr("aeiou",a[x[i]])!=0)
        return 0;
return 1;}

void back(int i)
{int j;
for(j=1;j<=8;j++)
{x[i]=j;
if(verif(i))
    if(i==k)
        afisare(k);
    else back(i+1);
}
}

int main()
{cin>>k;
back(1);
cout<<endl<<nr;
}

2. n copii sunt pregatiti pentru ora de sport. Se cunoaste inaltimea fiecaruia. Trebuie alesi k copii insirati pe un rand astfel incat diferenta dintre oricare 2 elevi sa nu fie mai mare de 10 cm.

#include<iostream>
using namespace std;
int nr=0,n,x[10],k;
int a[100];

void afisare(int k)
{int i;
nr++;
for(i=1;i<=k;i++)
    cout<<a[x[i]]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i])
        return 0;
    if(i>1 && abs(a[x[i]]-a[x[i-1]])>10)
        return 0;
return 1;}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==k)
        afisare(k);
    else back(i+1);
}
}

int main()
{cout<<"n=";cin>>n;
cout<<"k=";cin>>k;
for(int i=1; i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<nr;
}

3. Sa se scrie un algoritm BackTracking care genereaza toate sirurile de 5 cifre 0 si 1 astfel incat sa nu existe mai mult de doua cifre de 0 alaturate.

#include<iostream>
using namespace std;
int nr=0,n,x[10],k;
char a[10]=" 01";

void afisare()
{int i;
nr++;
for(i=1;i<=5;i++)
    cout<<a[x[i]]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(i>1 && a[x[i]]=='0' && a[x[i-1]]=='0')
        return 0;
return 1;}

void back(int i)
{int j;
for(j=1;j<=2;j++)
{x[i]=j;
if(verif(i))
    if(i==5)
        afisare();
    else back(i+1);
}
}

int main()
{back(1);
cout<<endl<<nr;
}

5. n persoane stau pe scaune numerotate de la 1 la n. Oricare doi vecini se ceartă. Să se afişeze toate posibilităţile de a-i reaşeza pe scaune astfel încât să nu fie 2 foşti vecini alăturaţi.

#include<iostream>
using namespace std;
int nr=0,n,x[100],k;
char a[10]=" 01";

void afisare(int n)
{int i;
nr++;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i])
        return 0;
if(i>1 && abs(x[i]-x[i-1])<=1)
    return 0;
return 1;}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare(n);
    else back(i+1);
}
}

int main()
{int i;
cin>>n;
    for(i=1;i<=n;i++)
        x[i]=i;
back(1);
cout<<endl<<nr;
}

1. Se da un vector cu nr intregi cu valori distincte. Se cere sa afisati toate posibilitatile de a alege k din cele n citite astfel incat oricare doua nr alaturate sa fie de paritati diferite.

#include<iostream>
using namespace std;
int a[10];
int n,x[10],nrsol,k;

int afisare()
{int i;
nrsol++;
for(i=1;i<=k;i++)
    cout<<a[x[i]]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i] || a[x[i]]%2==a[x[i-1]]%2 && i>1)
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==k)
        afisare();
    else back(i+1);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
cout<<"k=";cin>>k;
for(i=1;i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<"Nr. sol= "<<nrsol;
}

1.II.

#include<iostream>
using namespace std;
int a[10];
int n,x[10],nrsol,k;

int afisare()
{int i;
nrsol++;
for(i=1;i<=k;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i] || x[i]%2==x[i-1]%2 && i>1)
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=a[j];
if(verif(i))
    if(i==k)
        afisare();
    else back(i+1);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
cout<<"k=";cin>>k;
for(i=1;i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<"Nr. sol= "<<nrsol;
}

2. Se citesc n culori. Sa se formeze toate drapelele de 3 culori astfel incat oricare doua culori alaturate sa fie distincte.

#include<iostream>
using namespace std;
char a[10][10];
int n,x[10],nrsol,k;

int afisare()
{int i;
nrsol++;
for(i=1;i<=k;i++)
    cout<<a[x[i]]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i] || x[i]==x[i-1] && i>1)
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==k)
        afisare();
    else back(i+1);
}
}

int main()
{int i;
cout<<"n=";cin>>n;
k=3;
for(i=1;i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<"Nr. sol= "<<nrsol;
}

Se citesc de la tastatura numele a n copii. Sa se afiseze toate posibilitatile de aranjare a acestora pe n scaune.

#include<iostream>
using namespace std;
char a[10][10];
int n,x[10],nrsol;

int afisare()
{int i;
nrsol++;
for(i=1;i<=n;i++)
    cout<<a[x[i]]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i])
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare();
    else back(i+1);
}
}

int main()
{int i;
cin>>n;
for(i=1;i<=n;i++)
    cin>>a[i];
back(1);
cout<<endl<<"Nr. sol= "<<nrsol;
}

n camile sunt asezate in sir indian. Sa se afiseze toate posibilitatile de rearanjare a acestora astfel incat o camila sa aiba in fata ei o camila diferita de cea din configuratia initiala.

#include<iostream>
using namespace std;
int n,x[10],nrsol;

int afisare()
{int i;
nrsol++;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[j]==x[i] || x[i]-x[i-1]==1 && i>1)
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{x[i]=j;
if(verif(i))
    if(i==n)
        afisare();
    else back(i+1);
}
}

int main()
{int i;
cin>>n;
back(1);
cout<<endl<<"Nr. sol= "<<nrsol;
}