#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;

int x[51];
int k, n, nsol;
bool buna;

bool ConditiiContinuare(int k)
{
     // aici testam ca regina k sa nu se atace
     // pe linie sau pe diagonala cu vreuna
     // din reginele dinaintea sa
     bool atac=false;
     int i=1;
     while (!atac && i<k)
           if (x[i]==x[k] || k-i==abs(x[k]-x[i]))
    //doar prima conditie pentru ture si doar a doua conditie pentru nebuni
              atac=true;
           else i++;
     return !atac;
}

void ScrieSolutia()
{
     nsol++;
     cout<<"Solutie "<<nsol<<" este:\n";
     for (int i=1; i<=n; i++)
     {
         cout<<"  Asezati regina nr. "<<i<<" pe linia " <<i<<" si coloana "<<x[i]<<"\n";
         //cout<<x[i]; //pentru generarea permutarilor
     }
     //system("pause");
     getch();
}

int main()
{
    cout<<"Problema reginelor\n";
    cout<<"Dati numarul n: ";
    cin>>n;
    k=1; // plecam cu prima regina
    x[k]=0; // asezam regina aceasta sub tabla
    nsol=0; // numarul de solutii
    while (k>0) // cat timp inca mai avem regine pe tabla
      {
          buna=false; // deocamdata regina nu sta bine acolo
          // cat timp pozitia curenta nu e buna si regina
          // mai poate fi dusa cu o linie mai sus
          while (!buna && x[k]<n)
                {
                  // mut regina mai sus cu un rand/o linie
                  x[k]++;
                  // testez conditiile de continuare k->k+1
                  if (ConditiiContinuare(k)) buna=true;

                }
          if (buna) // daca varianta pentru regina k este buna...
             if (k==n) // daca am ajuns la ultima regina...
                 ScrieSolutia(); // atunci afisam solutia
             else // daca nu am ajuns la ultima,
                  {
                    k++; // trecem la urmatoarea regina
                    x[k]=0; // si o asezam sub tabla
                  }
          else
              k--; // daca nu (mai) gasim o varianta buna
              // atunci ne intoarcem la regina anterioara
      }

}