#include<iostream>
#include<cmath>
using namespace std;
class NQueen
{
  public:
    int x[10];
    int n;
    int count=0;
    bool Place(int k, int col)
    {
        for (int j=1; j<=k-1; j++) 
        {
            if((x[j] == col) || (abs(x[j] - col)==abs(j - k)))
                return false;
        }
        return true;
    }
    
    void Display(int n) 
    {
        for (int i = 1; i <= n; i++) 
        {
            for (int j = 1; j <= n; j++) 
            {
                if (x[i] == j) 
                    cout<<"Q ";
                else 
                    cout<<". ";
            }
            cout << endl;
        }
        cout << endl;
    }
    
    void queen(int k, int n)
    {
      for(int colm=1; colm<=n; colm++)
      {
        if(Place(k, colm)) 
        {
            x[k]=colm;
            if(k==n)
            {
              count++;
              cout<<"Solution as Column no.: \n";
              for (int j = 1; j <= n; j++) 
              {
                cout << x[j] << " ";
              }
              cout << endl;
              cout<<"\n";
              Display(n);
            }
            else 
            {
              queen(k+1,n);
            }
        }
      }
    }
};

int main() 
{
  NQueen q;
  int n;
  int k=1;
  cout<<"Enter number of queens: ";
  cin>>n;
  q.queen(k,n);
  if(q.count==0)
  {
    cout<<"No solutions\n";
  }
  else
  {
    cout<<"Total number of solutions= "<<q.count<<endl;
  }
    return 0;
}