Aranjarea reginelor. Dându-se o tablă de şah de dimensiune nxn (n>3) să se aranjeze pe ea n regine fără ca ele să se atace. Reamintim că o regină atacă linia, coloana şi cele 2 diagonale pe care se află. În figura de mai jos celulele colorare mai închis sunt atacate de regina poziţionată unde indică litera “R”.
#include<iostream>
În algoritmul de mai sus avem de particularizat următoarele:
Instrucţiunea pentru fiecare valoare i din mulţimea Sk execută va fi înlocuită cu o instrucţiune pentru care parcurge toate valorile de la 1 până la n.
Condiţia de a putea plasa o regină pe poziţia k este un pic mai complicată şi presupune verificarea ca să nu se atace cu nici una dintre celelalte k-1 regine deja plasate pe tabla. Dacă pe poziţia k din vectorul X punem o valoare ea va reprezenta coloana pe care se plasează pe tablă regina k. Condiţiile devin astfel:
x[i]¹x[k] şi |k-i|¹|x[k]-x[i]| cu i de la 1 la k-1 şi |x| reprezentând modului lui x.
Condiţia de soluţie este simplă şi presupune plasarea corectă a tuturor celor n regine.
Programul C++ rezultate prin implementarea algoritmului descris mai sus este următorul:
#include<iostream>
#include<cmath>
int x[100],n,nrsol;
void scriesol ()
{ int i,j;
nrsol++;
cout<<„Solutia a „<<nrsol<<” este”;
for(i=1;i<=n;i++)
{ cout<<endl;
for(j=1;j<=n;j++)
if (x[j]==i) cout<<„X „;
else cout<<„O „;
}
}
int potcont(int k)
{ int i;
for(i=1;i<=k-1;i++)
if (x[i]==x[k] || k-i==abs(x[k]-x[i])) return 0;
return 1;
}
void back(int k)
{
int i;
for(i=1;i<=n;i++)
{
x[k]=i;
if (potcont(k))
if (k==n) scriesol();
else back(k+1);
}
}
void main()
{
cin>>n;
nrsol=0;
back(1);
cout<<nrsol<<” solutii”;
}