【数据结构与算法】系列三十四 - 回溯

发表于 | 分类于
| 字数统计 1.8k 字 | 阅读时长 7 分钟

。。。

一、回溯

回溯（Back Tracking）可以理解为：通过选择不同的岔路口来通往目的地（找到想要的结果）。每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试。

树的前序遍历、图的深度优先搜索(DFS)、八皇后、走迷宫都是典型的回溯应用。

如下图，红色箭头代表前往目标点，绿色箭头代表回溯（再往下没有路了，只能往回走看是否有另外的路）。

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

1.1. 八皇后问题

八皇后问题（Eight Queens）是一个古老而著名的问题。在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击（任意两个皇后都不能处于同一行、同一列、同一斜线上）。请问有多少种摆法？

1个皇后（白色区域是剩余可摆放的位置，绿色是不能摆放的位置）：

2个皇后：

8个皇后（其中一种摆法）：

1.1.1. 解决思路

思路一：暴力出奇迹。

从64个格子中选出任意8个格子摆放皇后，检查每一种摆法的可行性，一共$C_{64}^8$种摆法（大概是4.4 * $10^9$种摆法）。

排列组合公式（高中知识）：

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

很显然，每一行只能放一个皇后，所以共有$8^8$（16777216）种摆法，检查每一种摆法的可行性。

思路三：回溯法（回溯 + 剪枝）。

1.2. 回溯法（Back Tracking）

在解决八皇后问题之前，可以先缩小数据规模，看看如何解决四皇后问题。

如下图，Q1在第一行第一列摆放后（图2），开始在第二行寻找位置摆放Q2，Q2摆放完毕后发现第三行没有位置给Q3（图3），此时开始往上一级查找另外可摆放Q2的位置（图4，这个步骤就是回溯），然后以此循环直到所有皇后都能按照规则入盘。

1.3. 剪枝（Pruning）

由于皇后问题的规则是任意两个皇后都不能处于同一行、同一列、同一斜线上。所以在寻找下一个摆放位置时，可以直接过滤之前的同一行、同一列、同一斜线上的位置，这个过滤操作就叫做剪枝（如下图，以四皇后为例）。

1.4. 代码实现

同一行、同一列、同一斜线，这三个条件只要都不满足，就可以摆放皇后。所以代码实现的重点就是判断待摆放皇后和已摆放皇后是否满足前面的条件。

数学知识扩展：二维坐标系中，处在同一斜线上的坐标点必然满足$|x_1 - x_2| == |y_1 - y_2|$。

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
public class Queens {

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

  /**
   * 存放皇后的坐标位置（数组索引是行号，数组元素是列号）
   */
  int[] queens;
  /**
   * 一共有多少种摆法
   */
  int ways;

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

  /**
   * 从第row行开始摆放皇后
   * @param row
   */
  void place(int row) {
    // 最后一行执行结束，意味着生成一种摆法
    if (row == queens.length) {
      ways++;
      show();
      return;
    }
    // 每一列都尝试摆放
    for (int col = 0; col < queens.length; col++) {
      // 判断是否可以摆放（剪枝）
      if (isValid(row, col)) {
        // 在第row行第col列摆放皇后
        queens[row] = col;
        // 摆放下一行
        place(row + 1);
        // col++就是回溯（寻找同一行下一列摆放方式）
      }
    }
  }

  /**
   * 判断第row行第col列是否可以摆放皇后（剪枝）
   */
  boolean isValid(int row, int col) {
    // 判断第row行【前面的行】是否已经有皇后
    // 因为是最新行，所以不需要判断同一行是否存在皇后
    for (int i = 0; i < row; i++) {
      // 第col列已经有皇后（同一列）
      if (queens[i] == col) {
        return false;
      }
      // 第i行的皇后跟第row行第col列格子处在同一斜线上（同一斜线）
      if (row - i == Math.abs(col - queens[i])) {
        return false;
      }
    }
    return true;
  }
  // 把所有摆放方式打印出来（1代表皇后摆放位置）
  void show() {
    for (int row = 0; row < queens.length; row++) {
      for (int col = 0; col < queens.length; col++) {
        if (queens[row] == col) {
          System.out.print("1 ");
        } else {
          System.out.print("0 ");
        }
      }
      System.out.println();
    }
    System.out.println("------------------------------");
  }
}

上面代码在判断某一行某一列是否有皇后时，每次都会遍历之前所有的行列，增加了重复计算成本。其实我们可以用一个列表记录每一列是否有皇后，每次只需要判断列表中对应列的值是否存在皇后（O(1)级别）。

对于斜线来说，其实每一个方向（左上角到右下角，右上角到左下角）的斜线一共是2n - 1。可以按照上面同列判断的方式实现斜线判断的功能，重点是怎么计算对角线的索引。

左上角到右下角的对角线索引：row – col + n - 1。

右上角到左下角的对角线索引：row + col。

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
public class Queens {

  public static void main(String[] args) {
    new Queens().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];
    leftTop = new boolean[(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;

      // 在第row行第col列摆放皇后
      queens[row] = col;
      // 把对应列和斜线设为已有皇后（剪枝）
      cols[col] = true;
      leftTop[ltIndex] = true;
      rightTop[rtIndex] = true;
      // 摆放下一行
      place(row + 1);
      // 回溯，因为是同一行，所以需要把上次位置的同一列、同一斜线的记录信息清空
			cols[col] = false;
			leftTop[ltIndex] = false;
			rightTop[rtIndex] = false;
    }
  }

  // 把所有摆放方式打印出来（1代表皇后摆放位置）
  void show() {
    for (int row = 0; row < queens.length; row++) {
      for (int col = 0; col < queens.length; col++) {
        if (queens[row] == col) {
          System.out.print("1 ");
        } else {
          System.out.print("0 ");
        }
      }
      System.out.println();
    }
    System.out.println("------------------------------");
  }
}

二、LeetCode