Description

在一個 $N \times N$ 的西洋棋棋盤上有 $N$ 個皇后，每個皇后都佔據一個格子而攻擊範圍同標準西洋棋規則，國王希望他們互相不能攻擊，請列出所有可能的皇后擺放位置。

皇后攻擊範圍如下：

Input Format

輸入只有一行，包含一個正整數 $1 \leq N \leq 12$ 代表棋盤的大小。

Output Format

輸出總共有 $(N + 1) \cdot S$ 行，其中 $S$ 是皇后擺放方式的數量。

一個皇后擺放方式可以表示成一個長度 $N$ 的序列 $(A_{1}, A_{2}, \dots, A_{N})$ ，代表第 $i$ 個橫列的皇后放在第 $A_{i}$ 直行。這 $S$ 個解請照序列的字典序由小到大輸出，換句話說，第一橫列的皇后放在第一直行的解會優先輸出，而第一橫列的皇后放在最後一直行的解則會最後輸出。

對於每一個皇后擺放方式，輸出 $(N + 1)$ 行長度為 $N$ 的字串，如果棋盤的第 $i$ 橫列第 $j$ 直行是一個皇后，則在第 $i$ 行的第 $j$ 個字元輸出 Q，否則輸出 *，最後一行則是一個空行。

請注意如果沒有合法的皇后擺放方式，輸出將會是空的，另外，如果有解的話，最後一行一定是空行（所以輸出格式比較方便 :p）。

Sample Input 1

Sample Output 1

*Q**
***Q
Q***
**Q*

**Q*
Q***
***Q
*Q**

Sample Input 2

Sample Output 2

Hints

Problem Source

經典題

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~13	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	1 2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2

691 . K皇后

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Hints

Problem Source

Subtasks

Testdata and Limits

691 . K皇后

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags Show solution-related tags

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Hints

Problem Source

Subtasks

Testdata and Limits

Tags