Solution for N Queens Problem using Backtracking in C

What is N Queens Problem?

The N Queens problem is:

How can N queens be placed on an NxN chessboard so that no two of them attack each other?

The eight queens puzzle is the problem of placing eight chess queens on an n x n chessboard so that no two queens threaten each other.

Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3.

A possible solution for N Queens problem is:


n queens problem


  •     Place the queens col­umn wise, start from the left most column
  •     If all queens are placed:
    return true and print the solu­tion matrix.
    Try all the rows in the cur­rent column.
  •         Check if queen can be placed here safely if yes mark the cur­rent cell in solu­tion matrix as 1 and try to solve the rest of the prob­lem recursively.
  •         If plac­ing the queen in above step leads to the solu­tion return true.
  •         If plac­ing the queen in above step does not lead to the solu­tion , BACKTRACK, mark the cur­rent cell in solu­tion matrix as 0 and return false.
  •     If all the rows are tried and noth­ing worked, return false and print NO SOLUTION.


C program for N Queens problem using Backtracking:

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:");
 return 0;
//function for printing the solution
void print(int n)
 int i,j;
 printf("\n\nSolution %d:\n\n",++count);
  for(j=1;j<=n;++j) //for nxn board
    printf("\tQ"); //queen at i,j position
    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;
  //checking column and digonal conflicts
   return 0;
    return 0;
 return 1; //no conflicts
//function to check for proper positioning of queen
void queen(int row,int n)
 int 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



N queens problem

Comment below in case you want discuss more about the solution.

Leave a Comment