843. n-皇后问题(dfs+输出各种情况)

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

843. n-皇后问题(dfs+输出各种情况)

现在给定整数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); } }

 

 

上一篇:843 N-皇后


下一篇:AcWing 843. n-皇后问题