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;
}

Explorarea în lărgime

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

typedef struct Nod{
    int cheie;
    struct Nod *urm;
    } nod;

void adauga_coada(nod **prim, int s)
{
    nod*p=NULL;
    p=(nod*)malloc(sizeof(nod));
    p->cheie=s;
    p->urm=NULL;

    if(*prim==NULL)
        *prim=p;
    else
    {
    nod*q=NULL;
    q=*prim;
    while(q->urm!=NULL)
        q=q->urm;
    q->urm=p;
    p->urm=NULL;
    }
}

void sterge_coada(nod **prim)
{
    nod*p=*prim;
    (*prim)=(*prim)->urm;
    free(p);
}

void largime(int a[][20],int n, int s)
{
    nod *prim=NULL;
    int viz[20];
    int i;
    for(i=0;i<n;i++)
        viz[i]=0;
    viz[s]=1;
    printf("%d ",s);
    adauga_coada(&prim,s);
    while(prim!=NULL)
    {
        int v=prim->cheie;
        int w=0;
        for(w=0;w<n;w++)
        {
            if(a[v][w]==1 && viz[w]==0)
            {
                viz[w]=1;
                printf("%d ",w);
                adauga_coada(&prim,w);
            }
        }
        sterge_coada(&prim);
    }
}

int main()
{
    int n,a[20][20],i,j,ok=1;
    FILE *f;
    f=fopen("date.txt","r");
    fscanf(f,"%d",&n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        a[i][j]=0;
    while(ok>0)
    {
        ok=fscanf(f,"%d,%d ",&i,&j);
        a[i][j]=a[j][i]=1;
    }
    printf("Nod de start: ");
    int p;
    scanf("%d",&p);
    largime(a,n,p);
    printf("\nApasati o tasta pentru iesire");
    getch();
    return 0;
}

date.txt

8
0,1 0,2 0,3
1,3 1,5 1,6
2,3 2,4
6,7

Explorarea în adâncime

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

typedef struct Nod
{
    int cheie;
    struct Nod *urm;
} nod;

void adauga_stiva(nod **vf, int x)
{
    nod*p;
    p=(nod*)malloc(sizeof(nod));
    p->cheie=x;
    p->urm=*vf;
    *vf=p;
}

void sterge_stiva(nod **vf)
{
    nod *x;
    x=(*vf);
    (*vf)=(*vf)->urm;
    free(x);
}

void adancime(int a[][20],int n, int s)
{
    nod *prim=NULL;
    int viz[20];
    int i,w,v;
    for(i=0; i<n; i++)
        viz[i]=0;
    viz[s]=1;
    printf("%d ",s);
    adauga_stiva(&prim,s);
    while(prim!=NULL)
    {
        v=prim->cheie;
        w=0;
        for(w=0;w<n;w++)
        {
            if(a[v][w]==1 && viz[w]==0)
                break;
        }
        if(w<n)
        {
            viz[w]=1;
            printf("%d ",w);
            adauga_stiva(&prim,w);
        }
        else sterge_stiva(&prim);
    }
}

int main()
{
    int n,a[20][20],i,j,ok=1;
    FILE *f;
    f=fopen("date.txt","r");
    fscanf(f,"%d",&n);
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            a[i][j]=0;
    while(ok>0)
    {
        ok=fscanf(f,"%d,%d ",&i,&j);
        a[i][j]=a[j][i]=1;
    }
    printf("Nod de start: ");
    int p;
    scanf("%d",&p);
    adancime(a,n,p);
    printf("\nApasati o tasta pentru iesire");
    getch();
    return 0;
}

date.txt

8
0,1 0,2 0,3
1,3 1,5 1,6
2,3 2,4
6,7

Algoritmul lui Dijkstra. Algoritmul lui Dijkstra este o metodă de a stabili drumul de cost minim de la un nod de start la oricare altul dintr-un graf.

#include <stdio.h>
#include <stdlib.h>
void dijkstra (int n,int a[][100])
{
    int tata[n],cost[n][n],dist[n],s[n],i,j,pas,k,q,minim;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i==j)
                cost[i][j]=0;
            else
                if (a[i][j])
                    cost[i][j]=a[i][j];
                else
                    cost[i][j]=100000;
    for (i=1;i<=n;i++)
    {
        s[i]=0;
        dist[i]=cost[1][i];
        if (dist[i]<100000)
            tata[i]=1;
        else
            tata[i]=0;
    }
    s[1]=1;
    tata[1]=0;
    for (i=1;i<n;i++)
    {
        minim=100000;
        for (q=1;q<=n;q++)
            if (dist[q]<minim && dist[q])
            {
                minim=dist[q];
                k=q;
            }

        if (k==100000)
            return;
        s[k]=1;
        for (j=1;j<=n;j++)
            if (s[j]==0 && dist[k]+cost[k][j]<dist[j])
            {
                dist[j]=dist[k]+cost[k][j];
                tata[j]=k;
            }
    }
    for (i=2;i<=n;i++)
        printf("%d - %d\n",dist[i],tata[i]);
}

int main()
{
    int a[100][100],n,m,i,x,y,c,j;
    FILE *f;
    f=fopen("date.txt","r");

    fscanf(f,"%d %d\n",&n,&m);
    for (i=0;i<m;i++)
    {
        fscanf(f,"%d %d %d\n",&x,&y,&c);
        a[x][y]=c;
    }
    dijkstra(n,a);
    return 0;
}

date.txt

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