#include<stdio.h>
#include<math.h>

int x[1000],c=0;

int Algo_place(int k);
void result(int n);
void queen(int n);

int main()
{
    int i,n;

    printf("Queens??\n");
    scanf("%d",&n);
    queen(n);

    printf("\nPossible solution is %d\n\n",c);

    return 0;
}
int Algo_place(int k)
{
    int j;
    for(j=1;j<k;j++)
    {
        if((x[j]==x[k])||((fabs(x[j]-x[k])==fabs(j-k))))
            return 0;
    }
    return 1;
}

void result(int n)
{
    int i,j;
    c++;
    printf("\n\nAnswer:%d\n",c);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(x[i]==j)
                printf("Q  ");
            else
            printf(". ");
        }
    printf("\n");
    }
}

void queen(int n)
{
    int k=1;
    x[k]=0;
    while(k!=0)
    {
        x[k]=x[k]+1;
        while((x[k]<=n)&&!Algo_place(k))
            x[k]++;
            if(x[k]<=n)
            {
                if(k==n)
                    result(n);
                else
                {
                    k++;
                    x[k]=0;
                }
            }
            else
                k--;
    }
}