企业官网建设流程全解析

DFS 综合练习第四课：魔法王国的终极挑战——简化版 N 皇后

这一课，我们把前面学过的 DFS 知识全部串起来！

前面三课，我们已经学会了：

• 第一课：枚举所有可能，学会了选择。

• 第二课：金币凑数、勇士爬台阶，学会了记录方案、检查结果。

• 第三课：勇闯魔法地图，学会了检查条件、避免走进死胡同。

今天，我们要挑战一个经典的算法问题——N 皇后问题。

我们先不挑战 8×8 的大棋盘，而是从简单的 4×4 棋盘开始。只要弄懂这道题，将来再挑战更大的棋盘，就有了基础！

一、故事开始：四位皇后的魔法棋盘

魔法王国举办了一场棋盘挑战赛。

棋盘有 4 行、4 列，需要放置 4 位皇后，并且满足一个重要规则：

任何两位皇后都不能互相攻击。

在国际象棋中，皇后可以沿着横线、竖线和斜线移动。因此，两位皇后不能处于同一行、同一列或同一条斜线上。

我们把规则拆成三个孩子容易理解的要求：

规则一：不能同行

每一行只能放一位皇后。

规则二：不能同列

已经有皇后的列，不能再放另一位皇后。

规则三：不能同斜线

两位皇后如果沿着斜线相连，就会发生冲突。

我们的任务是：找出所有合法的摆放方案，并统计一共有多少种。

注意，这道题不是让我们随便摆四位皇后，而是要把所有符合规则的方案都找出来，一个也不能漏！

二、先不写代码：我们应该怎样思考？

还记得前面学过的“岔路口”吗？

每次来到一个岔路口，我们都尝试不同的选择。

这一次，我们不再决定“选还是不选”，而是：

来到第几行，就决定这一行的皇后放在哪一列。

比如，第一行有 4 个选择：

假设第一位皇后放在第 1 行、第 1 列。

接下来轮到第二行。第二行也有四个位置可以尝试，但有些位置已经不合法了。

• 第 1 列：和第一位皇后同列，不行！

• 第 2 列：和第一位皇后在斜线上，不行！

• 第 3 列：没有同行、同列或斜线冲突，可以继续尝试。

• 第 4 列：也没有冲突，可以继续尝试。

我们只沿着合法的选择继续往下探索。

如果后来发现无论怎样摆都无法完成任务，就退回上一行，换一个位置。

这就是 DFS 在这道题里的工作方式：

选择一个位置 → 检查是否合法 → 记录选择 → 继续下一行；如果走不通，就退回来换位置。

三、给电脑准备一本“皇后位置记录本”

如果我们每次都把棋盘画出来，电脑会不会很累？

其实，我们只需要用一个数组，就能记录每位皇后的位置。

int col[5];

这里使用下标1、2、3、4表示第几行，数组里的数字表示皇后所在的列。

例如：

记录本就是：第几行，对应第几列。

例如，col[2] = 4的意思就是：第二行的皇后放在第四列。

这样，我们就不必保存整个棋盘，只用几个数字就能记住摆放方案。

四、最重要的一步：怎样检查皇后是否合法？

假设我们正在给第row行摆放皇后。

前面几行的皇后已经摆好了，我们只需要检查它和前面每一位皇后有没有冲突。

检查一：是不是在同一列？

如果：

col[row] == col[i]

就说明当前皇后和第i行的皇后在同一列，发生冲突。

例如：

• 第 1 行在第 2 列；

• 第 3 行也想放在第 2 列。

两位皇后在同一列，所以不合法。

检查二：是不是在同一条斜线上？

这是本题最关键的知识点！

看下面这个例子：

我们用一个规律判断斜线：

两位皇后所在行的距离，等于它们所在列的距离，就在同一条斜线上。

例如：

• 第一位皇后在第 1 行、第 2 列；

• 第二位皇后在第 3 行、第 4 列。

行号相差 3-1 = 2，列号相差 4-2 = 2。两个距离相等，因此在同一条斜线上，不能这样摆放。

代码里可以这样判断：

if (row - i == col[row] - col[i] || row - i == col[i] - col[row]) { return false; }

为了让代码更简洁，我们也可以使用绝对值：

if (row - i == abs(col[row] - col[i])) { return false; }

这里的abs()是求绝对值。例如abs(-2)的结果是2。

五、把 DFS 的五个动作串起来

这道题里，DFS 不再是一个陌生的东西，而是我们熟悉的“岔路口探险”。

其中，剪枝可以理解为：发现这条路已经不可能成功，就不再浪费时间继续走。

