目 录CONTENT

文章目录

843. n-皇后问题

Gz
Gz
2022-07-04 / 0 评论 / 0 点赞 / 339 阅读 / 1,177 字 / 正在检测是否收录...

843. n-皇后问题

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

1_597ec77c49-8-queens.png

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

输入格式

共一行,包含整数 nn。

输出格式

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

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

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

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围

1≤n≤91≤n≤9

输入样例:

4
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
    final static int N = 20;
    static char q[][] = new char[N][N];
    static boolean dg[] = new boolean[N], udg[] = new boolean[N], cor[] = new boolean[N];
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int n = 0;

    static void dfs(int u) throws IOException {
        if (u == n){
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    bw.write(q[i][j]);
                }bw.write("\n");
            }
            bw.write("\n");
            return;
        }

        for (int i = 0; i < n; i++) { // 第u行,第i列是否放皇后
            if (!cor[i] && !dg[u + i] && !udg[n - u + i]){ //判断是否冲突
                q[u][i] = 'Q';
                cor[i] = dg[u + i] = udg[n - u + i] = true;
                dfs(u + 1);
                cor[i] = dg[u + i] = udg[n - u + i] = false;
                q[u][i] = '.';

            }
        }
    }

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                q[i][j] = '.';
            }
        }
        dfs(0);
        bw.flush();
    }
}
0

评论区