Laborator 11 - Backtracking (13 mai)

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