Programming Geek
Rated 4.7/5 based on 1446 reviews

N Queen Problem

Problem : Given a n x n grid, how would you place n queens so that no two are attacking. Two queens are said to be attacking if they are on same row, column or diagonal. The naive solution of this problem will require to find  all the permutations i.e. finding all the n! arrangements. A typical example of n queen problem is 8 queen problem which requires us to find possible placements of 8 queens on a 8 x 8 chess board. One of the arrangements of 8 x 8 problem is shown below : 

Placements of 8 queens over 8 x 8 chess board
Solution of this problem can be thought as follows:

  • We start from first row and proceed to next row till last row.
  • if next queen to be placed has same column value as already placed queen has then don't place the queen. This can be checked by traversing from i=1 to i= k-1 where k is the next row where queen is to be placed.
  • if next queen to be placed lies in any of the diagonals of already placed queens then don't place the queen. This can be done by merely checking (abs(i-k)==abs(j-l)) where (i,j) is the place of any existing queen and (k,l) is the position of the next queen i.e. kth row and lth column.

This process require us to backtrack if next queen can't be placed and recheck other options. We can use two function for this. One for placing queen and other for checking whether queen can be placed on kth row and lth column or not .

Algorithm : 

  1. for i=1 to n do step 2
  2. if queen can be placed  
    1. then 
      1. place the queen
      2. if all queen placed then print the placements
      3. else try next row by recursively calling the function
Following is the implementation of this algorithm in C :
  
/**
 *
 * @author VIKASH VIK VIKASHVVERMA
 * 
 */

#include<stdio.h>
int*x;

int place(int k, int i)//this function returns true only and only if two queens can be placed in same row or column
{ int j;
 for(j=1;j<=k-1;j++)
 {
  if(x[j]==i//two queens in same row
  || abs(x[j]-i)==abs(j-k))//two queens in same diagonal
  {
   return 0;
  }
 }
 
 return 1;
}

void nQueen(int k, int n)
{
 int i;
 for( i=1;i<=n;i++)
 {
  if(place(k,i))
  {
   x[k]=i;
   if(k==n)
   {printf("\n");
   for(i=1;i<=n;i++)
   printf("%d\t",x[i]);
   
   }else
   nQueen(k+1,n);
  }
 }
}
void main()
{
 int n;
 printf("Enter value of n : ");
 scanf("%d",&n);
 x=(int*)malloc((n+1)*sizeof(int));
 printf("Possible placements are : ");
 nQueen(1,n);
 
}


Input :
 4
Output :
 Possible placements are :
2 4 1 3
3 1 4 2

Where ith value printed represents ith  row and the value as column of the row.

No comments :

Post a Comment