封面画师：Nengoro(ネんごろぅ)     封面ID：68874514

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

1. 基本含义

回溯（Back Tracking）：可以理解为通过选择不同的岔路口来通往不同的目的地。

每一步都选择从一条路出发，能进则进，不能进则退回上一步（回溯），然后换一条路尝试。

树、图的深度优先搜索（DFS）就是典型的回溯应用。

二叉树前序遍历

不难看出， 回溯 很适合使用 递归 ！

2. 八皇后问题

2.1 问题描述

八皇后（Eight Queens）问题是一个古老而著名的问题。

讲述的是：在 8 x 8 的国际象棋上摆放八个皇后，使其不能互相攻击（任意两个皇后不能处于同一行、同一列或者同一直线上），请问有多少种摆法？

皇后的攻击范围与摆法图示：

皇后的攻击范围与摆法图示

八皇后问题的一种解法：

八皇后的一种解法

2.2 解决思路

思路一：暴力出奇迹

从 64 个格子中选取任意 8 个格子摆放皇后，检查每一种摆法的可行性。

大概一共需要 4.4×1094.4 \times 10^9 种摆法 （使用数学中排列组合进行计算）：

Anm =n(n−1)⋯(n−m+1) =n!(n−m)!Cnm =Anmm!=n!m!(n−m)!=Cnn−m\begin{aligned} A_{n}^{m} \ &= n(n - 1) \cdots (n - m + 1) \ = \frac{n!}{(n - m)!} \\ C_{n}^{m} \ & = \frac{A_{n}^{m}}{m!} = \frac{n!}{m!(n - m)!} = C_{n}^{n - m} \end{aligned}

思路二：根据题意减少暴力程度

根据皇后的攻击范围，每一行只能摆放一个皇后，所以共有 888^8 种摆法（16777216 种），检查每一种摆法的可行性。

虽然相比于第一种削减了不少摆放次数，但是摆放次数依然很多。

暴力求解法在计算时使用了非常非常多的摆法，那有没有一种好的方法可以减少摆放次数？

那当然是有的，方法就是本文的标题 —— 回溯！ 😂

在解决八皇后问题之前，缩小数据规模，以 四皇后问题 出发。👇

2.3 四皇后 - 回溯法

下图是一副 4×44 \times 4 的棋盘，棋盘中会有不同的颜色：

  • 蓝色： 可摆放
  • 绿色： 已摆放
  • 黑色： 不可摆放
  • 红色箭头： 回溯

四皇后回溯法图解：

四皇后回溯法图解

剪枝

使用回溯法解决四皇后问题时，在 4×44 \times 4 棋盘中的第一行放置一个棋子，然后在第二行放置第二个棋子，同样第三行、第四行也可以放置一个棋子。

每一行虽然都有 4 个位置，但棋子并不是每个位置都可以摆放。

这样就涉及到一个概念 —— 剪枝（Pruning ），合理的剪枝可以进一步缩小计算次数。

如果在 4×44 \times 4 棋盘的第一个位置放置第一个棋子后，需要在第二行放置第二个棋子，这个棋子有四种摆放方式，但根据皇后棋子的攻击范围，可以将摆放位置范围缩小。

四皇后问题第一步剪枝处理

同样，第三个、第四个棋子能够摆放的位置的范围也可以根据这个方式进行缩小。

那么对于八皇后来说，应该怎么用回溯法来解决呢？

2.4 八皇后 - 回溯法

八皇后回溯法图解

跟四皇后的解题思路一样，先在棋盘的第一行选取一个位置摆放皇后棋子，然后在第二行中符合条件的位置摆放棋子（使用剪枝推断出合理的位置），以此类推。

如果棋盘上摆放的皇后棋子数量还没有到 8 个，但是棋盘上已经没有合适的位置能够摆放皇后棋子了，那么就将上一步摆放的皇后棋子撤销，在那一行另外选取一个合适的位置进行摆放。

