N-Queens
Hard · backtracking
A queen in chess attacks every square in her own row, in her own column, and along both diagonals.
You have an n by n board and n queens. Place all n queens on the board, one per square, so that no queen attacks another. Two placements are different if at least one queen stands on a different square.
Return the number of different valid placements. If there is none, return 0.
Examples
Example 1
Input: n = 4
Output: 2
Two placements work on a 4 by 4 board. They are mirror images of each other.
Example 2
Input: n = 1
Output: 1
A single queen on a single square attacks nothing.
Example 3
Input: n = 3
Output: 0
On a 3 by 3 board, any placement of three queens leaves two of them attacking each other.
Constraints
- 1 <= n <= 10