题目内容

国际象棋中，皇后可以沿行、列或两条对角线方向攻击。所谓 N 皇后问题，目标是：在一个 $n \times n$ 的棋盘上放置 $n$ 枚皇后，使得任意两枚皇后都不在同一行、同一列或同一斜线上。给定整数 $n$，请找出所有互不相同的可行摆放方式。每个摆放方式用一个长度为 $n$ 的字符串列表表示：第 $i$ 个字符串对应于棋盘从上到下的第 $i$ 行，字符串中字符 Q 表示该格放置皇后，字符 . 表示该格为空。返回所有这样的棋盘布局。

约束条件：整数 $n$ 满足 $1 \le n \le 9$。

输入描述

输入包含一个参数：一个整数 $n$，表示棋盘边长以及皇后数量。

输出描述

返回一个列表，其中每个元素代表一种不同的解法。每个解法本身是一个长度为 $n$ 的字符串列表，按棋盘从上到下的顺序给出每一行，Q 表示皇后，. 表示空位。解法之间的顺序不限。

样例1

输入

6

输出

.Q....
...Q..
.....Q
Q.....
..Q...
....Q.

..Q...
.....Q
.Q....
....Q.
Q.....
...Q..

...Q..
Q.....
....Q.
.Q....
.....Q
..Q...

....Q.
..Q...
Q.....
.....Q
...Q..
.Q....

说明

对于 $n=6$，共有 4 种不同的可行摆放。输出中每 6 行表示一个完整棋盘，不同棋盘之间用空行分隔。

按输出顺序，四种摆放的皇后所在列（列号从 0 开始）依次为：

• [1,3,5,0,2,4]
• [2,5,1,4,0,3]
• [3,0,4,1,5,2]
• [4,2,0,5,3,1]

以第一组为例，皇后位置为 $(0,1),(1,3),(2,5),(3,0),(4,2),(5,4)$。这些位置没有相同的行号或列号，任意两点的行号差与列号差也不满足 $|r_i-r_j|=|c_i-c_j|$，因此不会相互攻击。其余三组同理。

样例2

输入

2

输出

说明

在 $2 \times 2$ 棋盘上，两个皇后必须分别放在两行。

如果第一行皇后放在第 0 列，第二行只能选择第 1 列，但 $(0,0)$ 与 $(1,1)$ 位于同一条对角线上；如果第一行皇后放在第 1 列，第二行只能选择第 0 列，$(0,1)$ 与 $(1,0)$ 也位于同一条对角线上。

因此不存在合法摆放，输出为空。