C++实现马走日：深度优先搜索、回溯与剪枝算法详解-平芜编程栈

1. 项目概述：从“马走日”到算法思维的实战演练

最近在辅导一些中小学生准备信息学竞赛时，经常被问到一类经典问题：“马走日”，也叫“骑士遍历”或“骑士巡游”。这问题听起来像是个象棋游戏，但它实际上是一个绝佳的算法思维训练场，完美融合了深度优先搜索、回溯和剪枝这三大核心算法思想。很多初学者一听到DFS、回溯就觉得头大，感觉是“高端”玩意儿，但如果你能亲手用C++把“马走日”跑通，你会发现这些概念一下子就从抽象的课本知识，变成了你手里实实在在能解决问题的工具。今天，我就以一个老码农带新人的视角，拆解一下如何用C++实现“马走日”，并在这个过程中，把DFS、回溯、剪枝这些听起来唬人的词，掰开揉碎了讲清楚。无论你是刚开始接触算法竞赛的学生，还是想巩固基础的程序员，相信这篇结合了实战代码和思维剖析的长文都能给你带来收获。

“马走日”问题的典型描述是：在一个n * m的棋盘上，给定一个初始位置(x, y)，按照中国象棋中马的移动规则（走“日”字形，有8个可能方向），尝试让马遍历棋盘的每一个格子，且每个格子只能经过一次。我们需要计算出所有可能的遍历路径数量，或者找出其中一条/所有完整的路径。这本质上是一个图的深度优先遍历问题，棋盘上的每个格子是图的一个节点，马的合法日字步构成了节点之间的边。解决它的核心框架就是深度优先搜索，但裸的DFS会带来恐怖的指数级时间复杂度，因此必须引入回溯来撤销错误选择，并运用剪枝来提前终止无效的搜索分支，这是算法优化和竞赛解题的关键。

2. 核心算法思想拆解：为什么是DFS+回溯+剪枝？

在动手写代码之前，我们必须先理解为什么这个问题的“标准答案”是DFS、回溯和剪枝的组合拳，而不是其他方法，比如广度优先搜索。这关乎到对问题本质和算法特性的深刻理解。

2.1 深度优先搜索：一条道走到黑的探索者

DFS的核心思想是“尽可能深”地探索图的分支。在“马走日”中，我们从起点出发，尝试一个方向走到下一个格子，然后再从那个格子继续尝试走下去，直到无法继续（要么走出棋盘，要么走到已访问的格子）或者成功走完所有格子。这个过程就像走迷宫，我们倾向于先沿着一条路一直走到底，而不是像BFS那样一层一层地扫荡。

选择DFS而非BFS的主要原因在于路径记录和状态空间。我们需要记录的是一条完整的访问序列（即马的行走路径）。BFS更适合找“最短路径”或“最少步数”，它同时维护多条路径的前端，状态管理复杂。而DFS天然地使用递归栈来保存当前路径，状态清晰，实现寻找所有可能完整路径（即哈密顿路径）的任务更为直观和简洁。递归函数的每一层，都对应马在棋盘上的一个具体位置和当前的路径状态。

2.2 回溯：勇于试错，及时回头

裸的DFS有一个致命问题：如果它走进一条“死胡同”（提前无路可走但棋盘还未遍历完），那么这次搜索就失败了，并且由于递归调用已经深入，程序可能直接结束或者无法尝试其他可能性。回溯就是解决这个问题的钥匙。它的思想是：当沿着当前路径深入发现不满足最终条件时，就退回到上一个决策点（即回溯），尝试其他的选择。

在代码中，回溯体现在两个关键操作上：

状态标记与恢复：在尝试进入一个新格子前，将其标记为“已访问”。如果从这个格子出发的所有后续尝试都失败了，那么在递归函数返回上层之前，必须将这个格子的“已访问”标记清除，让它恢复为未访问状态，这样其他路径才有可能再次使用这个格子。
路径记录与删除：同样，将当前格子加入路径列表后，如果后续失败，在回溯时也需要将其从路径列表中移除。

