n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数n。

输出格式

每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。

其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

数据范围

1≤n≤91≤n≤9

输入样例：

4

输出样例：

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

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


代码：

import java.util.Scanner;

public class Main{
        static int n;
        static final int N=10;
        static int a[]=new int[N];
        static char map[][]=new char[N][N];
        static boolean check(int t){
                for(int i=0;i<t;i++)
                    if(a[i]==a[t] || Math.abs(i-t)==Math.abs(a[i]-a[t]))
                        return false;
                return true;
        }
        static void dfs(int t){
                       if(t==n){
　　　　　　　　　　　　　　　　　　　//因为开的字符数组大小为N，实际输出可不是N，所以两重循环输出
                                for(int i=0;i<n;i++) {
                                    for(int j=0;j<n;j++)
                                        System.out.print(map[i][j]);
                                    System.out.println();
                                }
                                System.out.println();
                       }
                       for(int i=0;i<n;i++){
                                 a[t]=i;
                                 if(check(t)) {
                                     map[t][i]='Q';
                                     dfs(t+1);
                                     map[t][i]='.';
                                 }
                       }
        }
        public static void main(String[] args) {
                Scanner scan=new Scanner(System.in);
                n=scan.nextInt();
                for(int i=0;i<n;i++)
                    for(int j=0;j<n;j++)
                        map[i][j]='.';
                dfs(0);
        }
}