The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.
A queen can move any number of steps in any direction (row, column, or diagonal). The only constraint is that it can't change its direction while it's moving.
Solutions
Method 1: Backtracking
One thing that is clear by looking at the queen's movement is that no two queens can be in the same row or column.
That allows us to place only one queen in each row and each column.
The idea is to place one queen in each column, starting from the leftmost column.
When we place a queen in a column, we check for clashes (isSafe(..)) with already placed queens.
While we are placing one queen in one column and that too, from left to right, we need to check for only three conditions in the isSafe() method:
1) Examine the current row on the left side.
2) Examine the top left diagonal.
3) Look down the bottom left diagonal.
If the queen is safe, try recursively placing the remaining queens (nQueenRecur (.., column + 1,..)) from the next column.
If the remaining queens do not find a place due to clashes, then we backtrack and return false.
If all queens are placed, return true.
Complexity
The time complexity of this solution is O(N!) and space complexity is O(N^2).