/*
****************************************
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);
}