No image available

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;
}
Citește și  Personalităţi din lumea informaticii (I)