/*8a.Write a program to implement n-Queen's problem*/ 

#include<stdio.h>
#include<conio.h>
int count=0;
int place(int k,int x[])
{
    int i;
    for (i = 1;i<k;i++)
    { /* Vertical collission Diagonal Collission */
        if ((x[i]==x[k]) || (i-x[i]==k-x[k]) || (i+x[i]==k+x[k]))
            return 0;
    }
    return 1;
}
void queen(int n)
{
    int k,x[40],i,j;
    k = 1;
    x[k] = 0;
    while (k != 0)
    {
        x[k] = x[k] + 1;
        while(x[k] <= n && !place(k,x))
            x[k] = x[k] + 1;    
        if (x[k] <= n)
        {
            if (k == n)
            {
                count++;
                printf("\nSolution %d :\n",count);
                for (i = 1;i <= n; i++)
                {
                    for (j = 1; j <= n; j++)
                        if (j == x[i])
                            printf("Q ");
                        else
                            printf("0 ");
                    printf("\n");
                }
                printf("\n\n");
                getch();
            }
            else
            {
                k = k + 1;
                x[k] = 0;
            }
        }
        else
            k = k - 1;
    }
}
void main()
{
    int n;
    clrscr();
    printf("Enter the number of queens : ");
    scanf("%d",&n);
    queen(n);
    printf("\nTotal no. of solutions is %d",count);
    getch();
}