Problema damelor

Considerandu-se o tabla de sah de dimansiune nXn, sa se determine toate modalitatile de amplasare a n regine pe tabla de sah astfel incat sa nu se atace doua cate doua(doua regine se ataca daca se afla pe aceeasi linie, coloana, sau diagonala).

 

//problema damelor
#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k;

void init()
{st[k]=0;}

int succesor()
{if (st[k]<n)
{st[k]++;
return 1;
}
else return 0;}

int valid()
{for(int i=1;i<k;i++)
if(st[i]==st[k]  || abs(st[k]-st[i])==abs(k-i)) return 0;
return 1;}

int sol()
{return (k==n);}

void tipar()
{for(int i=1;i<=n;i++) cout<<st[i];
cout<<endl;
}

void bkt()
{int as;k=1;
init();
while(k>0)
{
do {} while ((as=succesor()) && !valid());
if (as)
if (sol()) tipar();
else {k++;init();}
else k--;
}
}

main()
{cout<<"n=";cin>>n;
bkt();
getch();
}

{module orizontal600}

{joscommentenable}