八皇后

问题描述

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

现在给定整数 n，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 n。
输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例：

4

输出样例：

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

思路

与组合问题类似，找到一种能遍历所有情况的方法。
方法一按格子遍历，最大深度为n*n
方法二按行遍历，最大深度为n
可见不同的遍历顺序效果也不尽相同。

注意：在dfs过程中存储中间状态和结果。

方法一

import java.util.*;
public class Main {
    static int n;
    static char[][] g;
    static int[] row, col, dg, udg;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        g = new char[n][n];
        col = new int[n];
        row = new int[n];
        dg = new int[2 * n];
        udg = new int[2 * n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], '.');
        }
        dfs(0, 0, 0);
    }
    static void dfs(int x, int y, int sum) {
        if (y == n) {
            y = 0;
            x++;
        }
        if (x == n) {
            if (sum == n) {
                for (int i = 0; i < n; i++) 
                    System.out.println(g[i]);
                System.out.println();
            }
            return;
        }
        dfs(x, y + 1, sum);
        if (row[x] == 0 && col[y] == 0 && dg[y + x] == 0 && udg[y - x + n] == 0) {
            row[x] = col[y] = dg[y + x] = udg[y - x + n] = 1;
            g[x][y] = 'Q';
            dfs(x, y+1, sum + 1);
            g[x][y] = '.';
            row[x] = col[y] = dg[y + x] = udg[y - x + n] = 0;
        }
    }
}

方法二

import java.util.*;
public class Main {
    static int n;
    static char[][] g;
    static int[] col, dg, udg;
    public static void main(String[] swe) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        g = new char[n][n];
        col = new int[n];
        dg = new int[2 * n];
        udg = new int[2 * n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = '.';
            }
        }
        dfs(0);
    }
    static void dfs(int u) {
        if (u == n) {
            for (int i = 0; i < n; i++) {
                System.out.println(g[i]);
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if (col[i] == 0 && dg[i + u] == 0 && udg[i - u + n] == 0) {
                g[u][i] = 'Q';
                col[i] = 1;
                dg[i + u] = 1;
                udg[i - u + n] = 1;
                dfs(u + 1);
                g[u][i] = '.';
                col[i] = 0;
                dg[i + u] = 0;
                udg[i - u + n] = 0;
            }
        }
    }
}

n皇后.pdf