企业官网建设流程全解析

聊到"棋盘问题"，很多刚刷题的朋友第一反应是八皇后。但如果你在OJ上搜过这个标题，最常见的其实是另一道经典搜索题：一张n行n列、局部区域不能落子的棋盘上摆k颗棋子，要求任意两颗棋子不能在同一行或同一列，统计所有可行的摆放方案。这类题看着简单，却是DFS回溯里最典型的模板，后面碰到的N皇后、迷宫计数、连通块染色，追根溯源都是同一套状态设计。这篇文章用C++把这道题从代码到剪枝到复杂度全部拆开讲清楚，顺便把几个叫"棋盘问题"的兄弟题型一起比一比。不论你是刚入门递归，还是准备面试前想快速拾起搜索套路，这份笔记都值得过一遍。

1. 先把这个"棋盘问题"说清楚

1.1 名字相同，考法不同的三类棋盘题

先从名字下手。市面上的"棋盘问题"大致有三个指向：

第一个是搜索回溯型的摆放问题，也是本文主角。输入一个n行n列棋盘，有些格子标'#'表示可放棋子，有些标'.'表示不可放，再给一个整数k，要求在可放格子里摆k个棋子，任意两颗棋子不能在同一行、同一列，输出方案数。这个变体在很多基础题库里就叫"棋盘问题"，不少经典教材和训练题目都用这个名字。

第二个是棋盘覆盖问题，输入是2^k乘2^k的棋盘，其中有一个特殊方格位置已知，要求用若干L型骨牌（三格L形）把除特殊方格外的所有格子覆盖完整，输出一种覆盖方案。这个问题的标准解法是分治，跟DFS回溯完全是两码事。

第三个是棋盘路径计数类的题，比如从棋盘左上角走到右下角，只能向右向下走，问走法总数，或者骑士走棋盘到达某格的最少步数。这类问题本质是DP或者BFS。

之所以要把这三个区分开，是因为新手拿到题名很容易套错模板。我见过不少人把覆盖题当成搜索题写半天，或者把路径计数题硬上DFS导致超时。做题之前先确认题目问的是方案存在性、方案数量还是最短路径，这是第一步。

1.2 为什么这类题用C++最顺手

搜索回溯这类题，C++有天然优势：递归调用开销可控，STL容器虽然用得不多但vector和stack在需要时很省事，位运算直接操作int可以做状态压缩，输入输出用cin加sync配置后足够快。更重要的是，大部分测评环境对C++的代码量上限和运行时限都比较宽松，DFS这类写法只要剪枝到位，能跑到n等于8到10的规模。

我个人的习惯是：搜索题一律先把棋盘存成char数组或vector，状态用bool数组加int计数，先求正确再谈优化。C++里char board[12][12]这种静态数组因为内存连续，遍历起来比vector稍微快一点，对回溯这种高频循环有微小优势。不过用vector也没什么问题，差距在n很小的时候完全可以忽略。

2. 算法核心：DFS回溯如何设计状态与剪枝

2.1 搜索树长什么样，为什么要按行推进

摆放题最直观的想法是枚举每个格子放不放，但那样复杂度是2的n平方次方，n等于8就是2的64次方，直接爆炸。聪明的做法是观察约束条件：任意两颗棋子不能同一行。这个约束意味着每一行最多只能放一颗棋子，那就可以按行去推进。

按行推进的思路是：递归函数处理第row行时，这一行要么不放棋子，要么在某一个可放且列未占用的格子放一颗，然后跳去处理row+1行。这样一来，行维度天然不会冲突，剩下只需要用数组记录哪些列已经被占用了。搜索树的深度是行数n，每一层的分支数取决于当前行可用列数，整体复杂度就从指数爆炸降到了可接受的组合级别。

为什么不能按列再套一层？因为行推进已经覆盖了所有可能摆放，列约束是用占用数组控制的，再按列枚举会重复计数。比如先放第0行第2列，再放第1行第0列，和反过来放，摆放方案其实不同，但按行推进时顺序固定，每颗棋子对应唯一行号，所以不会出现同一方案被重复数两次的情况。这是回溯题最需要注意的"排序问题"。

2.2 状态记录：列占用数组就够了

核心状态有三个维度：当前处理到哪一行row、已经放下了几颗棋子placed、哪些列已经被占用。第三维用一个bool数组usedCol就能表达。

因为约束只有"不能同一列"，没有对角线要求，所以不需要像N皇后那样额外维护两条斜线数组。棋盘上不可放的格子，在枚举列时用board[row][col]等于'#'来判断即可。这三个状态足以唯一确定一条搜索路径，回溯时只需要复位usedCol[col]就好。

这里有个容易忽略的细节：行内已经决定了这一行最多放一颗，所以dfs(row+1, placed+1)是在循环内部对每一个满足条件的列执行一次，而不是在循环外。如果写成先选列再统一递归，就需要额外保存选中的列号，代码会啰嗦很多。按行推进配合循环枚举列，是这类题最清爽的写法。

2.3 两个剪枝让搜索量下降一个量级

基础版递归虽然正确，但n等于8、k等于8时会展开8的阶乘规模的路径，因为全可用棋盘上每行都能放。这时候如果目标棋子数k小于行数n，比如n等于8、k等于3，很多递归分支走到后面会发现行数不够放满棋子，白白搜索了一大片。

第一个剪枝：如果剩余未处理的行数加上当前已放棋子数都凑不够k，直接返回。写成代码就是if (n - row < k - placed) return。这个剪枝在k接近n时作用不大，但在k远小于n时能把无用分支砍掉一大半。

第二个剪枝：如果某行没有任何可放格子，或者可用列都被占满，循环自然为空，递归自动退化成纯跳过行。这不算代码上的剪枝，但说明搜索树的实际大小和棋盘上的'#'密度强相关。有些同学跑大数据时怀疑代码有bug，其实只是棋盘本身限制大，搜索分支少，输出答案较小而已。

这两个剪枝不需要额外空间，成本是一次减法比较或循环为空，收益率很高。

3. C++实现逐段拆解

3.1 完整一版能直接提交的代码

下面这段是我日常在OJ上提交的版本，经过多次修改，边界和性能都比较稳。

#include <bits/stdc++.h> using namespace std; char board[12][12]; bool usedCol[12]; long long answer; int n, k; void dfs(int row, int placed) { if (placed == k) { ++answer; return; } if (row >= n) return; if (n - row < k - placed) return; dfs(row + 1, placed); for (int col = 0; col < n; ++col) { if (board[row][col] == '#' && !usedCol[col]) { usedCol[col] = true; dfs(row + 1, placed + 1); usedCol[col] = false; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); while (cin >> n >> k) { if (n == -1 && k == -1) break; for (int i = 0; i < n; ++i) { cin >> board[i]; } answer = 0; memset(usedCol, 0, sizeof(usedCol)); dfs(0, 0); cout << answer << '\n'; } return 0; }

这段代码做了几件事：先用while读入多组数据，遇到n和k同时为-1时退出；棋盘按字符串整行读入，正好对应每行一个长度为n的字符串；每次case前重置answer和usedCol；然后从第0行开始深度搜索。

数组开成12乘12而不是刚好n，是为了避免某些题目边界描述不清导致越界。字符数组直接cin >> board[i]不需要处理换行符，比用getline简洁，也不容易踩残留换行的坑。答案类型我用long long，防御一下数据范围，后面会细说。

3.2 函数里每个参数和边界为什么这么写

dfs(row, placed)有两个参数，分别代表当前扫描到的行号和已经放置的棋子数。终止条件有两个：placed等于k说明当前路径已经凑够棋子，这是一个合法方案，answer加一后返回；row大于等于n说明行已经扫完但没凑够，返回。这两个条件的顺序很讲究，必须先判断placed，否则可能出现"放完最后一颗棋子的同时也扫描到了第n行"这种边界情形，把正确答案漏掉。

我之前写过一版把判断顺序写反的代码，结果n等于8、k等于8时答案始终是0，排查了很久才发现是这个问题。建议大家都把placed等于k的判断放在最前面。

剪枝条件n - row < k - placed放在两个终止条件之后、正式展开搜索之前，只有行数真的不够才返回，不会误伤合法分支。最后一个不放棋子的递归dfs(row + 1, placed)必须写在循环外面，它代表"当前行完全跳过"这一种选择，和"当前行选某一列放一颗"是两种独立分支。如果漏写这个分支，k小于n的时候方案数就会少一大截。

3.3 位运算加速版写法

如果想把搜索状态压缩成一个整数，可以这样写：

void dfs(int row, int placed, int colMask) { if (placed == k) { ++answer; return; } if (row >= n) return; if (n - row < k - placed) return; dfs(row + 1, placed, colMask); for (int col = 0; col < n; ++col) { if (board[row][col] == '#' && !(colMask & (1 << col))) { dfs(row + 1, placed + 1, colMask | (1 << col)); } } }

colMask的第col位为1表示该列已被占用，放置时用按位或写下占位，回溯时因为是按值传递，colMask实体不会变，不需要手动复位。这个版本在n小于等于10的棋盘上跟bool数组版跑起来几乎一样快，但好处是状态可以整体拷贝，未来如果要加记忆化，可以直接把colMask作为状态键。n大于等于12以后，棋盘本身的搜索空间已经非常大，位运算的优化不足以救回指数级复杂度，这时候应该回头检查剪枝或者考虑换算法。

3.4 一个具体例子：n=4、k=2全可用棋盘的手动推演

拿最简单的全可用4乘4棋盘放2颗棋子来走一遍递归。从dfs(0,0)开始，第一分支是第0行不放，直接进入dfs(1,0)；第二分支是第0行放，有4个列可选，每种情况进入dfs(1,1)。在dfs(1,1)里又可以第1行不放，或者在剩余3个未占列中选一列放，一旦placed到2就计数。整个过程会把所有满足不同行不同列的二元摆放全部枚举出来，数量正好是12。

而如果棋盘上某些格子是点号不可放，比如第0行只有两格可用，那么第0行放棋子的分支就只有两个，而不是四个，搜索树自然变窄。手动推一遍这个小例子的好处是，当你怀疑程序输出结果不对时，能用笔算出小规模答案来对照。

4. 复杂度分析与性能实测

4.1 最坏情况有多恐怖

这个问题的复杂度不太好用单一公式拍死，因为可用格子密度和k的大小共同决定搜索树宽度。最坏情况是棋盘全可用、k不超过n，此时每层的可用列递减，方案数等于排列数P(n,k)，也就是n的阶乘除以(n-k)的阶乘。比如n等于8、k等于8时，答案就是40320，遍历次数大致也在几万量级，非常快；n等于10、k等于10时答案是3628800，递归调用次数大约在千万量级，C++跑下来大约零点几秒到一两秒。

比这个再大的n等于12、k等于12，答案接近4.79亿，递归次数就是数十亿次，即便C++单次调用很轻，也会直接超时。所以这种裸DFS只适用于n小于等于10的常见数据范围，如果n更大，就要上记忆化搜索或者根据题目条件换思路。

实际棋盘因为存在大量点号不可放，搜索树会比全可用小很多。比如半数格子不可放，宽度近似砍半，总体时间能降一个量级，这也是为什么不少题目把n设到8还要求多case，裸搜索依然能过。

4.2 不同规格棋盘的真实运行时间

为了让数据有说服力，我在本机用release模式跑了一组简单的计时测试，棋盘全可用，k等于n，结果如下。

这个表说明两个问题：一是n小于等于10基本无压力；二是k等于n时剪枝的if (n - row < k - placed)永远为假，起不到任何作用，复杂度完全由排列数决定。如果k只有n的一半，剪枝会显著减少遍历，但即便剪掉了后半段的搜索，前半段的组合分支依然存在。

4.3 空间占用为什么可以忽略

整份代码的空间只包括board数组、usedCol数组以及递归栈。char board[12][12]是144字节，bool数组12字节，递归深度最多n层，每一层栈帧保存row、placed和局部变量，合起来不过几百字节。就算开成100乘100的棋盘，只要n不超过DFS能承受的范围，空间都不是瓶颈。真正值得关注的是时间，不是空间。

递归栈的另一个潜在风险是极端数据下爆栈。但n小于等于10时深度最多10层，离系统栈上限十万八千里，完全不用担心。只有把DFS思路硬套到n等于1000的棋盘上，才会因为深度太深导致栈溢出，那种题目一看就应该换BFS或DP。

5. 三个常见变体怎么迁移

5.1 N皇后：只多两条对角线

N皇后问题的约束除了不同行不同列，还要求不能在同一条对角线上，所以状态里除了usedCol数组，还要加两个对角线数组。对角线有两个方向：row加col相同说明同在一条从左上到右下的斜线，row减col加n相同说明同在一条从左下到右上的斜线。因为row减col可能是负数，统一加n偏移到非负下标。

代码只改一个循环判断：

void dfs(int row) { if (row == n) { ++cnt; return; } for (int c = 0; c < n; ++c) { int d1 = row + c; int d2 = row - c + n; if (!usedCol[c] && !usedDiag1[d1] && !usedDiag2[d2]) { usedCol[c] = usedDiag1[d1] = usedDiag2[d2] = 1; dfs(row + 1); usedCol[c] = usedDiag1[d1] = usedDiag2[d2] = 0; } } }

这就是从"棋盘问题"到"N皇后"的最直接迁移路径。学会了摆放题的按行推进，N皇后只等于多维护两个数组。反过来，如果你先把N皇后写熟了，再回头看棋盘问题会觉得它更简单，因为少了斜线判断。

5.2 棋盘覆盖：搜索题变分治题

棋盘覆盖问题的标准解法和搜索没什么关系，但很多人误以为要暴力尝试每种L型骨牌摆法。其实它的核心观察是：2^k乘2^k的棋盘去掉一个特殊方格后，剩余格子数恰好是4^k减1除以3，正好能被3格L型骨牌整除。分治思路是每次把棋盘切成四个2^(k-1)的小棋盘，特殊方格落在其中一个区域，另外三个区域各留一个相邻中心位置的缺口，用一块L型骨牌盖上，然后递归处理四个子区域。

特殊方格初始化时我习惯设置成-1，骨牌编号从1开始，这样输出棋盘时0表示尚未覆盖的空格，-1是特殊位置，其他数字表示哪一块骨牌覆盖。核心代码骨架如下：

int board[1024][1024]; int tile; void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = ++tile; int s = size / 2; if (dr < tr + s && dc < tc + s) { chessBoard(tr, tc, dr, dc, s); } else { board[tr + s - 1][tc + s - 1] = t; chessBoard(tr, tc, tr + s - 1, tc + s - 1, s); } if (dr < tr + s && dc >= tc + s) { chessBoard(tr, tc + s, dr, dc, s); } else { board[tr + s - 1][tc + s] = t; chessBoard(tr, tc + s, tr + s - 1, tc + s, s); } if (dr >= tr + s && dc < tc + s) { chessBoard(tr + s, tc, dr, dc, s); } else { board[tr + s][tc + s - 1] = t; chessBoard(tr + s, tc, tr + s, tc + s - 1, s); } if (dr >= tr + s && dc >= tc + s) { chessBoard(tr + s, tc + s, dr, dc, s); } else { board[tr + s][tc + s] = t; chessBoard(tr + s, tc + s, tr + s, tc + s, s); } }

这段题的复杂度是O(n的平方)，因为每个格子恰好被覆盖一次，分治的四次递归隐含遍历了整块棋盘。和DFS摆放题完全不同，但代码量其实差不多，都是十行以内的核心函数。遇到这类题时，关键不是搜索，而是理解特殊方格所在的象限和其他象限如何借助中心骨牌衔接。

5.3 走棋盘路径：DFS换成递推DP

还有一类"棋盘问题"是说从左上角走到右下角，只能向右向下，问路径数，或者带障碍物后有多少种走法。如果棋盘规模是几百乘几百，DFS显然不行，但递推非常优雅：

vector<vector<int>> dp(n, vector<int>(m, 0)); dp[0][0] = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j] == 1) continue; if (i > 0) dp[i][j] += dp[i - 1][j]; if (j > 0) dp[i][j] += dp[i][j - 1]; } }

递推时dp[i][j]只依赖上方和左侧，所以可以把二维压成一维滚动数组。这个问题的记忆点在于：只要状态可以按层推进、且不会产生环，就用DP；只要每一步会回头或者需要全局路径搜索，才用DFS。判断标准简单粗暴，能解决很多新手纠结"这题该用DFS还是DP"的问题。

5.4 快速分类口诀

我自己的经验是拿到题目先看数据范围。n在8到10左右，问方案数，棋子之间互相排斥，优先DFS回溯。棋盘规模到几千，问方案数且走法只向前不回头，优先DP。棋盘是2的幂次，问L型骨牌覆盖，想都不想直接分治。这样分类之后，代码模板基本可以套着用，剩下就是根据题目条件加细节。

6. 调试实录与避坑指南

6.1 三个经典症状速查表

我自己带人刷题时，最常看到的就是下面几类bug，直接做成速查表。

这里特别强调第二类：很多同学最初会以为"放棋子"已经包含了不放的情况，但实际上递归树必须有"跳过当前行"这个分支，k小于n时才会产生正确方案。我曾亲眼看到有人花一下午找bug，最后就是一行dfs(row+1, placed)的事。

6.2 排查工具：打印棋盘和分支

当答案不对时，我的习惯是先写一个临时打印函数，把当前棋盘和已选列打印出来。在answer加一的位置打印当前摆放，用人类可读的棋盘样子比单纯看数字变量直观得多。也可以加一个depth参数，用缩进显示递归层级，这样能立刻看出来有没有走重复路径。

void printCurrentBoard() { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cout << (usedCol[j] ? '#' : '.'); } cout << '\n'; } }

这类临时代码调试完成就删掉，不要留在提交版本里。另外，小数据手工验证很关键，n等于4、k等于2的全可用棋盘，答案应该是12，如果你程序在最小case上跑不对，就不要继续拿大数据测性能，问题一定是逻辑性的。

6.3 多case输入的两个坑

棋盘问题通常是多case输入，直到n和k同时为-1结束。第一个坑是换行符残留：如果第一行用cin读取n和k，后面用getline读棋盘，残留的换行会被当成一行，导致棋盘整体错位。解决办法要么整段都用cin >> board[i]，要么在getline之前用cin.ignore()清掉缓冲区。第二个坑是数据重置：每组case之间必须把answer归零、usedCol数组清空，否则上一组的答案会叠加到下一组。board数组其实不用每次清空，因为输入会完整覆盖n行，但这个习惯并不坏。

我提交前还会养成一个习惯：把输入样例整段复制，而不是肉眼敲进去。肉眼敲最多错两个字符，还能看，但那种错位问题会浪费半小时。用文件重定向跑一组自己构造的小样例，往往是发现边界问题的最快方式。

到这里，DFS版棋盘问题从算法状态设计、剪枝到C++实现和调试已经全部分析完了。我个人觉得，这道题的价值不在题目本身，而在于它把"按行推进加占用数组加回溯复位"这条搜索主线练得很透。带新人练这个题时，我通常会让对方先把全可用棋盘n等于4、k等于2的12种方案手动画出来，再对着程序输出验证一遍。

最后再分享一个小技巧：如果OJ时限紧张，把cin换成scanf、把答案在n等于13以后可能超过int上限，直接把计数类型定义成long long，这些微调能解决不少意外问题。尤其是方案数在n等于10、k等于10时已经超过300万，n到了13以后可能超过int上限，建议直接定义成long long计数的类型，否则测试点悄悄溢出时会让你排查到怀疑人生。