Problema reginelor

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

}