这个过程就像玩“一笔画”游戏，画错了线，你得用橡皮擦掉最后几步，回到还能做其他选择的地方重新画。没有回溯的DFS是鲁莽的，有回溯的DFS才是智慧的。

2.3 剪枝：聪明地放弃，大幅提升效率

即使有了回溯，对于稍大的棋盘（比如6x6），纯粹的DFS+回溯的搜索空间依然巨大，可能导致程序运行时间无法接受（俗称“TLE”，超时）。剪枝就是为了砍掉那些“明知道不可能成功”的搜索分支，从而节省大量计算时间。这是算法竞赛中从“暴力”走向“高效”的关键一步。

对于“马走日”，有几类常见的剪枝策略：

可行性剪枝：在尝试移动前，先判断目标格子是否在棋盘内、是否未被访问。这是最基本的剪枝，避免无效递归调用。
最优性/可行性预判剪枝（启发式）：更高级的剪枝。例如，在每一步，可以先检查当前未访问的格子中，是否存在某个格子，它的所有合法邻接格都已被访问（除了当前格）。如果存在，那么这个格子将成为一个“孤岛”，马将来永远无法进入，当前路径必然失败，可以立即回溯。这种剪枝能极大提升效率。
搜索顺序优化：这也是一种剪枝思想。马的下一步有8个方向可选。优先选择“出口”少（即下一步可选格子少）的格子走，这被称为“Warnsdorff规则”。这虽然不能保证绝对找到解，但能大大提高在寻找一条可行解时的速度，让DFS更快地深入到深层状态，从而间接剪掉了很多早期徘徊的分支。

理解了这三者的关系，我们就可以说：DFS提供了遍历的框架，回溯赋予了框架修正错误的能力，而剪枝则赋予了框架前瞻性的智慧，三者结合才能高效解决此类组合搜索问题。

3. 代码实现与逐行解析

理论说得再多，不如一行代码。下面我将呈现一个完整的、注释详细的C++解决方案，并逐一解析关键部分。这个版本不仅计算路径数量，还可以记录并打印出第一条找到的完整路径，非常适合教学和理解。

