The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.
Given an integer N, return all distinct solutions to the N-queens puzzle. You may return the answer in any order.
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, we have two choices:
1) Place the queen in the safe row of current column and try recursively placing the remaining queens (nQueenRecur (.., column + 1,..)) from the next column.
2) Look for any other safe row in the current column.
If all queens are placed for any of the recursive calls, add positions to the final answer.
Complexity
The time complexity of this solution is O(N!) and space complexity is O(N^2).