Description

The N-Queens problem is to place n queens on an n × n chessboard such that no two queens attack each other.

Return all distinct solutions to the N-Queens puzzle. Each solution contains a board configuration represented as an array of strings.

Input format:

• Line 1: Integer n

Output format:

Print a JSON array of solutions. Each solution is an array of strings.

Example:

[
  [".Q..","...Q","Q...","..Q."],
  ["..Q.","Q...","...Q",".Q.."]
]
          

Note:

Order of solutions does not matter. Print only the final result.