#include <iostream> #include <vector> #include <iomanip> // 用于格式化输出 using namespace std; class KnightTour { private: int n, m; // 棋盘行数、列数 int startX, startY; // 起始坐标 int totalSteps; // 总步数 = n*m int pathCount; // 成功路径计数器 vector<vector<int>> board; // 棋盘，记录访问顺序（步数），0表示未访问 vector<vector<bool>> visited; // 访问标记，与board功能可合并，这里为清晰分开 vector<pair<int, int>> path; // 记录当前路径序列 // 马移动的8个方向向量 (dx, dy) const int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2}; const int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; public: KnightTour(int rows, int cols, int sx, int sy) : n(rows), m(cols), startX(sx), startY(sy), totalSteps(rows * cols), pathCount(0) { board.resize(n, vector<int>(m, 0)); visited.resize(n, vector<bool>(m, false)); path.reserve(totalSteps); // 预留空间，避免频繁扩容 } // 主求解函数 void solve() { // 检查起始点合法性 if (startX < 0 || startX >= n || startY < 0 || startY >= m) { cout << "起始位置不合法！" << endl; return; } // 初始化：标记起点，加入路径 visited[startX][startY] = true; board[startX][startY] = 1; // 第一步 path.push_back({startX, startY}); cout << "开始搜索棋盘 (" << n << "x" << m << ") 从 (" << startX << ", " << startY << ") 出发的骑士遍历..." << endl; dfs(startX, startY, 1); // 开始深度优先搜索，当前已走1步 cout << "\n搜索完成。总共找到 " << pathCount << " 条不同的遍历路径。" << endl; if (pathCount > 0) { cout << "第一条完整路径的访问顺序如下：" << endl; printFirstPath(); } } private: // 深度优先搜索递归函数 // (x, y): 当前位置 // step: 当前是第几步 void dfs(int x, int y, int step) { // 递归终止条件：已经走完所有格子 if (step == totalSteps) { pathCount++; // 如果是第一条找到的路径，则记录当前棋盘状态 if (pathCount == 1) { // 此时board已经记录了完整的访问顺序 // 我们可以选择保存一个副本，这里为了简单，最后统一打印path } return; // 回溯，尝试寻找其他路径 } // 尝试向8个方向移动 for (int i = 0; i < 8; i++) { int nextX = x + dx[i]; int nextY = y + dy[i]; // **剪枝1：可行性剪枝** - 判断下一步是否合法 if (isValidMove(nextX, nextY)) { // 执行移动：标记、记录、加入路径 visited[nextX][nextY] = true; board[nextX][nextY] = step + 1; path.push_back({nextX, nextY}); // 递归深入 dfs(nextX, nextY, step + 1); // **回溯的关键步骤**：撤销当前选择，恢复状态 visited[nextX][nextY] = false; board[nextX][nextY] = 0; path.pop_back(); } } // 如果8个方向都尝试完毕仍未成功（或都不可行），函数将自动返回到上一层调用，实现回溯 } // 判断移动是否合法（基础剪枝） bool isValidMove(int x, int y) { // 1. 是否在棋盘范围内 if (x < 0 || x >= n || y < 0 || y >= m) { return false; } // 2. 该格子是否未被访问过 if (visited[x][y]) { return false; } // 这里可以添加更复杂的剪枝逻辑，例如启发式剪枝 return true; } // 打印第一条找到的完整路径 void printFirstPath() { // 注意：为了打印第一条路径，我们需要在找到第一条路径时保存棋盘状态。 // 上述代码中并未保存，因此我们这里采用一个简化方法：重新模拟搜索，找到第一条路径时打印并终止。 // 在实际竞赛或高效代码中，应在dfs内发现第一条路径时立即保存board状态。 cout << "路径序列 (行, 列):" << endl; for (size_t i = 0; i < path.size(); ++i) { cout << "第 " << setw(2) << i+1 << " 步: (" << path[i].first << ", " << path[i].second << ")"; if ((i + 1) % 5 == 0) cout << endl; // 每5步换行 else cout << " "; } cout << endl << endl; // 也可以选择打印棋盘形式的访问顺序（需要额外保存第一个解的board） // cout << "棋盘访问顺序 (数字表示第几步走到该格子):" << endl; // for (int i = 0; i < n; ++i) { // for (int j = 0; j < m; ++j) { // cout << setw(3) << firstSolutionBoard[i][j] << " "; // } // cout << endl; // } } }; int main() { // 示例：5x5棋盘，从(0,0)开始 int rows = 5, cols = 5; int startRow = 0, startCol = 0; KnightTour kt(rows, cols, startRow, startCol); kt.solve(); // 可以尝试其他大小和起点 // KnightTour kt2(6, 6, 0, 0); // kt2.solve(); // 注意：6x6搜索空间很大，可能需要很长时间或导致栈溢出 return 0; }

代码关键点解析：

数据结构选择：
- board: 使用vector<vector<int>>，用整数记录马在第几步走到该格子，0表示未访问。这便于直观展示路径。
- visited: 使用vector<vector<bool>>，布尔矩阵专门用于快速判断格子是否被访问。虽然board非零即可判断，但分开更清晰，且访问检查是O(1)操作。
- path: 使用vector<pair<int,int>>动态记录每一步的坐标，方便最后输出路径序列。
- dx, dy: 用两个常量数组定义8个方向，这是处理网格移动问题的标准技巧，使代码简洁且不易出错。
递归函数dfs的精髓：
- 参数：(x, y, step)清晰地定义了当前状态。
- 终止条件：step == totalSteps意味着成功找到一条完整路径，计数器pathCount加一。
- 循环尝试：for循环遍历8个方向，体现了DFS中“探索所有相邻节点”的思想。
- 回溯三部曲：在递归调用dfs之后，紧跟着的三行代码（visited[...]=false，board[...]=0，path.pop_back()）是回溯的灵魂。它们确保了递归返回后，状态被精确还原到尝试当前方向之前的样子，从而允许for循环继续尝试下一个方向。
剪枝函数isValidMove：这是最基础的剪枝，在递归深入前进行“预检”，过滤掉明显非法的移动，避免无谓的递归调用。这是提升性能的第一道关卡。