如果那一个行能够摆放皇后棋子的位置都已经摆放过了，但是棋盘上皇后棋子的数量始终不能达到 8 个，那么进一步撤销这一行与上一行摆放的皇后棋子，在上一行选取一个合适的位置摆放皇后棋子，重复这个方式，直到求解出八皇后问题。

八皇后回溯法-1

八皇后回溯法-2

上一步中棋盘的皇后棋子数量没有达到 8 ，且最后摆放皇后棋子的那一行能够进行摆放的两个位置都已尝试，那么回退两行，再次进行摆放尝试：

八皇后回溯法-3

3. 编码实现

3.1 初步实现

成员变量

为了方便起见，在编写八皇后的实现代码时，可以设置两个成员变量。

一个名为 cols 的整型数组，在创建时不指定数组长度，使用时给这个数组指定长度。数组的索引是行号，对应的元素是列号，比如 cols[4] = 5 表示第四行第五列放置了一个皇后。

另一个名为 ways 的整型变量，用于表示 N 皇后问题中有多少种摆法。比如 4 皇后问题中，有 2 种摆法，最终 ways 的值就是 2。

方法构成

主要的方法有四个：

  1. placeQueens(int n) ：N 皇后问题的主方法，调用其他方法并打印出有多少种摆法。
  2. place(int row) ：从第 row 行开始摆放皇后棋子，内部进行的递归调用。这个递归调用不仅实现了在放置好皇后棋子后自动移动到下一行进行摆放，还实现了回溯。
  3. isValid(int row, int col) ：判断第 row 行 第 col 列是否可以摆放皇后，在方法 place() 内部进行调用。 实现时需要着重理解数组 cols[] 的含义以及如何判断选中格子所在的斜线、列上已有皇后。
  4. show() ：打印皇后棋子摆放位置，摆放皇后的位置输出 1 ，未摆放皇后棋子的位置输出 0，该方法在方法 place() 内部调用。

代码实现

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * @author 默烦
 * 2020/9/12
 */
@SuppressWarnings("all")
public class Queens {

    public static void main(String[] args) {
        new Queens().placeQueens(4);
    }

    /**
     * 数组索引是行号，数组元素是列号
     * 比如 cols[4] = 5 表示第四行第五列放置了一个皇后
     */
    int[] cols;

    /**
     * 摆法
     */
    int ways;

    void placeQueens(int n) {
        if (n < 1) return;
        cols = new int[n];
        place(0);
        System.out.println(n + "皇后一共有" + ways + "种摆法");
    }

    /**
     * 从第 row 行开始摆放皇后棋子
     *
     * @param row 行号
     */
    void place(int row) {
        if (row == cols.length) {
            ways++;
            show();
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            if (isValid(row, col)) {
                // 在第 row 行第 col 列摆放一个皇后
                cols[row] = col;
                // 摆放好一个棋子后去下一行摆放棋子
                place(row + 1);
                // 因为上一步的递归调用，其实回溯也完成了
            }
        }
    }

