#include<iostream> /// Problema Damelor - folosind Backtracking
#include<cmath>
using namespace std;
int st[20],n,k,p; /// n = nr de elemente din multime; k = nivelul curent din stiva
int as,ok; /// as=am succesor;  ok=bucata de soluctie este valida
bool succesor(int k) /// verifica daca pe nivelul curent din stiva poate fi incarcata alta valoare (urmatoarea valoare posibila)
{
  if (st[k]<n)
     {
         st[k]++;
         return true;
      }
 return false;
}

bool valid(int k) /// verifica daca "solutia partiala" obtinuta este corecta (in cazul permutarilor se verif. daca elementele sunt diferite intre ele)
{
    for(int i=1;i<k;i++)
       if(st[i]==st[k] || k-i==abs(st[k]-st[i]))
          return false;
    return true;
}

bool final(int k) /// Verifica daca este solutie finala (in cazul permutarilor stiva trebuie sa fie plina pt. a avea o solutie finala)
{
	return (k==n);
}

void tipar() ///Afiseaza solutia
{
   for(int i=1;i<=n;i++)
	cout<<st[i]<<' '; cout<<endl;
}

int main()
{
	cout<<"nr de dame (minim 4) n=";
	cin>>n;
    k=1;

  while(k>0)
     {
      do
         {
           as=succesor(k);
           ok=valid(k);
         } while (as && !ok);

   if (as) ///daca a reusit sa incarce o noua valoare pe nivelul curent din stiva
     if (final(k))  ///daca este solutie finala
          tipar(); /// se afiseaza solutia
         else  /// altfel, daca nu s-a putut incarca o noua valoare pe nivelul curent din stiva (dar solutia partiala e corecta), atunci se urca in stiva
        {
            k++;
            st[k]=0; /// pe nivelul pe care s-a urcat, se pune valoarea 0
         }
    else k--; ///daca nu exista succesor pentru nivelul curent din stiva (pentru varful stivei) atunci se coboara un nivel
     } /// while
	return 0;
}