#include <iostream>
# include <stdio.h>
# include <stdlib.h>
# include <time.h>

using namespace std;

int N; // For the Number of Rows
int mark;
void printposition(int array[]); //print final solution
void Positions(int a[],int x,int y); //Recursion

void printposition (int array[]) // Each call gets its own count
{
     int b;
     int choose;
     static int counting = 0;
     counting ++;
     printf("\nSolution Number #%d: ", counting); //%d
     for(b=0;b<N;b++)
     printf("(%d,%d) ",b+1,array[b]+1);
     if(counting%5==0) //every 5 solution
     {
      cout << "\nType 0 to exit, 1 to Continue Solving" <<endl;
      scanf("%d",&choose);
     if(choose==0) exit(0);
             };
}

//void Positions(int a1[],int column,int row)
//{ int count1,count2;
//  a1[column]=row;
//  if(column==N-1)
//  { printposition(a1) ;
//    return;
  //         };
 // for(count1=0;count1<N;)
//  {      /* This Loop Finds Suitable Column Numbers , in the NEXT ROW */
 //  for(count2=0;count2<=column;count2++)
 //  if(a1[count2]==count1 || (column+1-count2)*(column+1-count2)==(count1-a1[count2])*(count1-a1[count2]))
 //  goto miss1;
 //  Positions(a1,column+1,count1);
 //  miss1:
 //  count1++;
 //  }
//}

void Positions(int a1[],int column,int row)
{ int count1,count2;
  bool miss = false;
  a1[column]=row;
  if(column==N-1)
    { printposition(a1) ;
    return;
           };
  for(count1=0;count1<N;)
  {      /* This Loop Finds Suitable Column Numbers , in the NEXT ROW */
   for(count2=0;count2<=column;count2++)
   {
      if(a1[count2]==count1 || (column+1-count2)*(column+1-count2)==(count1-a1[count2])*(count1-a1[count2]))
      {
         miss = true;

      }
   }
   if(!miss)
   {
      Positions(a1,column+1,count1);
   }
   count1++;
   }
}

int main()
{
    int *a;
    int count=0;

 printf ("\nInput Size of Chessboard: ");
 scanf("%d",&N);
 a=(int *)(malloc(sizeof(int)*N));
 for(count=0;count<N;count++)
 Positions(a,0,count);

}