problema calului backtracking

Problema calului backtracking

Fiind dată o tablă de şah de dimensiunea nxn şi un cal în colţul stânga sus al acesteia, se cere 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.

#include<iostream.h>
#include<fstream.h>
long st[100][100],vec[20][20],i,n;

int valid(int k)
{if((st[k][1]<1)||(st[k][1]>n)||(st[k][2]<1)||(st[k][2]>n))
return 0;
for(i=1;i<k;i++)
if((st[i][1]==st[k][1])&&(st[i][2]==st[k][2]))
return 0;
return 1;}

int solutie(int k)
{return (k==n*n);}

void tipar(int k)
{for(i=1;i<=k;i++)
cout<<st[i][1]<<” “<<st[i][2]<<”      “;
cout<<endl<<endl;}

void bkt(int k)
{int val;
for(val=1;val<=8;val++)
{st[k][1]=st[k-1][1]+vec[val][1];
st[k][2]=st[k-1][2]+vec[val][2];
if(valid(k))
{if(solutie(k))
tipar(k);
else
bkt(k+1);
}}}
void main()
{int j;
fstream f(“datee.in”,ios::in);
for(i=1;i<=8;i++)
for(j=1;j<=2;j++)
f>>vec[i][j];
cin>>n;
st[1][1]=1;
st[1][2]=1;
bkt(2);}

 

Leave a Reply