问题引入

百度百科：八皇后问题

简述：

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

这是一个典型的DFS回溯算法应用题，通过解这个题可以明确DFS算法的思路和步骤。

思路

由问题知道每行每列每条对角线都只能有一个皇后，所以需要用数组来记录每种条件的使用情况。其中每行的使用情况可以作为参数放在方法中，并为结束条件提供便利。

DFS算法基本步骤

要注意递归结束条件和回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void dfs(){
    //1.结束条件
    if (...) {return;}
    //2.遍历所有可能
    fori(){
        if(递归条件){
            //2.1递归前的操作(改变条件信息)
            ...
            dfs();
            //2.2回溯（也叫恢复现场）
            ...
        }
    }
    //3.其他特殊操作
}

注意

值得注意的是对角线的维护数组的创建思路

主对角线：row - col规律如图

image-20220321202855992

次对角线：row + col规律

image-20220321203244507

主次对角线各14条，主对角线main_diagonal[row - col + 7] 即是对应某条主对角线的使用状态，同理次对角线为sec_diagonal[row + col]

打印所有92种排列的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public class 八皇后问题 {
    static final int EI = 8, FT = 15;
    static int[][] map = new int[EI][EI];
    static boolean[] col = new boolean[EI];
    static boolean[] main_diagonal = new boolean[FT];
    static boolean[] sec_diagonal = new boolean[FT];
    static int result = 0;

    static void dfs(int n){
        if (n >= EI){
            soutMap();
            return;
        }
        for (int i = 0; i < EI; i++) {
            if (check(n , i)){
                map[n][i] = 1;
                act(n, i, true);
                dfs(n + 1);
                //回溯
                act(n, i, false);
                map[n][i] = 0;
            }
        }
    }
    static boolean check(int n, int i){
        return !col[i] && !main_diagonal[n - i + EI - 1] && !sec_diagonal[n + i];
    }
    static void act(int n, int i, boolean rel){
        col[i] = rel;
        main_diagonal[n - i + EI - 1] = rel;
        sec_diagonal[n + i] = rel;
    }
    static void soutMap(){
        result++;
        for (int[] i : map){
            for (int j : i){
                if(j == 1) System.out.print("*" + " ");
                else System.out.print("0" + " ");
            }
            System.out.println();
        }
        System.out.println("++++++++++++++++++++");
    }

    public static void main(String[] args) {
        dfs(0);
        System.out.println("总共有" + result + "种排列方式！");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//打印结果后面部分
......
++++++++++++++++++++
0 0 0 0 0 0 0 * 
0 0 * 0 0 0 0 0 
* 0 0 0 0 0 0 0 
0 0 0 0 0 * 0 0 
0 * 0 0 0 0 0 0 
0 0 0 0 * 0 0 0 
0 0 0 0 0 0 * 0 
0 0 0 * 0 0 0 0 
++++++++++++++++++++
0 0 0 0 0 0 0 * 
0 0 0 * 0 0 0 0 
* 0 0 0 0 0 0 0 
0 0 * 0 0 0 0 0 
0 0 0 0 0 * 0 0 
0 * 0 0 0 0 0 0 
0 0 0 0 0 0 * 0 
0 0 0 0 * 0 0 0 
++++++++++++++++++++
总共有92种排列方式！

总结

对于其他由此问题引出的皇后问题都可以参考此问题代码求解，只需更改特定方法或者参数即可。