Introduction
The Nqueen problem is one of the most popular problems to get an idea of how backtracking works. Backtracking in one of the most popular concepts that is asked about in the interviews for big tech companies as well. The Nqueen problem is one of the most common and practical examples to understand Backtracking.
Also see, Data Structures
Please try to solve this problem on your own before moving on to further discussion here.
Problem Statement
You are given an integer N. For a given N x N chessboard, find a way to place 'N' queens such that no queen can attack any other queen on the chessboard.
A queen can be attacked when it lies in the same row, column, or the same diagonal as any of the other queens. You have to print one such configuration.
Print a binary matrix as output that has 1s for the cells where queens are placed.
Backtracking
Cells that can be attacked by a queen is shown below 
Let’s take an example to understand the requirement.
Say, N=4. Now, we will try to place the 4 queens such that each of them is safe from every other queen.
In this figure, the red cross mark represents the cells that the queens can attack.
Observe that with this arrangement, we can only place 3 queens, and the 4th queen can't be placed as any of the positions left is safe. So, this is not the desired configuration.
Let’s try to place the queens in some other way 
Hence, the valid configuration is 
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
Note: There can be more than one such valid configuration. In this problem, our goal is just to print one of those.
The key idea is that no two queens can be placed in:
 Same Row
 Same Column

Same Diagonal
There are N rows, so we will place one queen in each row(as no two queens can be in the same column) such that they all are safe from each other.
We will use backtracking to solve the problem. It is a recursive approach in which we place the queen at a safe position and then recur for the remaining queens. If at any step the number of queens to be placed is not zero and there are no safe cells left, then we change the position of the previously placed queen and try another safe position.
Let’s see backtracking the approach step by step 
Check out Backtracking and Recursion
 Start with the first row.
 Check the number of queens placed. If it is N, then return true.

Check all the columns for the current row one by one.
 If the cell [row, column] is safe then mark this cell and recursively call the function for the remaining queens to find if it leads to the solution.
If it leads to the solution, return true, else unmark the cell [row, column] ( that is, backtrack) and check for the next column.
 If the cell [row, column] is not safe, skip the current column and check for the next one.
 If none of the cells in the current row is safe, then return false.
C++ Implementation
/*C++ code to solve N queen problem by backtracking*/
#include <bits/stdc++.h>
using namespace std;
/*function to check if a cell[i][j] is safe from attack of other queens*/
bool isSafe(int i, int j, int board[4][4], int N)
{
int k, l;
// checking for column j
for (k = 0; k <= i  1; k++)
{
if (board[k][j] == 1)
return 0;
}
// checking upper right diagonal
k = i  1;
l = j + 1;
while (k >= 0 && l < N)
{
if (board[k][l] == 1)
return 0;
k = k + 1;
l = l + 1;
}
// checking upper left diagonal
k = i  1;
l = j  1;
while (k >= 0 && l >= 0)
{
if (board[k][l] == 1)
return 0;
k = k  1;
l = l  1;
}
return 1; //the cell[i][j] is safe
}
int n_queen(int row, int numberOfqueens, int N, int board[4][4])
{
if (numberOfqueens == 0)
return 1;
int j;
for (j = 0; j < N; j++)
{
if (isSafe(row, j, board, N))
{
board[row][j] = 1;
if (n_queen(row + 1, numberOfqueens  1, N, board))
return 1;
board[row][j] = 0; //backtracking
}
}
return 0;
}
int main()
{
int board[4][4];
int i, j;
for (i = 0; i < 4; i++)
{
for (j = 0; j < 4; j++)
board[i][j] = 0;
}
n_queen(0, 4, 4, board);
//printing the board
for (i = 0; i < 4; i++)
{
for (j = 0; j < 4; j++)
cout << board[i][j] << "\t";
cout << endl;
}
return 0;
}
Output
0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 
Time Complexity  O(N!)
For the first row, we check N columns; for the second row, we check the N  1 column and so on. Hence, the time complexity will be N * (N1) * (N2) …. i.e. O(N!)
Space Complexity  O(N^2)
O(N^2), where ‘N’ is the number of queens.
We are using a 2D array of size N rows and N columns, and also, because of Recursion, the recursive stack will have a linear space here. So, the overall space complexity will be O(N^2).
Read More  Time Complexity of Sorting Algorithms