/*
****************************************
Problem: N Queen Problem
****************************************
Ashis Kumar Chanda
ID:   1624
CSE,  DU
****************************************
****************************************
*/
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include <iostream>
 
using namespace std;
 
int n=8;		//  number of chessboard n*n
int x[9]={0};	//  take ans of each row
 
void Nqueen(int k);
bool Can_Place(int a, int k);
void Print_ans();
 
int main()
{
	Nqueen(1);		// Let, chess board start from (1,1)  not (0,0)
	Print_ans();
	return 0;
}
 
void Nqueen(int k)
{
	int i,j;
 
	for(j=1; j<= n; j++){
		if( Can_Place(j,k) ){
			x[k]= j;
        if( k== n)
				break;
 
		Nqueen( ++k);//increment coloumn
		}
	}
}// end of NQueen
 
bool Can_Place(int a, int k)
{
	int j;
	for(j=1; j<=(k-1) ; j++){
		if( x[j]== a)
			return false;// two in same row
	}
	if(j!=1 )
		j--;
 
	if( abs(x[j]-a) == abs( j-k ) )
		return false;	// two in same diagonal
 
return true;// no need to check two in same coloumn
}
 
void Print_ans()
{
	puts("Answer is given below:");
	for( int i=1; i<=n; i++)
		printf(" row %d => coloumn %d\n",  x[i], i);
}