Programul REGINE.CPP - Revista EduSoft

Programul REGINE.CPP

Mai jos puteti gasi programul „regine.cpp”, care rezolva problema asezarii celor n regine pe o tabla de sah cu nxn patratele, asa cum l-am scris la curs. Am folosit medoda backtracking in varianta iterativa (repetitiva). L-am scris si testat in Dev C++.

```#include <iostream>

using namespace std;

int x[10];
int n;
int k;
int nrsolutii;

void scrie_solutia()
{
nrsolutii++;
cout<<"\n\nSolutia nr. "<<nrsolutii<<" este:\n";
int i,j;
cout<<"-";
for (i=1; i<=n; i++)
cout<<"--";
cout<<"-\n";
for (i=1; i<=n; i++)
{
cout<<"|";
for (j=1; j<=n; j++)
if (x[j]==i) cout<<"&&"; else cout<<"  ";
cout<<"|\n";
}
cout<<"-";
for (i=1; i<=n; i++)
cout<<"--";
cout<<"-\n";
system("PAUSE");
}

void scrie_solutia_altfel()
{
nrsolutii++;
cout<<"\n\nSolutia nr. "<<nrsolutii<<" este:\n";
for (int i=1; i<=n; i++) {
cout<<"  - asezam regina nr. "<<i;
cout<<" pe coloana "<<i<<" si linia "<<x[i]<<"\n"; }
system("PAUSE");
}

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

int main()
{
int i;
int bine;
cout<<"\n\nProblema celor n regine\n\n";
cout<<"Dati nr. de regine: "; cin>>n;
k=1;
x[k]=0;
while (k>0)
{
bine=0;
while (x[k]<n && !bine) {
x[k]=x[k]+1;
if (continuare(k)) bine=1;
}
if (bine)
if (k==n)
scrie_solutia();
else x[++k]=0;
else    k--;
}
return 0;
}```