nqueen.cpp

#include<bits/stdc++.h>
using namespace std;
#define tr(c,it)\
       for(typeof(c.begin()) = c.begin() ; it != c.end() ; it++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define present(c,x) (c.find(x) != c.end())
bool isSafe(vector<vector <int> > board,int row, int col, int n)
{
    int i,j;
    for(i=1 ; i<row ; i++)
        if(board[i][col])
            return false;
            
    for(i=row-1,j=col-1 ; i>=1 && j>=1 ; i--,j--)
        if(board[i][j])
            return false;
            
    for(i=row-1,j=col+1 ; i>=1 && j<=n ; i--,j++)
        if(board[i][j])
            return false;
    
    return true;
}
void printAns(vector<vector<int> > board, int n)
{
    for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=n ; j++)
            if(board[i][j])
                cout<<board[i][j]<<" ";
}
void nqueen(vector<vector<int> > board, int row, int n)
{
    int i,j;
    for(i=1 ; i<=n ; i++)
    {
        if(isSafe(board,row,i,n))
        {
            board[row][i] = 1;
            if(row == n)
            {
                printAns(board,n);
                // board[row][i] = 0;
            }
            else
                nqueen(board,row+1,n);
        }
        
    }
}
int main()
 {
	//code
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    vector< vector<int> > board(n+1, vector<int>(n+1));
	    nqueen(board,1,n);
	}
	return 0;
}