# 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:

### Algorithm:

•     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.
Else
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:

```#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