You are given an integer n representing the size of a chessboard (n × n). You need to place n queens on the board so that no two queens attack each other.
A queen can attack another piece if they are on the same row, same column, or same diagonal.
Return all distinct valid configurations of the board.
n
strings.
n
and represents one row of the board.
'Q'
represents a queen, and
'.'
represents an empty square.
Two configurations are considered different if they differ in at least one row string.
You may assume:
1 ≤ n ≤ 9
.
Example
Input:
One valid output (order of configurations and rows does not matter):
In each configuration above, there are 4 queens on the board, and no two queens attack each other.