//nqueens
#include<iostream>
#include <conio.h>
#include<math.h>
#include<stdlib.h>
#define max 20
using namespace std;
class nqueens
{
private:
 int n;
public:
    nqueens(int num);
void display(int [],int);
int place(int [],int);
};
nqueens::nqueens(int num)
{
    int x[max];
    int k;
    n=num;
    cout<<"the soln to"<<n<<"queens problem is\n";
    x[0]=-1;
    k=0;
    while(k>=0)
    {
        x[k]=x[k]+1;
        while(x[k]<n&&!place(x,k))
        x[k]=x[k]+1;
        if(x[k]<n)
        if(k==n-1)
        display(x,n);
        else
        {
                k++;
                x[k]=-1;
        }
        else
                k--;
    }
}
int nqueens::place(int x[],int k)
{
    int i;
    for(i=0;i<k;i++)
        if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))
            return 0;
            return 1;
}
void nqueens::display(int x[],int n)
{
    char chessb[max][max];
    int i,j;
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        chessb[i][j]='x';
        for(i=0;i<n;i++)
        chessb[i][x[i]]='q';
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            cout<<chessb[i][j]<<"";
            cout<<"\n";
        }
        cout<<"\n";
}
void main()
{
    int n;
    cout<<"enter the no. of queens\n";
    cin>>n;
    nqueens obj(n);
    getch();
}