N-Queens
Hard
BacktrackingArray
The **n-queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.
Given an integer `n`, return *all distinct solutions* to the n-queens puzzle. Each solution is a board configuration where `"Q"` indicates a queen and `"."` indicates an empty space.
**Example 1:**
```
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
```
**Example 2:**
```
Input: n = 1
Output: [["Q"]]
```
Expected Time Complexity
O(n!)
Expected Space Complexity
O(n²)
Example Test Cases
Example 1
Input:
1
Output:
[["Q"]]
Example 2
Input:
4
Output:
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]