N-Queens

Rotate String

Pseudo-Palindromic Paths in a Binary Tree

Return all valid N-Queens boards in deterministic DFS placement order.

Given an integer `n`, return all distinct solutions to placing `n` non-attacking queens on an `n x n` chessboard. Each solution should be represented as an array of `n` strings, where each string has length `n`, `'Q'` marks a queen, and `'.'` marks an empty square.

For this question, keep the output deterministic: list boards in the natural depth-first search order created by placing queens row by row, and at each row trying columns from left to right (column `0`, then `1`, then `2`, and so on). When a placement leads to a full valid board, record it immediately; that DFS/backtracking discovery order is the required output order.

**Input / output**
- Input: `n: int`
- Output: `string[][]` in DFS order

## Example
```json
Input: {"n":4}
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
```

## More examples
1. `n = 1` returns `[["Q"]]`.
2. `n = 2` returns `[]`.

## Constraints
- `1 <= n <= 9`

## Follow-up
How would you count the number of valid boards without constructing every board string, and why is that usually faster?

This is classic backtracking: place one queen per row, reject any column or diagonal conflict immediately, and let the recursion tree enumerate solutions in deterministic row-major DFS order.

Recognize the Pattern

Track three conflict sets or boolean arrays: used columns, used main diagonals (`row - col`), and used anti-diagonals (`row + col`). For each row, try columns from `0` to `n - 1`; every valid placement recurses to the next row, and every complete placement becomes one output board.

Build the Algorithm

Handle the trivial `n = 1` board, remember that `n = 2` and `n = 3` have no solutions, and be careful to copy the constructed board when a solution is found so later backtracking does not mutate saved answers.

Check Edge Cases

Time: `O(n!)` in the classic backtracking worst case. Space: `O(n^2)` counting the output boards plus `O(n)` recursion state and the current placement arrays.