    /**
     * 判断第 row 行 第 col 列是否可以摆放皇后
     *
     * @param row 行号
     * @param col 列号
     */
    boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 第 col 列已有皇后
            if (cols[i] == col) {
                System.out.println("[" + row + "][" + col + "]= false");
                return false;
            }
            // 选中格子的斜线上已有皇后
            if (row - i == Math.abs(col - cols[i])) {
                System.out.println("[" + row + "][" + col + "]= false");
                return false;
            }
        }
        System.out.println("[" + row + "][" + col + "]= true");
        return true;
    }

    void show() {
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if (cols[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("------------------------");
    }
}

实现细节：

  • place() 方法中，递归调用 place() 方法后，为什么没有重置 cols 数组的值？

因为无效的旧值会被覆盖，并且在计算某个位置的斜线上是否有棋子时，只计算斜线的行号小于当前位置行号的斜线位置。这在后文的优化中也会讲到。

  • isValid() 方法中，为什么通过判断 row - i 的值和 Math.abs(col - cols[i]) 的值是否相等就能判断选中格子的斜线上是否有皇后棋子？

cols[m] = n 表示第 m 行第 n 列有值，如果斜线上有值，那么那个位置横、纵坐标到当前节点的 距离 相等。除此之外，这里的判断使用减法，表示只计算当前位置所处斜线的行号小于当前行号的斜线位置，忽略大于当前行号的斜线位置，因为那可能是上一轮的计算。

输出测试

先告知结论， 四皇后问题共有 2 种摆法，八皇后问题中有 92 种摆法，打印结果如下：

四皇后问题：

四皇后问题打印结果

八皇后问题：

八皇后问题部分打印结果

3.2 优化成员变量

在编码解决八皇后问题时，有这样一个方法 boolean isValid(int row, int col) ，它可以用来判断第 row 行第 col 列是否可以摆放皇后。这个方法的内部实现使用了 for 循环，就是说针对每个棋盘上每个格子都要进行相同的判断。

但显然并不是所有格子都需要进行相同的判断，重复的判断会降低执行效率。

因此，可以对 isValid() 方法进行优化！ 😉

优化方法很简单，舍弃原来的整型数组成员变量 cols，使用以下成员变量：

  1. boolean[] cols：标记某一列是否有皇后棋子
  2. boolean[] leftTop：标记着某一对角线是否有皇后（左上角 --> 当前位置）
  3. boolean[] rightTop：标记着某一对角线是否有皇后（右上角 --> 当前位置）

第一个成员变量很好理解，比如 cols[1] = true 就表示第一列存在皇后棋子，那后两个成员变量应该怎么表示斜线上有皇后棋子呢？👇

八皇后优化对角线索引规律

rowrow 表示行号，colcol 表示列号：

  • 左上角 --> 当前位置的对角线索引：row−col+7row - col + 7（7 表示列长度减一），即 row−colrow - col 为定值，且各不相同，这个值有正有负，可以加上列长度减一用于对齐零点。对于八皇后问题有：

    row−col+7∈[0,14]row - col + 7 \in [0, 14]

  • 右上角 --> 当前位置的对角线索引：row+colrow + col，即 row+colrow + col 为定值，且各不相同。对于八皇后问题有：

    row+col∈[0,14]row + col \in [0, 14]

八皇后优化对角线索引规律

编码优化

引入上面三个成员变量后， show() 的实现将无法完成，因为成员变量 cols 数组的值一定全为 true，无法表达皇后棋子在哪一个格子。如果硬要输出摆放方式，可以再引入一个成员变量，这个成员变量和未优化代码中的整型数组 cols 的作用一样，比如叫 queens：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
 * @author 默烦
 * 2020/9/12
 */
@SuppressWarnings("all")
public class Queens2 {

    public static void main(String[] args) {
        new Queens2().placeQueens(4);
    }

    /**
     * 数组索引是行号，数组元素是列号
     */
    int[] queens;

    /**
     * 标记着某一列是否有皇后
     */
    boolean[] cols;

    /**
     * 标记着某一对角线是否有皇后（左上角 --> 当前位置）
     */
    boolean[] leftTop;

    /**
     * 标记着某一对角线是否有皇后（右上角 --> 当前位置）
     */
    boolean[] rightTop;

    /**
     * 摆法
     */
    int ways;

    void placeQueens(int n) {
        if (n < 1) return;
        queens = new int[n];
        cols = new boolean[n];
        // n * n 的棋盘上，135° 方向的斜线条数为 (n << 1) - 1
        leftTop = new boolean[(n << 1) - 1];
        // n * n 的棋盘上，45° 方向的斜线条数为 (n << 1) - 1
        rightTop = new boolean[leftTop.length];
        place(0);
        System.out.println(n + "皇后一共有" + ways + "种摆法");
    }

    /**
     * 从第 row 行开始摆放皇后棋子
     *
     * @param row 行号
     */
    void place(int row) {
        if (row == cols.length) {
            ways++;
            show();
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            if (cols[col]) continue;
            int ltIndex = row - col + cols.length - 1;
            if (leftTop[ltIndex]) continue;
            int rtIndex = row + col;
            if (rightTop[rtIndex]) continue;

            queens[row] = col;
            // 在对应的位置摆放一个皇后
            cols[col] = true;
            leftTop[ltIndex] = true;
            rightTop[rtIndex] = true;
            place(row + 1);
            // 回溯时重置布尔值
            cols[col] = false;
            leftTop[ltIndex] = false;
            rightTop[rtIndex] = false;
        }
    }

    void show() {
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("------------------------");
    }
}

数据复原

引入了三个布尔类型数组进行递归调用后，需要重置这三个数组的值。

愿意很简单，为什么需要回溯？

显然是因为当前的选择不正确才需要回溯，既然当前选择不正确，在尝试下一种选择前，就需要撤销上一次选择时进行的操作（布尔类型的值“非黑即白”）。

那为什么最开始未进行优化时不用复原呢？

最开始的实现方法使用了一个整型数组 cols，该数组的索引表示行号，数组元素表示列号，比如 cols[4] = 5 表示第四行第五列放置了一个皇后棋子。

那是如何使用这个数组的？

而在 place() 方法中是这么使用的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 从第 row 行开始摆放皇后棋子
 *
 * @param row 行号
 */
void place(int row) {
    if (row == cols.length) {
        ways++;
        show();
        return;
    }
    for (int col = 0; col < cols.length; col++) {
        if (isValid(row, col)) {
            // 在第 row 行第 col 列摆放一个皇后
            cols[row] = col;
            // 摆放好一个棋子后去下一行摆放棋子
            place(row + 1);
            // 因为上一步的递归调用，其实回溯也完成了
        }
    }
}

在判断了第 row 行第 col 列可以摆放皇后棋子后，执行了一行代码： cols[row] = col;，这行代码表示在第 row 行第 col 列摆放一个皇后。这行代码后，就使用了递归调用，这个递归调用不仅可以前往下一行摆放棋子，还在无形之中完成了回溯的操作。

当前选中的棋盘格子可以摆放皇后棋子，随着循环的进行，如果发现剩下的行中无法摆放棋子时就要进行回溯操作。在回溯时，循环变量 col 的值也会增加，如果又在当前行选中了另外一个格子摆放皇后棋子，又会执行代码： cols[row] = col;，当执行这行代码时，原来的值就会被覆盖。

正因如此，最开始未进行优化时不用数据复原。

3.3 优化八皇后位运算

在【3.2 优化成员变量】中，引入了三个布尔类型的成员变量，如果对内存空间有严格要求，可以使用位运算进一步优化。

在八皇后问题的棋盘上，一个格子只会有两种情况，要么摆放了皇后棋子，要么没有，这是一种“非黑即白”的情况，正因如此才使用了布尔类型的成员变量来描述这种情况。

其实再思考一下，还会发现二进制数据也是一种非黑即白的情况。二进制数据中，只有 0 和 1 两种值出现，它们构成了整个二进制数据。

在八皇后问题中，棋盘共有 8 列，可以使用 byte 类型的数据来表示列。比如 00010100 就表示第三列和第五列存在皇后棋子。

在棋盘中，一共有 15 条对角线，可以使用 2 字节（16位）的 short 类型来表示对角线。

对先前的三个成员变量再次进行优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 标记着某一列是否有皇后
 */
byte cols;

/**
 * 标记着某一对角线是否有皇后（左上角 --> 右下角）
 */
short leftTop;

/**
 * 标记着某一对角线是否有皇后（右上角 --> 左下角）
 */
short rightTop;

位运算技巧

怎么用 byte 和 short 类型的数据来表示哪一列或哪一个对角线上有皇后棋子呢？

如果要确定二进制数据中哪一位是 1 应该怎么操作呢？

可以使用位运算中的与 &，比如：

1
2
3
4
  10001100
& 00001000
-----------
  00001000

像上述这样，使用与和左移相结合就可以确定哪一位是 1 了。比如判断 10001100 的第四位是否是 1，可以先让 1 左移 3 位得到 00001000，然后使用原值与左移得到的值进行与运算，判断结果是否为 0 ，如果为 0，表示指定位置是 1，反之不是 1。

如果想要让二进制数据中某一位由 0 变成 1 又该怎么操作呢？

可以使用位运算中的或 |，比如：

1
2
3
4
  10001100
| 00000010
-----------
  10001110

像上述这样，使用或和左移相结合就可以让二进制中的某一位由 0 变成 1 了。

那么反过来呢？怎么让二进制数据中某一位由 1 变成 0 呢？

可以使用位运算中的与 &，只不过左移后还得取非 ~，比如：

1
2
3
4
  10001100
& 11110111
-----------
  10000100

像上述这样，使用与、左移和非相结合就可以让二进制中的某一位由 1 变成 0 了，直接使用异或运算 ^ 也可以达到这种目的。

编码实现

位运算的一些技巧已经熟悉了，然后直接改写代码即可，主要改写的就是 place() 方法：

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
/**
 * 从第 row 行开始摆放皇后棋子
 *
 * @param row 行号
 */
void place(int row) {
    if (row == 8) {
        ways++;
        show();
        return;
    }
    for (int col = 0; col < 8; col++) {
        int cv = 1 << col;
        if ((cols & cv) != 0) continue;

        int lv = 1 << (row - col + 7);
        if ((leftTop & lv) != 0) continue;

        int rv = 1 << (row + col);
        if ((rightTop & rv) != 0) continue;

        queens[row] = col;
        // 在对应的位置摆放一个皇后
        cols |= (1 << col);
        leftTop |= lv;
        rightTop |= rv;

        place(row + 1);

        // 回溯时数据重置
        cols &= ~cv;
        leftTop &= ~lv;
        rightTop &= ~rv;
        // 上述数据重置也可直接使用异或^
    }
}

完整代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
 * @author 默烦
 * 2020/9/12
 */
public class Queens3 {

    public static void main(String[] args) {
        new Queens3().placeQueens();
    }

    /**
     * 数组索引是行号，数组元素是列号
     */
    int[] queens;

    /**
     * 标记着某一列是否有皇后
     */
    byte cols;

    /**
     * 标记着某一对角线是否有皇后（左上角 --> 右下角）
     */
    short leftTop;

    /**
     * 标记着某一对角线是否有皇后（右上角 --> 左下角）
     */
    short rightTop;

    /**
     * 摆法
     */
    int ways;

    void placeQueens() {
        queens = new int[8];
        place(0);
        System.out.println("8皇后一共有" + ways + "种摆法");
    }

    /**
     * 从第 row 行开始摆放皇后棋子
     *
     * @param row 行号
     */
    void place(int row) {
        if (row == 8) {
            ways++;
            show();
            return;
        }
        for (int col = 0; col < 8; col++) {
            int cv = 1 << col;
            if ((cols & cv) != 0) continue;

            int lv = 1 << (row - col + 7);
            if ((leftTop & lv) != 0) continue;

            int rv = 1 << (row + col);
            if ((rightTop & rv) != 0) continue;

            queens[row] = col;
            // 在对应的位置摆放一个皇后
            cols |= (1 << col);
            leftTop |= lv;
            rightTop |= rv;

            place(row + 1);

            // 回溯时数据重置
            cols &= ~cv;
            leftTop &= ~lv;
            rightTop &= ~rv;
            // 上述数据重置也可直接使用异或^
        }
    }

    void show() {
        for (int row = 0; row < 7; row++) {
            for (int col = 0; col < 7; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("------------------------");
    }
}

代码贴了出来，当然还得跑一跑，看看有没有问题：

八皇后位运算优化测试结果

到此，回溯与八皇后问题就介绍完了！ 🎉