N-Queens

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' indicates a queen and '.' indicates an empty space.

Examples

Example 1

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation: There are two distinct solutions to the 4-queens puzzle.

Example 2

Input: n = 1

Output: [["Q"]]

Explanation: There is only one solution for a 1×1 board.

Constraints

• 1 <= n <= 9