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

Articole înrudite:

Programare – particular si general, concret si abstract Interviu la Google (I) De ce nu se angajeaza absolventii? Epilog (nepublicat) la un manual din 1998 Învăţământul superior din România Lecții de limba germană cu Tatiana Moraru Să ne jucăm cu Scratch! Studiul individual în studenție – calea sigură spre succes Între două sisteme de învăţământ – Romania vs. Franţa Ioan Slavici – vocea satului ardelean Mihail Sadoveanu – penița epicureistă a secolului XX Științele Cognitive – definiție, trăsături Temele pentru acasă – necesitate sau povară? 10 mai – triplă sărbătoare a statului român