例如，某位皇后已经和前面的皇后在同一列了，就没必要再摆后面的皇后了。我们直接放弃这个选择，换下一列。

六、完整 C++ 参考程序

接下来，我们把刚才的想法变成代码。建议同学们自己先猜一猜每个函数负责什么，再一起阅读。

#include <iostream> #include <cstdlib> using namespace std; const int N = 4; // col[row] 表示第 row 行的皇后所在的列 int col[N + 1]; int cnt = 0; // 检查当前行的皇后是否合法 bool check(int row) { for (int i = 1; i < row; i++) { // 检查是否在同一列 if (col[row] == col[i]) { return false; } // 检查是否在同一条斜线上 if (row - i == abs(col[row] - col[i])) { return false; } } return true; } // 从第 row 行开始摆放皇后 void dfs(int row) { // 四行都摆好了，找到一种完整方案 if (row == N + 1) { cnt++; cout << "方案 " << cnt << "："; for (int i = 1; i <= N; i++) { cout << col[i] << " "; } cout << endl; // 打印棋盘 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (col[i] == j) { cout << "Q "; } else { cout << ". "; } } cout << endl; } cout << endl; return; } // 尝试把皇后放在当前行的每一列 for (int c = 1; c <= N; c++) { // 选择并记录位置 col[row] = c; // 检查合法，合法才继续搜索 if (check(row)) { dfs(row + 1); } // 恢复记录，尝试下一列 col[row] = 0; } } int main() { dfs(1); cout << "一共找到 " << cnt << " 种方案" << endl; return 0; }

七、逐步追踪：电脑是怎样找到第一种方案的？

先看程序最开始的调用：

dfs(1);

意思是：从第一行开始摆放皇后。

我们用一张表，跟着电脑走一遍。

这说明了一个重要道理：

第一行放在第 1 列，并不代表后面一定有解。

如果这一条路走不通，DFS 就会回到前面的岔路口，换一个选择。它不会因为前面已经花了时间，就死守错误的方案。

最终，程序会找到两种合法方案。

程序的主要输出如下：

方案 1：2 4 1 3 . Q . . . . . Q Q . . . . . Q . 方案 2：3 1 4 2 . . Q . Q . . . . . . Q . Q . . 一共找到 2 种方案

这里用Q表示皇后，用.表示空格。

注意：程序输出的是两种不同的合法摆法，不是只找到两位皇后。

八、最后把五个知识点讲透

1. 选择：for (int c = 1; c <= N; c++)

每一行都尝试第 1、2、3、4 列。这就是 DFS 的岔路口。

2. 记录：col[row] = c

把当前皇后的位置记下来，后面的皇后才能根据它检查冲突。

3. 检查：check(row)

检查同列和同斜线。每次只需要检查当前皇后与前面几行的皇后。

4. 剪枝：if (check(row))

只有合法的选择才能进入下一行。不合法的选择直接放弃，不继续搜索。

5. 恢复：col[row] = 0

当前选择探索完毕后，清除这一行的记录，接着尝试下一列。否则，之前的选择可能会影响后面的探索。

九、课后练习：试着自己当一回 DFS 探险家

练习一：理解数组

如果col[3] = 4，代表什么？

A、第三列放了第四位皇后

B、第三行的皇后放在第四列

C、第四行的皇后放在第三列

答案：B。

col[3] 表示第三行的皇后所在列。

练习二：理解剪枝

如果当前皇后与前面某位皇后在同一列，应该怎么办？

继续摆下一行

把已经摆好的皇后全部删除

放弃当前列，尝试下一列

答案：C。

当前选择不合法，就放弃它，尝试下一列。

练习三：理解恢复

为什么尝试完一个位置后，要执行col[row] = 0？

清除当前行的旧记录，方便尝试其他位置

让程序马上结束

把皇后移动到第 0 列

答案：A。

恢复记录，避免旧选择干扰后面的探索。

十、这一课的记忆口诀

每行选一列，先记再检查；

合法往下走，不合法就剪枝；

走完要恢复，找到答案就记录。

这就是 DFS 综合运用的完整过程。

从子集、排列、组合，到金币凑数、爬台阶，再到网格、迷宫和 N 皇后，我们一直在做同一件事：尝试选择，记录状态，检查条件，继续探索，走不通就返回。

同学们真正掌握了这个思路，以后遇到新的搜索题，就不只是背代码，而是能够自己分析：有哪些选择？怎样判断合法？什么时候继续？什么时候返回？这才是学习 DFS 最重要的收获。