A queen on a chessboard attacks every square in its row, in its column, and along both of its diagonals, however far away. You get a whole number n. Return every way to place n queens on an n by n board so that no queen attacks another.

Write each placement as a list of n strings, one per row from top to bottom. Each string has n characters: "Q" for a square with a queen and "." for an empty square.

Return each placement once, in any order. If there is no placement, return an empty list.