N Queens

You get a whole number n.

Return every way to place n queens on an n x n chessboard. No queen may attack another. The ways can be in any order.

Two queens attack each other when they share a row, a column or a diagonal.

Write each way as an array of n numbers, one per row. The number at index r is the column of the queen in row r. Columns count from 0.

If there is no way, return an empty array.

Example 1:

Input: n = 6
Output: [[1, 3, 5, 0, 2, 4], [2, 5, 1, 4, 0, 3],
         [3, 0, 4, 1, 5, 2], [4, 2, 0, 5, 3, 1]]
Explanation: A 6 x 6 board has exactly four ways, drawn above.
In the first one, the queen in row 0 is in column 1.
The queen in row 1 is in column 3, and so on.

Example 2:

Input: n = 3
Output: []
Explanation: On a 3 x 3 board, two of the 3 queens always attack each other.
There is no way to place them.

Constraints:

• n is from 1 to 9.