零基础数据结构与算法——第五章：高级算法-回溯算法N皇后问题

5.3 回溯算法（Backtracking）

5.3.1 回溯算法的基本概念

什么是回溯算法？

回溯算法是一种通过探索所有可能的解来找到所有解（或特定解）的算法。它采用试错的思想，尝试分步解决问题，当发现当前方案不是正确的解或不可能通向正确的解时，就回溯到上一步，尝试其他可能的方案。

生活例子：

想象你在一个迷宫中寻找出口。你会怎么做？一种方法是：

1. 选择一条路径前进
2. 如果遇到死胡同，就退回到上一个路口
3. 尝试另一条没走过的路
4. 重复这个过程，直到找到出口或尝试完所有可能的路径

这就是回溯算法的基本思想——尝试、失败、回退、再尝试。

回溯算法的基本思想

1. 定义解空间：包含问题的所有解
2. 使用深度优先搜索：遍历解空间
3. 利用约束条件：避免无效搜索

图解：

                    [开始]|↓[选择1]/   |   \/    |    \↓     ↓     ↓[选择1-1][选择1-2][选择1-3] ← 如果这条路径不可行，回溯到上一步/  |  \     |      |  \/   |   \    |      |   \↓    ↓    ↓   ↓      ↓    ↓... [解]  ...  ...    ...  ...

回溯算法与其他算法的区别

算法	特点	适用问题
回溯算法	尝试所有可能的解，遇到不符合条件的解就回退	组合问题、排列问题、子集问题、路径问题
贪心算法	每步都选择当前最优解	具有贪心选择性质的问题
动态规划	将问题分解为子问题，并存储子问题的解	具有重叠子问题和最优子结构的问题
分治算法	将问题分解为独立的子问题，解决后合并结果	可以分解为独立子问题的问题

生活例子对比：

假设你要从家到学校，有多条路径可选：

• 回溯算法：尝试每一条可能的路径，如果遇到堵车或死路，就返回上一个路口，尝试其他路径。
• 贪心算法：每次都选择看起来最短的路。
• 动态规划：提前计算出从每个路口到学校的最短路径，然后根据这些信息选择最优路径。
• 分治算法：将路径分成几段，分别找出每段的最佳路径，然后组合起来。

回溯算法的一般步骤

1. 定义递归函数及其参数：确定需要传递的状态信息
2. 确定递归终止条件：找到一个解或无法继续搜索
3. 遍历所有可能的选择：考虑当前状态下的所有可能选择
4. 对于每个选择：
   • 进行选择（修改状态）
   • 递归调用
   • 撤销选择（回溯，恢复状态）

伪代码：

function backtrack(状态, 选择列表):if 满足结束条件:记录解returnfor 选择 in 选择列表:if 选择不合法:continue做选择（修改状态）backtrack(新状态, 新选择列表)撤销选择（回溯，恢复状态）

回溯算法的优缺点

优点：

• 能找到所有可能的解
• 适用于组合、排列等问题
• 实现相对简单

缺点：

• 时间复杂度通常较高（可能是指数级）
• 对于大规模问题可能效率低下
• 需要额外空间存储状态

适用场景

回溯算法特别适合解决以下类型的问题：

1. 组合问题：从n个数中选择k个数的所有可能组合
2. 排列问题：n个数的所有可能排列
3. 子集问题：一个集合的所有子集
4. 路径问题：迷宫寻路、旅行商问题等
5. 约束满足问题：数独、八皇后、图着色等

5.3.2 经典回溯算法问题

1. N皇后问题

问题描述：

在N×N的棋盘上放置N个皇后，使得它们互不攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。

生活例子：

想象你是一名活动组织者，需要在一个大厅里安排N个重要嘉宾就座。每个嘉宾都很有影响力，如果两个嘉宾坐得太近（同一行、同一列或同一对角线），他们会互相干扰。你的任务是找到一种安排方式，使得所有嘉宾都能和平共处。

问题分析：

在国际象棋中，皇后可以攻击同一行、同一列或同一对角线上的任何棋子。因此，要使N个皇后互不攻击，我们需要：

1. 每行只能有一个皇后
2. 每列只能有一个皇后
3. 每条对角线只能有一个皇后

