前阵子在评论区看到有人讨论第36题到底算不算“简单题”，我的看法是：它表面上是一个模拟题，但真正把它吃透的人并不多。这道题核心不是“怎么判断重复”，而是“怎么把一行、一列、一个3x3九宫格这三层约束，在一个遍历里干净地表达出来”。如果你正准备面试，或者刚开始刷题想找一道既能练手又能学到细节的题目，这道题非常合适。这篇笔记我打算把暴力解法、布尔数组解法和位运算解法都过一遍，重点是讲清楚两件事：九宫格坐标公式(i / 3) * 3 + j / 3到底怎么来的，以及“先查再标记”的顺序为什么不能反过来。
1. 题目到底在考什么：不是“查重”，是“状态管理”
1.1 题干解读与常见误区
题目给了一个9 x 9的棋盘，里面有一部分格子已经填上了数字1-9，剩下的是'.'表示空格。要求判断：每一行里有没有重复数字、每一列里有没有重复数字、每个3 x 3小宫格里有没有重复数字。如果有任何重复，就返回false，否则返回true。
这道题有一个容易混淆的地方：它只是“校验”，不是“求解”。也就是说，我们不需要去填数字，也不需要去回溯尝试每一种可能性，只需要判断当前这个盘面是否符合数独规则。很多第一次接触的人会把思路往“搜索”上带，结果把自己绕进去了。把“校验”和“求解”分开，后面才会走得顺。
常见的误区有两个。第一个是只检查行和列，忘了九宫格。第二个是知道要检查九宫格，但不知道怎么优雅地拿到某个格子属于第几个九宫格。第一个问题好解决，想清楚就行；第二个问题是大多数人的真实卡点，后面的章节我会专门拆开讲。
1.2 换一个视角：从“按维度遍历”到“按格子录入”
大多数人第一反应是：先遍历所有行查一遍重复，再遍历所有列查一遍重复，再遍历所有九宫格查一遍重复。这个思路没毛病，逻辑也正确，但写出来的代码是三段几乎相同的逻辑，很容易在某一段里漏掉条件或者写错边界。比如“按宫检查”时，要自己手算每个宫格的起始坐标，代码会变得又长又丑。
更好的方式是反过来：把整个棋盘上的 81 个格子逐个遍历，每遇到一个数字，就同时去三个“台账”里查重。行台账记录这一行出现过哪些数字，列台账记录这一列出现过哪些数字，宫台账记录这个宫格出现过哪些数字。只要其中任何一个台账显示“这个数字我已经见过了”，就直接判非法。
这样做的本质是把“查重”变成了“状态录入”：每处理一个格子，同时更新三个维度的状态。代码只需要写一次判断逻辑，而不是写三遍。这个视角的转变，比单纯背一套模板更重要。
2. 三种直接解法：暴力遍历、布尔数组、位运算
2.1 暴力解法：能过，但不够干净
先不追求最优，第一时间能想到的暴力写法是分三段独立检查。
// 结构示意，不推荐直接这么提交 for (int i = 0; i < 9; ++i) { unordered_set<char> seen; for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') continue; if (seen.count(board[i][j])) return false; seen.insert(board[i][j]); } } // 再对每一列做同样的事情 // 再对每一个3x3宫格做同样的事情这版代码能通过测试，因为题目固定是9 x 9的棋盘，无论怎么写，遍历上限都是 81 个格子，时间复杂度都是常数级别。但问题也显而易见：重复代码太多，尤其在“按宫检查”那段，如果不用循环而是手写 9 个宫格的起始坐标，非常容易出错。我个人建议是：暴力解法只用来帮助理解题意，真正上提交或者讲给面试官听，最好还是用后面的统一遍历方案。
2.2 布尔数组方案：一眼能看懂的常规写法
这种写法的核心是用三个固定的二维布尔数组来记账：
rows[i][num]表示第i行里，数字num是否出现过；cols[j][num]表示第j列里，数字num是否出现过；boxes[idx][num]表示第idx个宫格里，数字num是否出现过。
数组第二维我习惯开成10，这样可以直接用数字1-9当作下标，不用每次再减一个偏移量。虽然下标0会浪费掉，但换来的是代码更好读，这个取舍非常划算。
#include <vector> using namespace std; class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { bool rows[9][10] = {}; bool cols[9][10] = {}; bool boxes[9][10] = {}; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { char c = board[i][j]; if (c == '.') continue; int num = c - '0'; int boxIdx = (i / 3) * 3 + j / 3; if (rows[i][num] || cols[j][num] || boxes[boxIdx][num]) { return false; } rows[i][num] = true; cols[j][num] = true; boxes[boxIdx][num] = true; } } return true; } };用一个具体例子走一遍。假设board[0][0] = '5'，那么num = 5，boxIdx = 0。此时三份台账里都还没有数字 5 的记录，于是把rows[0][5]、cols[0][5]、boxes[0][5]都置为true。接着遍历到board[0][1] = '5'，在查rows[0][5]时发现已经是true，立刻返回false。
这里有一个值得注意的细节：为什么用布尔数组而不是真正的哈希集合？因为数字范围固定且很小，只有 1 到 9。数组下标的天然哈希能力已经足够，完全没有必要引入unordered_set的开销。面试中如果被追问“你这里为什么不用哈希表”，你要能答出这一点。
三种方案的复杂度对比如下：
| 方案 | 时间复杂度 | 空间复杂度 | 代码可读性 |
|---|---|---|---|
| 暴力三层遍历 | O(1) | O(1) | 一般，重复代码多 |
| 布尔数组 | O(1) | O(1) | 最好，结构清晰 |
| 位运算 | O(1) | O(1) | 依赖个人对二进制的熟悉度 |
这里的 O(1) 都是因为棋盘固定为 9x9，格子数量上限是 81，不会随着输入规模变化。
2.3 位运算方案：把一行状态装进一个整数
如果你已经看过一些高手的题解，可能会遇到位运算版本。思路是：用一个整数的低 9 位，分别代表数字 1 到 9 是否出现过。如果某一位是 1，说明这个数字已经出现过；如果是 0，说明还没出现。
#include <vector> using namespace std; class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { int rows[9] = {}; int cols[9] = {}; int boxes[9] = {}; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { char c = board[i][j]; if (c == '.') continue; int num = c - '0'; int mask = 1 << num; int boxIdx = (i / 3) * 3 + j / 3; if ((rows[i] & mask) || (cols[j] & mask) || (boxes[boxIdx] & mask)) { return false; } rows[i] |= mask; cols[j] |= mask; boxes[boxIdx] |= mask; } } return true; } };判断是否重复时，先做按位与。如果rows[i] & mask的结果不是 0，说明第num位已经被置为 1，也就是这一行已经出现过num。没有重复时，用按位或把这个数字的状态记录下来。
这个写法的内存只有三个长度为 9 的整数数组，每个整数只用到 9 个比特位，非常省空间。但我得说实话：位运算版本更适合在刷题笔记里作为进阶理解，不太适合作为面试中的首选答案。因为不是所有面试官都能第一时间看懂这种写法，你还要花额外的时间去解释每一行位运算的含义。更好的策略是：先讲布尔数组方案，如果面试官追问“空间还能再优化吗”，再展示位运算思路，这会显得你理解得足够深。
3. 九宫格编号：公式推导与坐标映射细节
3.1(i / 3) * 3 + j / 3到底是怎么凑出来的
很多题解会直接给你这个公式，但你照着写完之后，并不知道它为什么是对的。下次再遇到坐标转换的题，依旧容易卡壳。其实这个公式不需要背，完全可以现场推出来。
我们给九宫格编号，按从左到右、从上到下的顺序，编成 0 到 8。现在有一个格子，行是i，列是j。先看行方向：i / 3得到的是这个格子落在第几“横带”。i取 0、1、2 时，i / 3 = 0，属于最上面一行宫格；i取 3、4、5 时，属于中间一行；i取 6、7、8 时，属于最下面一行。所以i / 3的实际含义是“宫格的行组号”。
每一行宫格组里有 3 个宫格，编号分别为行组号 * 3 + 0、行组号 * 3 + 1、行组号 * 3 + 2。因此基础偏移量是(i / 3) * 3。再看列方向：j / 3得到的是这个格子落在第几“纵带”。j取 0、1、2 时，j / 3 = 0，表示在宫格的左列；取 3、4、5 时，是中间列；取 6、7、8 时，是右列。所以最终编号就是基础偏移量加上列组号。
打个比方，把宫格编号想象成电影院座位：先根据行数确定你坐在第几排大区域，再根据列数确定你是这片区域的左侧、中间还是右侧。两步一合，位置就唯一确定了。
如果记不住这个推导也没关系，你在草稿纸上画一个 3x3 的宫格编号表，填上 0 到 8，然后看任何一个格子，都能迅速验证公式。多推两遍，比硬背要牢固得多。
3.2 坐标映射示例和常见误写
为了确认公式正确，可以选几个特殊坐标代入计算。
| 格子坐标 (i, j) | i / 3 | j / 3 | (i / 3) * 3 + j / 3 | 所在位置 |
|---|---|---|---|---|
| (0, 0) | 0 | 0 | 0 | 左上宫格 |
| (2, 2) | 0 | 0 | 0 | 左上宫格 |
| (3, 0) | 1 | 0 | 3 | 左中宫格 |
| (4, 4) | 1 | 1 | 4 | 正中宫格 |
| (5, 8) | 1 | 2 | 5 | 右中宫格 |
| (6, 0) | 2 | 0 | 6 | 左下宫格 |
| (8, 8) | 2 | 2 | 8 | 右下宫格 |
这里最常见的误写是(j / 3) * 3 + i / 3，也就是行列弄反。举一个具体的反例：坐标(1, 7)，正确结果应该是(0) * 3 + 2 = 2，也就是右上角那一行中间偏右的宫格。如果把公式误写成(j / 3) * 3 + i / 3，得到2 * 3 + 0 = 6，直接跳到左下区域去了，差得十万八千里。
如果你写完代码心里没底，可以在循环里临时加一行调试输出，打印每个数字格子对应的boxIdx，配合一个手画的宫格编号表逐个核对。这种笨办法在起步阶段非常有效。
3.3 不用公式的替代写法：按宫格为单位遍历
如果你确实不喜欢这个公式，还有另一种等价写法，适合在初学时用来辅助理解：四重循环，先按宫格编号遍历，再在这个宫格内部遍历三行三列。
// 结构示意：按宫遍历，每个宫格内再走 3x3 for (int box = 0; box < 9; ++box) { int startRow = (box / 3) * 3; int startCol = (box % 3) * 3; bool seen[10] = {false}; for (int r = startRow; r < startRow + 3; ++r) { for (int c = startCol; c < startCol + 3; ++c) { char ch = board[r][c]; if (ch == '.') continue; int num = ch - '0'; if (seen[num]) return false; seen[num] = true; } } }这段代码只能验证九个宫格内部的情况，还需要再配一个行检查和一个列检查，才能覆盖完整流程。所以它更适合作为“理解宫格坐标”的辅助代码，不适合作为最终提交的最优结构。我的建议是：讲解思路时可以用四重循环来给对方建立直觉，提交代码时还是用统一的单层双循环加公式，代码最简洁。
4. 复盘最容易翻车的几个点，以及代码走读
4.1 “先查再标记”的顺序，说反就会凉
这是我在评论区和同事的代码评审里见到最多的问题。正确的逻辑是：先检查三个台账里有没有出现过这个数字，如果出现过就直接返回false，否则再把这个数字标记为“已出现”。
如果把顺序写成先标记再检查，会发生什么？第一个格子board[0][0] = '5'，你先把rows[0][5]改成true，然后才去检查rows[0][5]，发现是true，直接返回false。也就是说，自己刚写上去的记录立刻把自己出卖了，哪怕整盘数独完全合法，也会被误判成非法。这种逻辑错误在没有覆盖到同类样例的时候很难发现，因为它只会在“第一个数字恰好出现在合法位置”时触发误报。
写代码时把检查放在前面，标记放在后面，这个顺序应该形成肌肉记忆。
4.2 字符转换和下标的坑
棋盘里的元素类型是char，不是int。'5'对应的 ASCII 码是 53，如果你直接拿board[i][j]去当数组下标，轻则数据错乱，重则数组越界。必须先执行int num = c - '0'，把字符数字转成真正的数值数字。
另一个容易忽略的地方是'.'的处理。没有跳过空格的话，'.' - '0'会得到一个负数，后面的数组访问就全乱了。正确做法是在拿到字符之后第一时间判断：如果是'.'，直接continue，不参与任何记账。
还有一个细节：题目默认输入一定是合法的 9x9 棋盘，字符只可能是数字或'.'，所以不需要做额外校验。但如果你把这道题的逻辑放进实际工程里，就不能这么乐观了，至少应该先验证board.size()以及每一行的长度。竞赛和面试场景可以大胆假设，工程代码不能。
4.3 空间复杂度的面试回答和自测用例设计
关于复杂度，面试官偶尔会追问“你的算法空间复杂度是多少”。这里有一个容易答错的点：棋盘是题目限定死的 9x9，所以无论是三个长度为 9 的数组，还是布尔数组，空间都可以说是 O(1)。你不用纠结“如果棋盘变成更大怎么办”，因为这道题的输入约束就决定了规模是固定的。回答时可以直接说：由于棋盘固定，时间上最多遍历 81 个格子，空间上也是三个固定大小的数组，所以时间和空间都是常数级。
自测用例也值得认真设计，不然你把代码写完后，很难判断到底有没有覆盖到三个维度。我个人习惯构造以下几个用例：
- 全空棋盘：所有格子都是
'.'，应该返回true。这个用例主要用来验证代码不会因为空值报错。 - 行冲突：
board[0][0] = '5'，board[0][1] = '5'，其余全空，应该返回false。 - 列冲突：
board[0][0] = '5'，board[1][0] = '5'，其余全空，应该返回false。 - 宫格冲突：
board[0][0] = '5'，board[1][1] = '5'，虽然不同行也不同列，但它们在同一个3x3宫格里，应该返回false。 - 跨宫格不冲突：
board[0][0] = '5'，board[0][3] = '5'，两个格子不在同一行宫格，也不再同一列宫格，应该返回true。
把这些用例在本地跑一遍，基本就能确定三个维度的检查都写对了。至于那种“只检查行和列，忘掉宫格”的典型错误，第 4 个用例一眼就能揪出来。
我个人在刷这一题时最大的体会是：它真正想考察的不是某个惊为天人的算法，而是你愿不愿意把“查重”这个动作组织得干净、不重不漏。如果能亲手把布尔数组和位运算两个版本都写出来，并且对着面试官把(i / 3) * 3 + j / 3推导一遍，这道题才算真正变成了你自己的东西。