注意：上述代码为了清晰，省略了更高级的剪枝（如启发式剪枝）和寻找第一条路径时立即保存状态的逻辑。在竞赛中，为了应对更大棋盘，这些优化是必须的。

4. 从基础到优化：高级剪枝策略与性能对比

对于小棋盘（如5x5），基础版的DFS+回溯已经可以快速得出答案。但当棋盘增大到6x6、8x8时，搜索空间呈指数级爆炸，基础版本可能会运行几分钟甚至几小时都无法完成。这时，高级剪枝策略就至关重要了。

4.1 Warnsdorff规则（启发式搜索顺序剪枝）

这个规则很简单：在当前马的位置，计算所有合法下一步格子的“出口数”（即从那个格子出发，下一步还有多少个未访问的合法格子）。然后，优先选择出口数最少的那个格子作为下一步。其背后的直觉是：尽早访问那些“偏僻”的、出路少的格子，把出路多的、中心区域的格子留到后面，这样可以降低早期走入死胡同的概率。

实现方法：在dfs函数的循环尝试方向之前，不对dx, dy的顺序进行简单遍历，而是先收集所有合法的下一步格子，然后根据它们的“出口数”进行排序，最后按照排序后的顺序（出口数由少到多）进行递归尝试。

// 在dfs函数内部，尝试移动前增加排序逻辑 vector<pair<int, int>> nextMoves; for (int i = 0; i < 8; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (isValidMove(nx, ny)) { int exitCount = countExits(nx, ny); // 计算从(nx,ny)出发的合法出口数 nextMoves.push_back({exitCount, i}); // 存储出口数和方向索引 } } // 按出口数升序排序 sort(nextMoves.begin(), nextMoves.end()); // 按排序后的方向进行递归 for (auto& move : nextMoves) { int dirIndex = move.second; int nextX = x + dx[dirIndex]; int nextY = y + dy[dirIndex]; // ... 执行移动、递归、回溯 ... }

这个优化对于寻找一条可行解（而不是所有解）的效果是惊人的，通常能在毫秒级内解决8x8的经典骑士巡游问题。

4.2 可行性预判剪枝（前瞻性剪枝）

这是一种更强的剪枝。在决定是否走入一个格子(nx, ny)之前，我们不仅检查它本身是否合法，还快速检查一下剩余的棋盘状态。一个经典的策略是：检查是否存在某个尚未访问的格子，它所有的合法邻接格（除了当前马所在的格子(x,y)和候选格子(nx,ny)）都已经被访问了。如果存在这样的“孤岛”格子，那么即使马走到了(nx, ny)，将来也绝对无法访问那个“孤岛”，这条路径注定失败，因此可以立即剪掉(nx, ny)这个分支。

实现这种剪枝需要更复杂的检查逻辑，会带来额外的计算开销，但对于中等规模棋盘，它往往能剪掉大量分支，净收益是正的。对于非常大的棋盘（如10x10以上），其开销可能变得显著，需要谨慎评估。

4.3 对称性剪枝

如果棋盘是对称的（如正方形），并且起点在对称轴上，那么很多解本质上是对称的。通过定义搜索顺序或限制起始移动方向，可以避免计算对称的重复解，从而将搜索空间减半或更多。但这通常用于计数问题，并且需要仔细证明以避免漏解。

性能对比实验（感性认识）：

5x5棋盘，起点(0,0)：
- 基础版：可能在几毫秒到几十毫秒内找到所有解（数量不多）。
- Warnsdorff优化版：寻找一条解的速度极快，但找全解可能稍慢（因为排序开销）。
6x6棋盘，起点(0,0)：
- 基础版：可能需要数秒到数十秒，甚至更久，搜索空间巨大。
- Warnsdorff优化版：寻找一条解仍然非常快（毫秒级）。
- Warnsdorff+可行性预判：能更快地剪枝，在寻找所有解的任务上可能比基础版快几个数量级。
8x8棋盘，起点(0,0)：
- 基础版：几乎不可能在合理时间内完成（解的数量是天文数字）。
- Warnsdorff优化版：寻找一条解是经典问题，可以在毫秒级完成。
- 寻找所有解：即使有高级剪枝，也需要极其复杂的算法和大量计算资源，通常不是普通DFS回溯能解决的。

