A chess queen attacks every square in its own row, its own column and both of its diagonals, however far away. Put n queens on an n × n board so that no two of them attack each other: no two share a row, a column or a diagonal.
Return every such placement. Write each board as n strings, one per row from top to bottom, where "Q" is a queen and "." is an empty square. You may list the boards in any order, but each board's rows must stay in top-to-bottom order. If there is no placement, return an empty list.
A 6 × 6 board has exactly four placements. In the one drawn, the queens sit in columns 1, 3, 5, 0, 2, 4 going down the rows: every column is used once, and no two queens are on a shared diagonal.
[]
Whichever square the top row's queen takes, the middle row has at most one square it doesn't attack, and the bottom row is then left with none. Three queens never fit.
Constraints
1 <= n <= 9Each row holds exactly one queen, so place them row by row: for the current row, try each column no earlier queen attacks, and back up when a row has no safe column left (backtracking).
6