Sunday, February 6, 2011

N Queen Problem


OBJECTIVE: c Implementation of N-Queen problem.
THEORY: The concept of N queens problem is that we need to place N queens in N x N matrix where in which the following conditions should apply.
1. No two queens should be placed in the same row
2. No two queens should be placed in the same column
3. No two queens should be placed in the same diagonal

PROGRAM:
#include <stdio.h>
#include<conio.h>
define TRUE 1
define FALSE 0
int *board;
int main()
{
board=(int*)calloc(8+1,sizeof(int));
board++;
int col;
int queens=2;//example from userinput
for(col=1;col<=8;col++)
     placeQueens(1,col,queens);
}
void placeQueens(int row,int col,int queens)
{
       int i;
        for(i=1;i<row;i++)
       {
        if((board[i] == col) || ((row+col)==(i+board[i]))||((row-col)==(i-board[i])))
        {
            check= FALSE;
        }
        else
         check=TRUE;
     }
      if(check==TRUE)
       {
         board[row]=col;  
  if(row==8)
        {
            for(i=1;i<=queens;i++)
            printf("(%d,%d)",i,board[i]);              
          printf("\n");
        }          
        else
        {
            for(i=1;i<=8;i++)
            placeQueens(row+1,i);
        }
    }    
}

No comments:

Post a Comment