由于每行只能放一个皇后，我们可以逐行放置皇后，对于每一行，尝试在不同的列放置皇后，然后检查是否有冲突。

回溯策略：

1. 从第一行开始，尝试在每一列放置皇后
2. 如果当前位置不会导致冲突，则在该位置放置皇后，并递归处理下一行
3. 如果递归返回失败，则回溯（撤销当前位置的皇后），尝试下一列
4. 如果所有列都尝试过仍然失败，则返回失败
5. 如果成功放置了N个皇后，则找到一个解

图解过程（以4皇后为例）：

初始状态：空棋盘

. . . .
. . . .
. . . .
. . . .

第一行尝试放置皇后：

Q . . .  (尝试第一列)
. . . .
. . . .
. . . .

第二行尝试放置皇后（第一列和第二列不行，因为会与第一行的皇后冲突）：

Q . . .
. . Q .  (尝试第三列)
. . . .
. . . .

第三行尝试放置皇后（尝试所有列都会冲突）：

Q . . .
. . Q .
? ? ? ?  (所有位置都不行)
. . . .

回溯到第二行，尝试第四列：

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

第三行尝试放置皇后：

Q . . .
. . . Q
. Q . .  (尝试第二列)
. . . .

第四行尝试放置皇后：

Q . . .
. . . Q
. Q . .
. . Q .  (尝试第三列，成功找到一个解)

代码实现：

public static List<List<String>> solveNQueens(int n) {List<List<String>> result = new ArrayList<>();char[][] board = new char[n][n];// 初始化棋盘for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {board[i][j] = '.';}}System.out.println("开始求解" + n + "皇后问题...");backtrack(board, 0, result);System.out.println("共找到" + result.size() + "个解");return result;
}private static void backtrack(char[][] board, int row, List<List<String>> result) {// 如果已经放置了n个皇后（到达最后一行之后），则找到一个解if (row == board.length) {result.add(constructSolution(board));return;}int n = board.length;for (int col = 0; col < n; col++) {// 尝试在当前行的每一列放置皇后if (isValid(board, row, col)) {// 放置皇后board[row][col] = 'Q';// 递归处理下一行backtrack(board, row + 1, result);// 回溯，撤销当前位置的皇后board[row][col] = '.'; }}
}// 检查在board[row][col]位置放置皇后是否合法
private static boolean isValid(char[][] board, int row, int col) {int n = board.length;// 检查列（因为是逐行放置，所以只需检查当前行之前的行）for (int i = 0; i < row; i++) {if (board[i][col] == 'Q') {return false;}}// 检查左上对角线for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (board[i][j] == 'Q') {return false;}}// 检查右上对角线for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (board[i][j] == 'Q') {return false;}}// 如果没有冲突，则合法return true;
}// 将棋盘转换为字符串表示
private static List<String> constructSolution(char[][] board) {List<String> solution = new ArrayList<>();for (char[] row : board) {solution.add(new String(row));}return solution;
}// 打印棋盘（用于调试）
private static void printBoard(char[][] board) {for (char[] row : board) {System.out.println(new String(row));}System.out.println();
}

时间复杂度分析：

N皇后问题的时间复杂度是O(N!)，因为：

• 第一行有N种放法
• 第二行最多有N-1种放法
• 第三行最多有N-2种放法
• 以此类推

所以总的时间复杂度约为O(N!)。

空间复杂度分析：

O(N²)用于存储棋盘，O(N)用于递归调用栈的深度。

优化思路：

1. 使用一维数组表示皇后位置：可以用一个长度为N的数组queens，其中queens[i]表示第i行皇后所在的列。

2. 使用三个布尔数组加速检查：

   • columns[j]：表示第j列是否已有皇后
   • diagonals1[i+j]：表示从左上到右下的对角线是否已有皇后
   • diagonals2[i-j+n-1]：表示从右上到左下的对角线是否已有皇后

这样可以将检查冲突的时间从O(N)降低到O(1)。

应用场景：

N皇后问题是回溯算法的经典应用，虽然在实际中直接应用较少，但其解决思路可以应用于：

• 资源分配问题
• 图着色问题
• 排课问题
• 其他约束满足问题