# N Queen Problem Analysis

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

For a larger N, this problem couldn’t be solved in polynomial time. So, it is an **NP-Complete problem**. However, this problem could be solved by backtracking in *non-polynomial *time for a smaller N.

**Backtracking** is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Solution of **N Queen problem **using backtracking checks for all possible arrangements of **N Queens **on the chessboard. And then checks for the validity of the solution. The code for the problem is below:

```
/* C/C++ program to solve N Queen Problem using
backtracking */
#define N 4
#include <stdbool.h>
#include <stdio.h>
/* This function prints the solution */
void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
}
/* A function to check if a queen can
be placed on board[row][col]. */
bool check(int board[N][N], int row, int col) {
int i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row][i])
return false;
/* Check upper diagonal on left side */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
/* Check lower diagonal on left side */
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
/* A recursive function to solve N
Queen problem */
bool solveUtil(int board[N][N], int col)
{
/* base case: If all queens are placed
then return true */
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
/* Check if the queen can be placed on
board[i][col] */
if (check(board, i, col)) {
board[i][col] = 1;
/* recur to place rest of the queens */
if (solveUtil(board, col + 1))
return true;
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
int main() {
int board[N][N] = {0};
if (solveUtil(board, 0) == false) {
printf("Solution does not exist");
} else {
printf("Solution:\n");
printSolution(board);
}
return 0;
}
```

Here is a working example – N Queen solution. (Try changing the value of N)

Now number of possible arrangements of N Queens on** N x N** chessboard is ** N!**, given you are

*skipping row or column, already having a queen placed*.

So average and worst case complexity of the solution is

**O(N!)**(since, you are checking all the possible solutions i.e.

*N^N**arrangements). The best case occurs if you find your solution before exploiting all possible arrangements. This depends on your implementation.*

**Also there could be more than one solution for this problem, but we stop as soon as we find one feasible solution to the problem.**And if you need all the possible solutions, the best, average and worst case complexity remains O**(N!**).

P.S. Check out our new tool on our website for intelligent and cool quotes & captions for your social media as well as blogs – CAPTAGRAM

Like my posts ????

🙂

Already did ????