85. N-Queens

Hard · Backtracking

The n-queens puzzle asks you to place n chess queens on an n×n board so that no two queens attack each other — no two share a row, column, or diagonal.

The input is a single integer n. Return the number of distinct ways the n queens can be placed.

Examples

Example 1
Input: 4
Output: 2
Explanation: On a 4×4 board there are exactly 2 valid arrangements.
Example 2
Input: 1
Output: 1
Explanation: On a 1×1 board the single queen trivially has 1 placement.

Constraints