Problem Statement - II

Problem Statement:-

                              N x N board is given for 'N' queen. We want to place 'N' queen on the board in non-attacking position.

Note: Queen can attack horizontally, vertically and diagonally.

For this use 1-D array-X where K^th element of array-X will give column of K^th queen.

Example:

Constraint on array-X:

1. Every value stored in array-X should be unique

2. Every value stored in array-X should be between 1 to 'N'

Program:

#include<stdio.h>

#include<math.h>

#define MAXSIZE 10

int x[MAXSIZE];

int n;

void printsolution()

{

    int i, k;

    static int solno=1;

    printf("\nSolution %d: ", solno++);

    for(i=1;i<=n;i++)

    {

        printf("%d ",x[i]);

    }

}

int place(int k, int i)

{

    int j;

    for(j=1; j<k; j++)

    {

        if( (x[j] == i) || (abs(x[j]-i) == abs(j-k)) )

            return 0;

    }

    return 1;

}

void nqueen(int k)

{

    int i;

    for(i=1; i<=n; i++)

    {

        if(place(k,i))

        {

            x[k] = i;

            if(k == n)

                printsolution();

            else

                nqueen(k+1);

        }

    }

}

void main()

{

    printf("\nEnter board size: ");

    scanf("%d",&n);

    if(n>MAXSIZE)

    {

        exit(1);

    }

    nqueen(1);

}

Output:

Enter board size: 4

Solution 1: 2 4 1 3

Solution 2: 3 1 4 2