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

```
//
// main.cpp
// N Queen
//
// Created by Himanshu on 22/04/22.
//
#include <iostream>
#include <cstdio>
#define N 8
// 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
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 (It’ll work for other values of N also)

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!**).

Like my posts ????

🙂

Already did ????