In chess, a queen can capture any piece that stands in her row, in her column, or on either diagonal line through her square. You have a square board with n rows and n columns, and you have n queens.
Place all n queens on the board so that no queen can capture another one. Find every different arrangement that works. Return the arrangements in any order.
Draw each arrangement as n strings, one string for each row from top to bottom. In a string, 'Q' marks a queen and '.' marks an empty square.
Examples
Example 1:
Input: n = 2
Output: []
Explanation: On a 2 x 2 board, any two squares share a row, a column or a diagonal. So no safe arrangement exists, and the list is empty.
Example 2:
Input: n = 3
Output: []
Explanation: Three queens cannot be kept safe on a 3 x 3 board either, so the list is empty.
Example 3:
Input: n = 6
Output: [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]
Explanation: A 6 x 6 board has exactly four safe arrangements. Each one is a list of 6 strings.