N Queens Problem in C Using Backtracking

Here you will get program for N queens problem in C using backtracking.

N Queens Problem is a famous puzzle in which n-queens are to be placed on a nxn chess board such that no two queens are in the same row, column or diagonal. In this tutorial I am sharing the C program to find solution for N Queens problem using backtracking. Below animation shows the solution for 8 queens problem using backtracking.

Also Read: C Program for Tower of Hanoi Problem

 

8 Queens Problem Using Backtracking
8 Queens Problem Using Backtracking

 

Program for N Queens Problem in C Using Backtracking

#include<stdio.h>
#include<math.h>

int board[20],count;

int main()
{
 int n,i,j;
 void queen(int row,int n);

 printf(" - N Queens Problem Using Backtracking -");
 printf("\n\nEnter number of Queens:");
 scanf("%d",&n);
 queen(1,n);
 return 0;
}

//function for printing the solution
void print(int n)
{
 int i,j;
 printf("\n\nSolution %d:\n\n",++count);

 for(i=1;i<=n;++i)
  printf("\t%d",i);

 for(i=1;i<=n;++i)
 {
  printf("\n\n%d",i);
  for(j=1;j<=n;++j) //for nxn board
  {
   if(board[i]==j)
    printf("\tQ"); //queen at i,j position
   else
    printf("\t-"); //empty slot
  }
 }
}

/*funtion to check conflicts
If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row,int column)
{
 int i;
 for(i=1;i<=row-1;++i)
 {
  //checking column and digonal conflicts
  if(board[i]==column)
   return 0;
  else
   if(abs(board[i]-column)==abs(i-row))
    return 0;
 }

 return 1; //no conflicts
}

//function to 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 conflicts so place queen
   if(row==n) //dead end
    print(n); //printing the board configuration
   else //try queen with next position
    queen(row+1,n);
  }
 }
}

 

Output

C Program for N Queens Problem Using Backtracking

Comment below if you found anything incorrect in above N queens problem in C.

30 thoughts on “N Queens Problem in C Using Backtracking”

  1. arafat chowdhury

    #include will not declared in the scope fix it then it will work 🙂 thanks again to build up this dashing structure .

  2. Hey Neeraj! can you please explain the code. I have got manual logic of n queen problem but finding code difficult to understand like board[i]=column and other such lines. Does board[i] or board[row] has some value. Please explain, i am a beginner….

  3. I tried but i am not able to understand the logic :-
    if (abs(board[i]-column)==abs(i-row))

    How, it is able to check the column. please explain.

  4. thanks for the code, but I have a doubt.
    consider the first two queens are placed at (row 1, column1) and (row2 ,column 3). now the next queen can not be placed in row 3 and hence the position of 2nd queen is changing from (row2, column3) to (row2 ,column4).
    since, I can not see any code line to decrement the row number. can you please tell me how it is really executing this step???

    1. That’s the basics of backtracking :
      We use a recursive call of the queen() function to compute and verify the next row.
      If a position cannot be found for the next row, the code goes back to where the recursive call was made, and keeps going from there.

      It’s not very clear, i’m sorry, let’s try it that way :
      We’re on row 3. We’re looking for a position for our queen on that row, with those lines :
      —————————–
      if(place(row,column))
      {
      board[row]=column;
      —————————–

      If there’s a valid position, we place the queen, then call the function recursively :
      —————————–
      queen(row+1,n);
      —————————–
      Which is going to do the same thing again, for the next row : row 4.
      If a position isn’t found in this call (for row + 1, which is row 4), the program will abandon that solution, and go back to where it was before, which means it will execute the rest of the code, and that was the loop where we’re incrementing “column” for row 3.. There, it will check again for the next value of column, and if the position is valid, it is then going to try again for row + 1 (row 4), until there is a valid solution there. When it finds one, it is going to call queen() again, with row + 1, which means row 5.

    2. its an recursion algorithm.. when you return it takes you back to the earlier function from where you have called the function. means example : if u r in 4th row means you called place() function in 3th row.. so in case the functions returns the it will take back to 3rd row this how decrement takes place.

  5. saikrishna vadali

    thank you so much bro 🙂 its hard to understand algorithm from textbook….. but u made it simple to understand through this program… thank you once again 🙂

  6. KESANA KARTHIK .

    output not coming:-
    the error i am getting:-
    queen1.c:51:7: warning: implicit declaration of function ‘abs’ [-Wimplicit-function-declaration]
    if(abs(board[i]-column)==abs(i-row))queen1.c:51:7: warning: implicit declaration of function ‘abs’ [-Wimplicit-function-declaration]
    if(abs(board[i]-column)==abs(i-row))

    1. As a rule of thumb the mathematical functions that operate on floating point numbers are in math.h, and the ones that operate on integers are in stdlib.h.
      so including instead of math.h header file can solve the implicit declaration of function abs error.

  7. //Basically we will place queen at a row assuming for our solution all the queens are placed at 1 to row-1 correctly .To clear this condition queens at
    //1 to row-1 are
    //placed such that they do not contradict with queen placed at column vertically or diagonally .Since we are placing board[row]=column so there is no
    //way in hell we can produce a solution such that board[i]=column when i iterates from 1 to row-1.Also for diagonal condition difference b/w i and row &&
    //board[i] and column can’t be equal.Otherwise queen at ith row will kill u.

  8. how is it printing all solutions ??
    how does it store all the solutions?
    its seems it is working on only one solution

  9. Is there any particular formula for finding number of solutions for this problem for a given number of queens??

Leave a Comment

Your email address will not be published. Required fields are marked *