## 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