N -queen's problem ( or Eight queen's problem ) using backtracking in c

On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in C:
#include<stdio.h>
#include<math.h>
int board[20],count;
int main()
{
  int n,i,j;
  void Queen(int row,int n);
  printf("\nEnter Number of Queen's: ");
  scanf("%d",&n);
  Queen(1,n);//trace using backtrack
  return 0;
}
/* This function is for printing the solution to n-queen's problem */
void print_board(int n)
{
  int i,j;
  printf("\n\nSolution %d : \n\n",++count);
       //number of solution
  for(i=1;i<=n;i++)
  {
   printf("\t%d",i);
  }
  for(i=1;i<=n;i++)
  {
   printf("\n\n%d\t",i);
   for(j=1;j<=n;j++)// for  board
   {
    if(board[i]==j)
     printf("Q\t");//Queen at i,j position
    else
     printf("-\t");// empty slot
   }
  }
}
/*This function is for checking for the conflicts.If there is no conflict for the desired position it returns 1 otherwise it returns 0*/
int place(int row,int column)
{
  int i;
  for(i=1;i<=row-1;i++)
  { //checking for column and diagonal conflicts
   if(board[i] == column)
    return 0;
   else
    if(abs(board[i] - column) == abs(i - row))
     return 0;
  }
  return 1;//no conflicts hence Queen can be placed
}
/* By this function we try the next free slot and check for proper positioning of queen*/
void Queen(int row,int n)
{
  int column;
  for(column=1;column<=n;column++)
  {
   if(place(row,column))
   {
     board[row] = column;//no conflict so place queen
    if(row==n)//dead end
    print_board(n);
      //printing the board configuration
    else  //try next queen with next position
     Queen(row+1,n);
   }
  }
}
output:-
Enter Number of Queen's: 4


Solution 1 :

        1       2       3       4

1       -       Q       -       -

2       -       -       -       Q

3       Q       -       -       -

4       -       -       Q       -

Solution 2 :

        1       2       3       4

1       -       -       Q       -

2       Q       -       -       -

3       -       -       -       Q

4       -       Q       -       -
--------------------------------

0 comments: