棋盘问题：深度优先搜索与回溯算法实战解析

1. 项目概述：从棋盘问题看搜索与回溯的实战价值

“棋盘问题”是《信息学奥赛一本通》中一个经典的搜索与回溯算法练习题，编号1217。乍一看，题目描述很简单：在一个给定形状的棋盘上摆放棋子，要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列。这听起来是不是有点像简化版的“八皇后问题”？没错，它的本质就是“八皇后问题”的一个变种，但约束条件更少，棋盘形状不规则，且摆放的棋子数量可能少于棋盘的行数。对于刚接触深度优先搜索和回溯算法的选手来说，这道题是一个绝佳的“磨刀石”。它不像八皇后那样有固定的8x8棋盘和8个皇后，其不规则的棋盘和可变的棋子数，恰恰能帮你剥离对具体数字的依赖，真正理解“状态”、“选择”、“约束”和“回溯”这几个核心概念是如何在代码中落地的。很多人在学习算法时，看理论觉得懂了，一写代码就懵，而“棋盘问题”就是帮你跨越这道坎的关键一步。无论你是正在备战信息学奥赛的中学生，还是希望夯实算法基础的开发者，吃透这道题，都能让你对搜索算法的理解提升一个档次。

2. 问题核心与算法思路拆解

2.1 问题重述与建模

题目通常会给一个 n x n 的字符矩阵来表示棋盘，其中‘#’表示可以放置棋子的位置，‘.’表示不能放置的位置。我们需要在这个棋盘上放置 k 个棋子（k ≤ n），并满足任意两个棋子既不在同一行，也不在同一列。

这本质上是一个组合选择问题。我们不能暴力枚举所有位置组合，因为组合数会爆炸。核心思路是利用深度优先搜索配合回溯，系统地探索所有可能的摆放方案。

为什么是DFS？因为我们要尝试所有可能的摆放顺序。想象一下，你从第一行开始，尝试在这一行的每一个合法位置（即‘#’）放置一个棋子。每放置一个，就标记这一列已经被占用（因为不能再放），然后“深入”到下一行去尝试。这就是“深度优先”。当我们在某一行找不到合法位置，或者已经放满了k个棋子时，我们就需要“回溯”：撤销当前行所做的选择（取消列的占用标记），回到上一行，尝试该行的下一个合法位置。这个过程就像走迷宫，一条路走到黑，走不通就退回上一个岔路口换条路。

2.2 状态定义与搜索树

理解搜索算法的关键在于在脑中构建一棵“搜索树”。

• 树的每一层：对应棋盘的一行。我们按行进行搜索，这是解决此类行列约束问题的常用技巧，可以天然避免“同行”冲突。
• 树的每个节点：表示搜索进行到某一行的某个状态，包含了当前已经放置的棋子数量cnt，以及哪些列已经被占用（通常用一个布尔数组col_used记录）。
• 节点的分支：对于当前行，我们遍历所有列。如果该位置是‘#’且该列未被占用，那么这就是一个合法的分支，我们可以选择在此放置棋子，并进入下一层（下一行）的搜索。
• 叶子节点：当cnt == k（找到一种合法方案）或者已经搜索完所有行时，到达叶子节点。

我们的DFS就是系统地遍历这棵搜索树，记录所有到达cnt == k的路径数。

2.3 回溯的精髓

回溯是DFS的“后悔药”。代码中的体现通常如下：

// 伪代码示意 void dfs(int current_row) { if (cnt == k) { // 找到一种方案 ans++; return; } if (current_row >= n) return; // 超出棋盘，返回 // 情况1：在当前行选择放置一个棋子 for (int j = 0; j < n; j++) { if (棋盘[current_row][j]是‘#’ && 第j列未被占用) { 标记第j列为占用; cnt++; dfs(current_row + 1); // 深入下一行 // 回溯：撤销选择 cnt--; 取消第j列的占用标记; } } // 情况2：在当前行选择不放置任何棋子 dfs(current_row + 1); }

注意最后一部分dfs(current_row + 1)。这是本题非常关键的一个点！因为题目只要求放k个棋子，k可能小于n。这意味着不是每一行都必须放棋子。所以，对于每一行，我们有两种策略：1) 尝试在该行放置一个棋子（如果可能）；2) 直接跳过该行。我们必须对这两种情况都进行搜索，否则会漏掉很多合法解（例如，所有棋子都放在最后几行的方案）。

实操心得：很多初学者在这里犯错，只考虑了“当前行必须放棋子”的情况。一定要牢记，DFS是枚举所有可能性，“不放”也是一种需要被枚举的选择。这是“棋盘问题”区别于标准八皇后（每行必须放一个）的核心差异，也是题目设计的巧妙之处。

3. 代码实现与逐行解析

下面我们结合C++代码，详细拆解每一个步骤。假设输入格式为：每组数据第一行是n, k，接下来n行是棋盘。n=0, k=0表示输入结束。

#include <iostream> #include <cstring> using namespace std; char board[10][10]; // 棋盘，题目规模n<=8，开10足够 bool col_used[10]; // 标记列是否被占用 int n, k; int ans; // 方案总数 // current_row: 当前搜索到第几行 (从0开始) // placed_cnt: 已经放置的棋子数 void dfs(int current_row, int placed_cnt) { // 递归终止条件1：已经放置了k个棋子，找到一种合法方案 if (placed_cnt == k) { ans++; return; // 不需要再继续搜索，直接返回 } // 递归终止条件2：已经搜索完所有行，但还没放够k个棋子，这条路径无效 if (current_row >= n) { return; } // 选择1：尝试在当前行(current_row)放置一个棋子 for (int col = 0; col < n; col++) { // 条件：位置是‘#’，且该列未被占用 if (board[current_row][col] == '#' && !col_used[col]) { // 做出选择 col_used[col] = true; // 标记该列被占用 // 深入到下一行，棋子数加1 dfs(current_row + 1, placed_cnt + 1); // 回溯：撤销选择，恢复状态 col_used[col] = false; } } // 选择2：当前行不放任何棋子，直接搜索下一行 dfs(current_row + 1, placed_cnt); } int main() { while (cin >> n >> k) { if (n == -1 && k == -1) break; // 根据题目要求，也可能是-1 ans = 0; memset(col_used, 0, sizeof(col_used)); // 初始化列标记数组 // 读入棋盘 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> board[i][j]; } } // 从第0行，已放置0个棋子开始深度优先搜索 dfs(0, 0); // 输出本组数据的答案 cout << ans << endl; } return 0; }

3.1 关键变量与初始化解析

• board[10][10]: 存储棋盘。题目给定n≤8，但通常我们会稍微开大一点（如10）以防边界问题，这是一个好习惯。
• col_used[10]:这是算法的核心状态变量之一。它是一个布尔数组，col_used[j] = true表示第j列已经被某个棋子占用。由于我们按行搜索，天然避免了同行冲突，所以只需要记录列冲突。
• ans: 累计所有合法方案数。注意，对于每一组新的输入数据，ans必须在计算前清零。
• memset(col_used, 0, sizeof(col_used)): 在每组数据开始前，必须清空列占用标记。忘记初始化是导致结果错误的一个常见原因。

3.2 DFS函数参数设计

dfs(int current_row, int placed_cnt)的参数设计体现了搜索的“状态”。

• current_row: 当前正在处理的行索引。它告诉我们搜索进行到了哪一步。
• placed_cnt: 当前已经成功放置的棋子数量。这是我们判断搜索是否成功（placed_cnt == k）的依据。

将状态作为参数传递，而不是使用全局变量，有时可以使逻辑更清晰。当然，使用全局变量cnt也是完全可行的，但要注意在回溯时正确地进行加减操作。

3.3 递归终止条件

两个终止条件至关重要：

1. if (placed_cnt == k) { ans++; return; }
   • 意义：只要棋子数达到k，就立即构成一个合法解。注意这里直接return，不再继续搜索当前分支。因为继续搜索只会添加更多棋子，而题目要求恰好k个。
2. if (current_row >= n) return;
   • 意义：已经搜索完所有行（从0到n-1），但棋子数还没达到k，说明这条路径不可能成功，直接返回。

顺序问题：必须先判断placed_cnt == k，再判断current_row >= n。为什么？考虑一种情况：当搜索到最后一行（current_row == n-1）时，放置了第k个棋子，此时placed_cnt先变成k，我们累加答案并返回。如果顺序反过来，先判断行号，就会错过这个在最后一行刚好凑齐k个棋子的解。

3.4 核心搜索逻辑：两个“选择”

这是整个算法的灵魂，对应搜索树的分支。

选择1：在当前行放置棋子

for (int col = 0; col < n; col++) { if (board[current_row][col] == '#' && !col_used[col]) { col_used[col] = true; dfs(current_row + 1, placed_cnt + 1); col_used[col] = false; // 回溯 } }

• for循环：遍历当前行的所有列，枚举所有可能的放置位置。
• if条件：必须同时满足两个条件——位置可用、该列空闲。
• “做出选择”三件套：
  1. 修改状态：col_used[col] = true。
  2. 递归深入：dfs(current_row + 1, placed_cnt + 1)，进入下一行，棋子数加1。
  3. 恢复状态：col_used[col] = false。这是回溯的关键，它保证了在尝试完“在这个位置放棋子”所衍生出的所有可能性之后，状态能恢复到之前的样子，以便进行下一个位置的尝试。

选择2：跳过当前行

dfs(current_row + 1, placed_cnt);

• 这一行代码非常简洁，但意义重大。它代表了“在当前行什么都不做”这个选择。
• 参数变化：行号+1，棋子数不变。
• 这个调用必须放在for循环之外。因为“跳过当前行”和“在当前行选一个位置放棋子”是并列的选择，而不是在遍历所有列之后才考虑。代码中的顺序（先处理放置，再处理跳过）不影响正确性，两者调换顺序也可以。

注意事项：dfs(current_row + 1, placed_cnt)这个调用可能会让初学者疑惑：“会不会导致无限递归？” 不会。因为current_row每次递归都在增加，最终会触发current_row >= n的终止条件。它的作用就是系统地探索“那些某些行没有棋子”的解空间。

4. 算法优化与剪枝策略

虽然本题数据规模（n≤8）很小，基础的DFS已经足够快，但掌握剪枝技巧是搜索算法的必修课。剪枝，就是在搜索过程中提前判断出某些分支不可能产生合法解，从而直接跳过，减少不必要的计算。

4.1 可行性剪枝

这是最直接的剪枝。在递归函数开头，我们可以增加一个判断：

void dfs(int current_row, int placed_cnt) { // 剪枝：即使后面所有行都放棋子，也无法达到k个 if (placed_cnt + (n - current_row) < k) { return; } // ... 原来的终止条件和搜索逻辑 }

• 原理：placed_cnt是已放棋子数，(n - current_row)是剩余的行数。因为一行最多放一个棋子（列不冲突），所以剩余行数就是理论上还能放置棋子的最大数量。如果已放 + 最大可放 < 目标k，那么这条路径绝对不可能成功，直接返回。
• 效果：当k相对n较小时，这个剪枝效果不明显。但当k接近n时，可以提前终止很多“前面棋子放得太少”的无用分支。

4.2 搜索顺序优化

本题的搜索顺序是按行进行的。这已经是一个很好的优化，因为它避免了同行冲突。对于按列搜索，原理也一样。对于更复杂的问题，有时对搜索顺序进行排序（比如先搜索选择少的分支）能更快地找到解或触发剪枝，但本题结构简单，按行或按列都是最优的。

4.3 状态压缩进阶

对于n≤8，我们可以用状态压缩来替代布尔数组col_used。用一个整数的二进制位来表示列的占用情况。例如，int state = 0，如果第j列被占用，就将第j位设为1 (state |= (1 << j))。判断第j列是否空闲：!(state & (1 << j))。

• 优点：位运算速度极快，并且传递状态（一个整数）比传递整个数组（或传引用）更方便。
• 缺点：代码可读性稍差，对初学者不友好。在竞赛中，对于n≤16的情况，状态压缩是常用技巧。

void dfs(int row, int placed_cnt, int col_state) { if (placed_cnt == k) { ans++; return; } if (row >= n) return; // 剪枝 if (placed_cnt + (n - row) < k) return; for (int j = 0; j < n; j++) { if (board[row][j] == '#' && !(col_state & (1 << j))) { dfs(row + 1, placed_cnt + 1, col_state | (1 << j)); } } dfs(row + 1, placed_cnt, col_state); // 跳过当前行 } // 初始调用: dfs(0, 0, 0)

5. 调试技巧与常见错误实录

即便思路清晰，实现时也难免踩坑。下面是我在教授这道题时，学生们最容易出现的几个错误。

5.1 错误：全局变量未重置

// 错误示例 int ans; void solve() { // 忘记了 ans = 0; dfs(0, 0); cout << ans << endl; }

• 现象：第二组及之后的数据结果错误，可能是上一组数据的答案累加了过来。
• 排查：检查所有全局状态变量（ans,col_used）是否在每组数据开始前正确初始化。
• 修正：在while(cin >> n >> k)循环体内，开头就执行ans = 0; memset(col_used, 0, sizeof(col_used));。

5.2 错误：回溯状态恢复不全

// 错误示例 void dfs(int row, int cnt) { if (cnt == k) { ans++; } // 忘记了 return， 会继续执行后面的代码，导致逻辑混乱 if (row >= n) return; for (int j=0; j<n; j++) { if (board[row][j]=='#' && !col_used[j]) { col_used[j] = true; dfs(row+1, cnt+1); // 忘记了 col_used[j] = false; // 致命错误！ } } dfs(row+1, cnt); }

• 现象：程序输出的答案远大于正确结果，甚至出现段错误（无限递归导致栈溢出）。
• 排查：仔细检查递归函数中，每次“做出选择”后，是否在递归调用后对称地“撤销选择”。特别是标记数组的恢复。
• 修正：确保每个dfs调用后，状态都恢复到调用前的样子。cnt如果是全局变量，也需要cnt--。

5.3 错误：遗漏“跳过当前行”的分支

// 错误示例 void dfs(int row, int cnt) { if (cnt == k) { ans++; return;} if (row >= n) return; for (int j=0; j<n; j++) { if (board[row][j]=='#' && !col_used[j]) { col_used[j] = true; dfs(row+1, cnt+1); col_used[j] = false; } } // 缺少了 dfs(row+1, cnt); }

• 现象：当 k < n 时，程序输出的答案比标准答案小。因为它只计算了“每行都放棋子”的方案，而漏掉了“某些行空着”的方案。
• 排查：确认递归函数中是否包含了“不选择”当前行的情况。这是本题最经典的陷阱。
• 修正：在for循环外部，添加dfs(row+1, cnt)调用。

5.4 错误：输入处理与边界条件

• 棋盘读入：注意棋盘是字符，中间没有空格。使用cin >> board[i][j]或scanf(“ %c“, &board[i][j])（注意%c前的空格用于过滤换行符）均可。
• 输入终止：题目要求是n==0 && k==0还是n==-1 && k==-1？务必看清题目描述，写错会导致程序无法正常结束或提前结束。
• 数组大小：虽然n≤8，但声明数组时习惯性开board[10][10]可以避免很多潜在的越界问题。

5.5 调试建议

1. 小数据测试：自己构造一个 2x2 或 3x3 的小棋盘，手工计算出所有方案，然后与程序输出对比。
2. 打印调试：在DFS函数入口和回溯点打印关键状态（行号、棋子数、列占用情况），观察搜索路径是否符合预期。

   void dfs(int row, int cnt) { printf(“进入dfs: row=%d, cnt=%d\n“, row, cnt); // ... 原有逻辑 printf(“回溯前: row=%d, cnt=%d\n“, row, cnt); }

3. 使用IDE调试器：单步执行，观察变量col_used数组的变化，是理解回溯过程最直观的方式。

6. 从棋盘问题到更广阔的搜索世界

彻底理解“棋盘问题”后，你会发现很多经典问题都共享同一套搜索回溯框架。

• 八皇后问题：可以看作是本题在 n=8, k=8，且棋盘全为‘#’，并增加了“对角线”约束的升级版。你需要用额外的数组来标记两条对角线是否被占用。
• 全排列问题：给定数字集合，生成所有排列。状态是当前已排列的序列，选择是剩余可用的数字。col_used数组在这里变成了digit_used，标记数字是否已使用。
• 组合问题：从n个数中选k个。状态是已选择的数字集合和起始索引（避免重复），选择是选当前数或不选当前数，其“选/不选”的结构与棋盘问题“放/不放”如出一辙。
• 子集问题：求一个集合的所有子集。这是k从0到n的所有组合问题的集合。

举一反三的要点：

1. 定义状态：你的DFS函数参数代表了什么？是位置索引、计数、还是某个位掩码？
2. 明确选择：在当前状态下，你可以做出哪些选择？（例如：放/不放，选/不选，用哪个数字）
3. 设计约束：哪些选择是非法的？（冲突条件，如列占用、数字已用、超出范围）
4. 实现回溯：对每一个合法选择，递归前修改状态，递归后必须恢复状态。

棋盘问题就像学习编程时的“Hello World”，它简单到足以让你看清搜索回溯的所有细节，又经典到其模式可以应用到无数场景。我建议在AC这道题后，不要停下，立刻去尝试“八皇后”、“全排列”、“组合总和”这些问题。你会惊讶地发现，当初觉得晦涩难懂的算法，现在已经成了你手中顺手的工具。算法的学习就是这样，攻破一个核心模型，就能打开一片新的天地。当你再遇到类似“在约束条件下寻找所有可能解”的问题时，第一反应就应该是：“这能不能用DFS+回溯来解？” 这时，你就真正入门了。