dsa · hard
N Queens
Place n queens on an n × n board so that no two share a row, a column, or a diagonal. Return every distinct board as a list of n strings of length n. Use "Q" for a queen and "." for an empty square. Each string is one row, top to bottom.
Arguments
n— board size and number of queens to place
The order of the boards does not matter.
Example
n = 4 has two drawings:
.Q.. / ...Q / Q... / ..Q.
and
..Q. / Q... / ...Q / .Q..
n = 1 is a single cell with a queen: [["Q"]].
n = 2 and n = 3 have no valid placement → [].
Constraints
1 <= n <= 9
Examples
Example 1
Input: 4 Expected: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Example 2
Input: 1 Expected: [["Q"]]