51. N-Queens
The n-queens puzzle asks you to arrange n chess queens on an n × n board so that no queen threatens another — no two queens may ever share a row, a column, or either diagonal.
Your function receives the integer n and returns every distinct arrangement that works. Encode each arrangement as a list of n strings, one per board row from top to bottom, where 'Q' marks a queen and '.' marks an empty square.
To keep the answer canonical, read each solution as its column sequence — the queen's column in row 0, then row 1, and so on — and return the solutions in increasing lexicographic order of those sequences. A row-by-row search that tries columns from left to right produces exactly this order. If n admits no arrangement at all, return an empty list.
Example 1:
Input: n = 4
Output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
Explanation: The 4×4 board has exactly two safe arrangements. Their column sequences are [1, 3, 0, 2] and [2, 0, 3, 1], so the first board comes first.
Example 2:
Input: n = 1
Output: [["Q"]]
Explanation: A lone queen on a 1×1 board threatens nobody.
Constraints:
- 1 ≤ n ≤ 9
Hints:
Every valid board uses each row exactly once and each column exactly once, so a solution is really a permutation: row i gets some column p[i]. That alone shrinks the search from n² choose n placements to n! candidates.
Place queens one row at a time. A queen at (row, col) is safe if col is unused, row − col has no queen (one diagonal direction), and row + col has no queen (the other). Three hash sets answer all three checks in O(1).
Trying columns in ascending order inside the row-by-row search emits solutions already sorted by column sequence — no sorting pass needed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 4
Expected output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]