N Queens

The N-Queens puzzle asks you to place n chess queens on an n x n chessboard so that no two queens attack each other. A queen attacks any piece in the same row, the same column, or along either diagonal.

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution should be represented as a list of strings of length n, where 'Q' marks a queen and '.' marks an empty square. (If you only need the count of solutions rather than the boards themselves, the same search works — just increment a counter at each goal instead of recording a board.)

Example 1:

Input:  n = 4
Output: [
  [".Q..", "...Q", "Q...", "..Q."],
  ["..Q.", "Q...", "...Q", ".Q.."]
]
Explanation: There are exactly two distinct solutions for a 4x4 board.

Example 2:

Input:  n = 1
Output: [["Q"]]

Constraints:

• 1 <= n <= 9