Tuesday, 21 June 2016

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 Kth element of array-X will give column of Kth 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