/* Problema celor n dame.
		Fiind data o tabla de sah nxn, se cer toate solutiile de aranjare
		 a n dame, a.i. sa nu se atace reciproc
		 (sa nu se afle pe aceeasi linie, coloana sau diagonala)
    - deoarece pe fiecare linie se afla o singura dama, solutia o
		reprezentam sub forma unui vector cu n componente
    - fiecare nivel ia valori intre 1 si n
		- st[i]=k semnifica faptul ca pe linia i dama ocupa pozitia k
		- 2 dame se afla pe aceeasi linie sau coloana daca  st[i]=st[k]
		- 2 dame se afla pe aceiasi diagonala, daca este indeplinita conditia
    |st[i]-st[j]|=|i-j| (diferenta in modul dintre linii si coloane este aceeasi)
*/
#include <stdio.h>
#include <conio.h>
#include <math.h>
int st[10],n,k;
void Init()
 {
st[k]=0;
 }
int Am_Succesor()
 {
if(st[k]<n)
		{
    	st[k]++;
      return 1;
    }
    else return 0;
 }
int Valid()
 {
 for(int i=1;i<k;i++)
 		if(st[i]==st[k] || abs(st[k]-st[i])==abs(k-i)) return 0;
 return 1;
 }
int Solutie()
 { return k==n;}
void Tipar()
 {
 for(int i=1;i<=n;i++) printf("%d  ",st[i]);
 printf("\n");
 }
void back()
 {
 int As;
 k=1;
 Init();
 while (k>0)
 	{ do  {
				} while ((As=Am_Succesor()) && !Valid());
  	if (As)
    	if (Solutie()) Tipar();
      	else {
        			k++;
              Init();
             }
     else k--;
   }
 }
 void main()
{
clrscr();
printf("n=");
scanf("%d",&n);
back();
getch();
}