1190: n-皇后问题
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：58
Solved：24
Description
$n−$皇后问题是指将 $n$ 个皇后放在 $n×n$ 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
例如，下面是 $8-$皇后问题中的一种摆法。
现在给定整数 $n$，请你输出所有的满足条件的棋子摆法。
例如，下面是 $8-$皇后问题中的一种摆法。
现在给定整数 $n$，请你输出所有的满足条件的棋子摆法。
Input
共一行，包含整数 $n$。
Output
每个摆法占 $n$ 行，每行输出一个长度为 $n$ 的字符串，用来表示完整的棋盘状态。
其中 * 表示某一个位置的方格状态为空，! 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
具体格式参见输出样例。
其中 * 表示某一个位置的方格状态为空，! 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
具体格式参见输出样例。
Sample Input Copy
4Sample Output Copy
*!**
***!
!***
**!*
**!*
!***
***!
*!**
HINT
数据范围：
对于 $100\%$ 测试点，$2 \le n \le9$。
对于 $100\%$ 测试点，$2 \le n \le9$。