实操心得：在算法竞赛中，除非题目明确要求输出所有解，否则应优先考虑使用Warnsdorff规则快速找到一条可行解。如果要求所有解，必须设计强有力的剪枝，并且往往需要结合问题特性（如棋盘奇偶性分析）进行数学上的优化，有时DFS本身可能就不是最优解法了。

5. 常见问题、调试技巧与扩展思考

在实际编写和调试“马走日”程序时，新手常会遇到一些典型问题。

5.1 栈溢出与递归深度

棋盘较大时，递归深度可能达到n*m（如8x8棋盘深度为64）。C++默认的栈空间可能不足以支持如此深的递归调用，导致栈溢出（Segmentation fault）。解决方案：

调整编译器栈空间：对于GCC/Clang，可以使用编译选项-Wl,-stack_size,10000000（macOS/Linux）或在代码中使用#pragma指令（视编译器而定）来增大栈大小。
改为迭代加深搜索或手动栈：对于极深搜索，可以考虑用循环和显式栈（stack容器）来模拟递归过程，避免系统调用栈的限制。但这会大大增加代码复杂度。
优化剪枝：最根本的方法是加强剪枝，减少无效递归的深度和广度。

5.2 时间复杂度与“超时”

这是竞赛中最常见的问题。排查与优化方向：

输出调试：在递归函数入口打印当前步数和位置，观察搜索过程是否卡在某个无望的分支。过多的重复打印会影响性能，可条件编译或使用计数器限制输出量。
性能分析：使用clock()函数测量不同剪枝策略下关键函数的运行时间。
复杂度估算：理论上，最坏时间复杂度是O(8^(n*m))，但实际由于棋盘边界和访问限制，会小很多。估算你实现的算法在目标棋盘大小下的最大递归调用次数，判断是否可行。
启用编译器优化：使用-O2或-O3优化等级编译，有时能带来显著提升。

5.3 路径记录与输出

当需要输出路径时，要小心浅拷贝与深拷贝问题。如果在找到一条路径时简单地将path向量或board矩阵赋值给一个“解决方案”变量，由于回溯会修改path和board，最终你保存的“解决方案”可能只是一个空壳或最后的状态。正确做法是在找到解的那一刻，将当前path或board的内容完整地复制（深拷贝）到另一个专门存储解的变量中。

5.4 问题扩展与变种

“马走日”是一个模型，掌握后可以解决许多变种问题，这也是算法思维举一反三的体现：

求一条可行路径：使用Warnsdorff规则高效求解。
求所有可行路径：如本文基础版，需要强大的剪枝。
求指定终点的哈密顿路径：在递归终止条件中增加终点判断。
棋盘上有障碍物：在isValidMove中增加对障碍物的检查。
求回到起点的哈密顿回路：在终止条件中检查最后一步是否能跳回起点。
非完全遍历（指定步数）：修改终止条件为达到指定步数。
最大访问格子数：在递归过程中维护一个最大值，即使找不到完整路径，也记录最多能走多少步。

5.5 环境配置与学习建议

从热搜词看，很多朋友关心环境。对于C++算法学习，我强烈推荐使用Visual Studio Code (VSCode)配合MinGW-w64或MSYS2中的GCC编译器。配置好C/C++插件和调试器后，单步调试递归函数、观察变量变化，是理解DFS和回溯过程最直观的方式。比单纯看代码和输出有效十倍。

对于初学者，不要一开始就追求最优化解。先写出基础的回溯框架，确保逻辑正确，在小棋盘上能跑出结果。然后逐步加入剪枝，每加一种，都测试一下性能变化，并思考这个剪枝为什么有效。这个过程本身就是算法思维最好的训练。

最后，算法学习切忌死记硬背模板。理解“马走日”背后DFS的栈式推进、回溯的状态重置、剪枝的提前终止这些思想，比你记住这段代码更重要。下次遇到数独、N皇后、全排列、组合求和等问题时，你会惊喜地发现，它们都是同一个“套路”下的不同面孔，而你已经掌握了破解它们的钥匙。