N-Queens

Problem

Place n queens on an n x n chessboard so that no two queens threaten each other; queens attack along rows, columns, and both diagonals. Return every distinct arrangement. Each arrangement is a list of n strings, one per row, using 'Q' for a queen and '.' for an empty square. Output order does not matter.

• The board size n is between 1 and 10.

Examples

• n = 4 → [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]. Exactly two arrangements exist, mirror images of each other.
• n = 1 → [["Q"]]. A single queen on a single square.
• n = 3 → []. No valid arrangement exists for n = 2 or n = 3.

Hints

1. Every row must contain exactly one queen. So a solution is just a choice of one column per row; you do not need to consider arbitrary square subsets.
2. Placing a queen at (r, c) rules out column c, the diagonal where r - c is constant, and the anti-diagonal where r + c is constant. Can you check those in O(1)?
3. Backtrack row by row, keeping three sets (columns, r - c, r + c); place, recurse, remove.