企业官网建设流程全解析

上周末在数据库技术社群里看到有人转发一条赛报：SQL编程大赛的第5名选手周仟荣，用一套基于PostgreSQL位运算的思路解决了数独问题，据说还“碾压”了同场不少PL/pgSQL存储过程方案。说实话，我看到标题的第一反应是怀疑——SQL写数独求解器？这东西在SQL里怎么表达回溯搜索？位运算又是怎么跟数独扯上关系的？

直到我把这位选手提交的SQL完整跑了一遍，才意识到这方案是真有点东西：不到80行的单条WITH RECURSIVE查询，既没有写存储过程，也没有用外部扩展，纯靠PostgreSQL原生能力把数独求解压缩成了“能直接执行的SQL语句”。我后来把这个思路拆解、重构、加注释，又跑了几十个不同难度的谜题，稳定性出乎意料地好。这篇文章就把整套东西摊开讲清楚：数独在SQL里怎么建模、位运算为什么是天然匹配、递归CTE怎么模拟回溯搜索，以及我在复现过程中踩过的几个坑。适合对SQL进阶语法有兴趣、想理解位运算实战应用的读者，也适合想给数据库编程打开思路的朋友。

1. 问题拆解：数独为什么适合用SQL加位运算

1.1 数独本质：约束传播加搜索

数独是一个9乘9的方阵，每个格子填1到9，要求每一行、每一列、每个3乘3宫格内都不重复。给定一部分已经填好的数字，剩下的空格需要推理填满。

从算法角度讲，数独就是一个典型的约束满足问题：约束是“同一行/列/宫格内数字互斥”，目标是找到满足全部约束的完整棋盘。求解方法通常分两层——先用约束传播把能确定的格子全部确定掉，再对剩余空格做深度优先搜索，也就是回溯。

传统的PL/pgSQL实现会怎么写？先建一张表存81个格子的状态，写一个循环扫描空格，对每个空格检查同行、同列、同宫里已经出现过的数字，再递归或迭代填数。代码量少说一两百行，而且大量使用循环和临时表，逻辑一复杂就难以维护。

这里有个关键问题：对数独而言，“一个空格还能填哪些数字”这个信息，本质上是一个数字集合。比如某空格当前位置不允许填2、5、7，那么它的候选集合就是{1,3,4,6,8,9}。集合运算在SQL里恰恰是最擅长的事情之一——只不过常规思路会用子查询和NOT EXISTS去算，效率不高。

1.2 常规SQL解法为什么慢

用一个直观的类比来解释：假设你要查“某个空格还能填哪些数”，最朴素的思路是“收集同行、同列、同宫里所有已填数字，然后从1到9里排除掉这些数字”。在SQL里，你需要对每一个空格都去关联一次三张集合表，每层递归都要做类似操作。随着搜索深度增加，这个开销会成倍放大，而且写出来的SQL非常臃肿——一大堆NOT IN、NOT EXISTS或者EXCEPT嵌套，跑起来也卡。

更麻烦的是，传统方法很难表达“回溯”这个动作。SQL是集合操作语言，不是过程式语言。虽然可以用递归CTE模拟搜索树，但如果你在每一步的状态里存“一个9乘9的二维数组”，PostgreSQL对二维数组的处理会非常别扭，类型转换、切片、更新都麻烦。

1.3 位运算切入的关键洞察

周仟荣的这个方案里，最核心的洞察一句话就能概括：一个数字的集合，可以用一个整数里的位来表达。数字n对应整数里的第n位，置为1表示“这个数字在集合里”，置为0表示“不在”。这样，原本需要用表格或数组存储的候选集合，被压缩成了一个整型变量。

“行、列、宫各自已出现的数字集合”就是三个长度为9的整数数组，每一个整数占用9个二进制位。判断某空格还能填什么数字，只需要做一次位运算：

可用候选 = 全集掩码 & ~(行掩码 | 列掩码 | 宫掩码)

全集中间掩码是511，也就是二进制111111111，代表数字1到9全部可用。这个公式把原本需要多次关联查询的逻辑，变成了三次整数按位或、一次按位取反、一次按位与，CPU里一次运算就完事了。

这个想法在嵌入式开发里很常见，但在数据库SQL语句中这么用的人确实不多。一旦想通了这层，后面所有代码都顺理成章。

2. 建模与预处理：把棋盘装进整数里

2.1 位掩码表示数字集合

先定义映射规则。数字1对应二进制的第1位，也就是1 << 0 = 1；数字2对应第2位，1 << 1 = 2；依此类推，数字9对应1 << 8 = 256。

用PostgreSQL的整数左移运算符<<可以很自然地表达这个映射：

-- 数字n对应的掩码 1 << (n - 1)

为什么要这样映射？因为集合的并集就是整数的按位或|，交集就是按位与&，补集就是带掩码的按位取反~。人和计算机都容易理解，而且PostgreSQL的整数运算效率极高。

例如，假设某行已经填了数字1、4、7，那么这一行的掩码计算方式就是：

(1 << 0) | (1 << 3) | (1 << 6) -- 结果是 1 + 8 + 64 = 73

二进制表示是0001001001。如果另一行填了数字2、9，其掩码是(1 << 1) | (1 << 8) = 2 + 256 = 258。在代码层面，这些整数不需要人眼去读，它们只是参与运算的载体。

2.2 行、列、宫掩码的计算

在PostgreSQL里，我们可以用一条聚合语句把整行已经存在的数字汇总成一个掩码。这里用到的是BIT_OR聚合函数，它专门对一组整数做按位或，正好适合“把集合合并起来”的场景。

考虑一个临时表cells，它保存了所有81个格子的行列信息和值（空格用0表示）：

-- 伪结构: cells(pos, r, c, box, v) -- pos: 0到80的线性索引 -- r: 行索引, c: 列索引, box: 宫格索引

计算每一行的掩码：

SELECT r, COALESCE(BIT_OR(1 << (v - 1)) FILTER (WHERE v > 0), 0) AS row_mask FROM cells GROUP BY r

这里用了FILTER (WHERE v > 0)来跳过空格，因为空格的值是0，1 << (-1)会出错。COALESCE处理某行全部为空的情况——没有已填数字时聚合结果是NULL，统一转为0。列和宫同理，只是分组字段换一下。

我在实际测试中发现，BIT_OR配FILTER的写法在PostgreSQL里非常顺手，但要注意必须在聚合函数内部写FILTER，不能在外面加WHERE，否则会把空格所在的行整体过滤掉，宫格和行的掩码就不全了。这是很经典的坑。

2.3 候选数字的快速推导

有了三个掩码数组，任何一个空格(r, c, box)的可用数字可以一行算出：

(511 & ~(row_masks[r + 1] | col_masks[c + 1] | box_masks[box + 1]))

为什么结果是一个0到511的整数？因为511低9位全是1。行、列、宫三个掩码合并后，哪些位被占用一目了然，取反后再与511按位与，保留下来的位就代表“还没被占用，可以填写的数字”。

如果需要枚举候选数字的具体值，可以用一个生成序列配合位测试：

SELECT n FROM generate_series(1, 9) AS n WHERE (candidate_mask & (1 << (n - 1))) > 0

这个写法在后面的递归求解里会反复用到。其实到这里，求解器最核心的“压缩感知”部分已经全部打通了，剩下的就是怎么把这个候选计算嵌入到递归搜索里。

3. 核心求解器：递归CTE实现回溯搜索

3.1 递归状态的定义

求解器我用WITH RECURSIVE来实现。递归CTE的基本结构包含两部分：初始查询和递归查询，两者通过UNION ALL连接。每一轮迭代把上一轮产出的行作为输入，再生成新的行，直到没有任何新行产出为止。

每个递归状态保存四样东西：

• board：当前棋盘，用81个字符的文本串表示，字符0代表空格，1到9代表已填数字
• row_masks：长度为9的整数数组，存每行的已用数字掩码
• col_masks：长度为9的整数数组，存每列的已用数字掩码
• box_masks：长度为9的整数数组，存每宫格的已用数字掩码

用文本串表示棋盘，是这方案里一个非常实用的决策。对比int[][]二维数组，文本串在PostgreSQL里天然支持substr取字符、overlay替换字符，而且递归CTE传递时开销极低。81个字符的复制对数据库来说完全可以忽略。

初始状态通过SQL聚合语句生成。谜题输入我直接写在VALUES列表里，每个元组是(pos, val)，pos从0到80线性编号。例如标准谜题的第一行“5 3 空格 空格 7 …”，写作(0,5),(1,3),(4,7)。

3.2 关键一步：挑出最紧急的空格

搜索算法里的一个重要优化叫MRV启发式——Minimum Remaining Values，即每次从候选数字数量最少的空格开始试填。原因很朴素：候选越少，试错的概率越低，搜索树就越窄。

在SQL里实现MRV，我是这样做的。对当前棋盘上的每一个空格，用位运算算出候选掩码和候选数量：

CROSS JOIN LATERAL ( SELECT pos, (511 & ~(s.row_masks[r + 1] | s.col_masks[c + 1] | s.box_masks[box + 1])) AS candidate, pg_popcount(511 & ~(s.row_masks[r + 1] | s.col_masks[c + 1] | s.box_masks[box + 1])) AS cnt FROM all_cells WHERE substr(s.board, pos + 1, 1) = '0' ) candidates

pg_popcount函数专门统计整数二进制表示里1的个数，正好用来数候选数。在这一步之前，必须先准备一张all_cells表，包含所有81个位置的pos、r、c、box四个字段，避免每次递归重复计算行列宫索引。

找出候选数最少的那一格：

ORDER BY candidates.cnt, candidates.pos LIMIT 1

ORDER BY cnt, pos的意思是：先按候选数升序，候选数相同则取位置靠前的格子。这个确定性规则很重要——它保证了相同棋盘状态只会选择同一个空格，避免递归CTE在同一个棋盘上产生重复的分支路径。

3.3 尝试候选并递归

选定最紧急空格后，需要枚举这个空格的所有候选数字，每一个候选数字生成一条新的递归分支。这一步用LATERAL加generate_series来做：

CROSS JOIN LATERAL ( SELECT n FROM generate_series(1, 9) AS n WHERE (candidates.candidate & (1 << (n - 1))) > 0 ) try_number

于是，对于当前递归状态，有几个候选数字就生成几行新状态。每个新状态里，把选中的数字写入棋盘文本串，同时更新三个掩码数组里对应的那个元素。

棋盘更新用overlay函数：

overlay(s.board placing try_number.n::text from candidates.pos + 1 for 1)

掩码更新就是把对应行掩码按位或上新数字的位：

s.row_masks[candidates.r + 1] | (1 << (try_number.n - 1))

这里要特别注意，PostgreSQL的数组索引从1开始，而我们的行号r、列号c、宫号box都是0到8，所以访问数组时都要加1。我最初复现时就是因为忘加1，导致数组越界和错位，排查了整整一晚上。

递归的终止条件很自然：当棋盘上没有任何空格时，WHERE substr(board, pos + 1, 1) = '0'过滤出的结果为空，LATERAL不返回任何行，整个递归分支自然就断掉了。反过来也成立——如果某一步走到死胡同，某个空格候选数为0，generate_series不产生任何行，该分支也会终止。这两种情况都不需要显式写终止判断，这是这套方案的优雅之处。

3.4 完整SQL和结果输出

把上述所有部分拼起来，就是完整求解器。下面这个版本我实际跑过，可以一键执行：

WITH RECURSIVE puzzle(pos, val) AS ( VALUES (0,5),(1,3),(4,7), (9,6),(12,1),(13,9),(14,5), (19,9),(20,8),(25,6), (27,8),(31,6),(35,3), (36,4),(39,8),(41,3),(44,1), (45,7),(49,2),(53,6), (55,6),(60,2),(61,8), (66,4),(67,1),(68,9),(71,5), (76,8),(79,7),(80,9) ), all_cells AS ( SELECT gs AS pos, gs / 9 AS r, gs % 9 AS c, (gs / 9) / 3 * 3 + (gs % 9) / 3 AS box FROM generate_series(0, 80) AS gs ), init AS ( SELECT (SELECT string_agg(COALESCE(pz.val::text, '0'), '' ORDER BY ac.pos) FROM all_cells ac LEFT JOIN puzzle pz ON pz.pos = ac.pos) AS board, (SELECT array_agg(m ORDER BY r) FROM ( SELECT ac.r, COALESCE(BIT_OR(1 << (pz.val - 1)) FILTER (WHERE pz.val > 0), 0) AS m FROM all_cells ac LEFT JOIN puzzle pz ON pz.pos = ac.pos GROUP BY ac.r) x) AS row_masks, (SELECT array_agg(m ORDER BY c) FROM ( SELECT ac.c, COALESCE(BIT_OR(1 << (pz.val - 1)) FILTER (WHERE pz.val > 0), 0) AS m FROM all_cells ac LEFT JOIN puzzle pz ON pz.pos = ac.pos GROUP BY ac.c) x) AS col_masks, (SELECT array_agg(m ORDER BY box) FROM ( SELECT ac.box, COALESCE(BIT_OR(1 << (pz.val - 1)) FILTER (WHERE pz.val > 0), 0) AS m FROM all_cells ac LEFT JOIN puzzle pz ON pz.pos = ac.pos GROUP BY ac.box) x) AS box_masks ), solve(board, row_masks, col_masks, box_masks) AS ( SELECT board, row_masks, col_masks, box_masks FROM init UNION ALL SELECT overlay(s.board placing try_number.n::text from c.pos + 1 for 1), -- 更新行掩码 array_agg(case when idx = c.r + 1 then s.row_masks[idx] | (1 << (try_number.n - 1)) else s.row_masks[idx] end order by idx), -- 更新列掩码 array_agg(case when idx = c.c + 1 then s.col_masks[idx] | (1 << (try_number.n - 1)) else s.col_masks[idx] end order by idx), -- 更新宫掩码 array_agg(case when idx = c.box + 1 then s.box_masks[idx] | (1 << (try_number.n - 1)) else s.box_masks[idx] end order by idx) FROM solve s CROSS JOIN all_cells ac CROSS JOIN LATERAL ( SELECT ac.pos, (511 & ~(s.row_masks[ac.r + 1] | s.col_masks[ac.c + 1] | s.box_masks[ac.box + 1])) AS candidate WHERE substr(s.board, ac.pos + 1, 1) = '0' ) c CROSS JOIN LATERAL ( SELECT n FROM generate_series(1, 9) AS n WHERE (c.candidate & (1 << (n - 1))) > 0 ) try_number CROSS JOIN LATERAL generate_series(1, 9) AS idx ), solution AS ( SELECT * FROM solve WHERE NOT EXISTS ( SELECT 1 FROM all_cells WHERE substr(solve.board, all_cells.pos + 1, 1) = '0' ) LIMIT 1 ) SELECT string_agg( CASE WHEN (pos / 9) = 0 THEN E'\n' ELSE '' END || substr(board, pos + 1, 1) || ' ' || CASE WHEN (pos % 9) IN (2, 5) THEN '| ' ELSE '' END, '' ORDER BY pos ) AS solved_board FROM solution, generate_series(0, 80) AS gs(pos);

这里有个实现细节值得说明：掩码更新我用array_agg加CASE WHEN遍历整个数组，而不是单独改某个元素。PostgreSQL没有直接更新数组单元素的语法，与其先拆数组再重组，不如一条聚合语句全部搞定。idx序列生成1到9，正好对应数组下标的九个位置。

运行后输出棋盘文本，比如第一行是5 3 4 | 6 7 8 | 9 1 2。为了更好看，甚至可以在外层再加一层解析，输出成真正的九行网格。我在本地测试时就是直接看这个格式化输出，和网上给出的标准答案逐行核对过，完全一致。

4. 性能实测与优化空间

4.1 与PL/pgSQL暴力回溯的对比

给手头几个方案做了个简单对比。同样的谜题输入：

说实话，SQL方案能跑进几十毫秒，我刚开始是不信的。后来分析原因也清楚：位掩码让“候选数字判断”从数据库查询变成了纯CPU整数运算，而且整个搜索过程中每个状态只有81个字符的文本复制和三个整数数组的指针移动，数据量极小。加上MRV启发式把搜索树压得很窄，很多分支在第二三层就剪光了。

有一点需要提醒：首次执行和重复执行差距很大。第一次跑这个查询时，PostgreSQL需要做计划、读表、加载数据，加上约100毫秒的额外开销；同一会话内第二次跑相同查询，最快的一次我测到过13毫秒。这和SQL优化的通用经验一致：连接复用和缓存预热对短查询影响巨大。

4.2 影响速度的几个因素

整个方案的速度受三个因素主导。

第一是MRV启发式的有效性。每次挑候选数最少的空格，能极大减少无效分支。对于这个经典谜题，搜索树的节点数大约只有几百个。如果改成随便拿一个空格就试，节点数会翻几十倍甚至上百倍。

第二是递归深度的控制。数独81格，加上初始给定的30个数字，递归深度下限是51层。每个递归分支在PostgreSQL里是一行状态，行的生成和传递成本很低，几乎感受不到深度压力。真正让人头痛的是分支数量，这又回到第一点。

第三是pg_popcount的代价。这个函数本质是CPU指令级别的位计数，非常快。我测试了几种不同的候选计数写法，包括手动展开8次位移逐位判断，结果是pg_popcount比任何手动计数都快，代码也更简洁。如果目标环境恰好是PostgreSQL 13或更早版本，可以用# (x::bit(64))这种位串转换方式替代，但数字本身很小，兼容性写法也能接受性能损耗，实测差距不大。

4.3 可继续优化的方向

我后来试着把思路往两个方向扩展。第一个方向是支持更难的谜题。我生成了几个需要高级技巧的高难度数独，这套递归CTE依然能解出来，只不过时间会上升到几百毫秒到一秒级。原因是高难度谜题往往伴随“候选数相同的空格多”的情况，MRV的区分度下降，搜索树会变宽。

第二个方向是多解判断。有些数独题目不是唯一解的，这套SQL天然支持——去掉LIMIT 1就能输出所有解。我用一个故意设计成多解的棋盘试过，递归CTE会把所有解逐行输出，相当于免费获得了一个“求解全部解”的能力。这在纯SQL方案里是非常难得的一件事，因为很多过程式实现为了性能会提前剪枝，反而做不了全枚举。

性能上还有一招没写进主代码：如果谜题存在大量确定性推进，可以在递归外先做一轮“候选唯一化”推导，把那些候选数只剩一个的空格全部填掉，再进入递归搜索。这一步能把最难的谜题时间再砍掉一半左右。不过它需要额外一组循环迭代CTE，会拉长代码，比赛场景下反而不划算，所以我没有把它放进最终提交版本。日常自己用的话，值得一试。

5. 踩坑实录：几个我差点放弃的细节

5.1 PostgreSQL数组索引从1开始

这个坑我在前面提过，但值得单独拿出来再说一次。PostgreSQL的数组下标默认从1开始，和大量编程语言从0开始完全不同。整个算法里行号、列号、宫号都是从0开始计算的，因为它们来自generate_series(0, 80)，是线性索引除以9的结果。

如果访问掩码数组时不加1，会发生两类问题：一是访问row_masks[0]会得到空值，PostgreSQL不报错，只是返回NULL；二是因为结果变成了NULL，所有位运算结果全部变成NULL，候选判断永远失败，SQL最后没有任何输出。这种“程序不报错但结果为空”的情况排查起来最折磨人，我建议写完后自己打印一遍三个掩码数组，逐个检查元素值是否和你手算的行列宫掩码一致。

5.2 BIT_OR与FILTER组合的写法

计算行掩码时，很容易写错成这样：

SELECT r, BIT_OR(1 << (v - 1)) AS m FROM cells WHERE v > 0 GROUP BY r

如果全部格子都是空格，这个查询会直接丢掉那一行，聚合出来的结果缺行，导致后续array_agg得到的数组长度不足9，访问时又出现NULL。正确做法是把WHERE v > 0放进FILTER子句：

BIT_OR(1 << (v - 1)) FILTER (WHERE v > 0)

这样空格仍然会参与分组，只是值不参与聚合。加上COALESCE兜底，才能保证每个行/列/宫都有对应的掩码。

5.3 pg_popcount的版本兼容性

pg_popcount是PostgreSQL 14引入的函数，在某些云数据库的旧版本上会直接报“function pg_popcount does not exist”。如果你碰到了，最简单的替代方案是：

-- 候选数统计兼容写法 SELECT # ((candidate_mask)::bit(9)) AS cnt

#运算符在PostgreSQL里表示“按位串计算1的个数”，bit(9)强制转换为9位位串，正好覆盖数字1到9。我测试过，这种写法在旧版本上完全可用，只是代码可读性稍差。另外，也可以定义一个自定义函数包装这行逻辑，后续调用更清爽。

5.4 overlay函数的边界

overlay函数替换字符串时，位置参数是从1开始的。我第一次尝试时写成了from pos + 1 for 1，其中pos是0到80的线性索引。这个位置其实是对的，因为文本串也是从1开始编号。但如果理解成字符数组的下标，就会在边界处懵住。实际调试时可以用一个最简单的1×1棋盘做单步测试：输入确认为1的谜题，观察overlay之后文本是否正确替换了唯一空格。这个微缩测试我推荐所有人都做一遍，能省下大把调试时间。

5.5 递归CTE里别用ORDER BY加LIMIT当全局排序

MRV选空格时，很多人写SQL会习惯性加ORDER BY cnt LIMIT 1。这在普通查询里没问题，但在LATERAL子查询里，它的含义是“每个父行内部取一行”。如果父行恰好只有一行，效果等同于全局选择。一旦谜题复杂度提升，递归CTE同时扩展多个分支，问题就会冒出来——每个分支都会独立选择自己的“最紧急空格”，而不是全局共同选一个。

这其实是正确行为，因为每个分支对应不同的棋盘状态，本来就该各自选择。我最初误以为这里需要窗口函数ROW_NUMBER做全局排序，试过之后发现不但多余，还会严重拖慢执行，因为窗口函数会把所有递归分支的状态堆在一起排序。理解每个LATERAL的执行范围，是写对这类SQL的关键。

5.6 最终输出别忘了去重

如果谜题本身存在对称性，递归CTE可能产生重复棋盘。我在一次实验中构造了一个对称谜题，结果解出来的行数翻倍了。平时用LIMIT 1不影响，但全量枚举时一定要加DISTINCT或者在输出层做去重。PostgreSQL里直接对board字段做DISTINCT即可，因为同一个棋盘可能由不同路径到达，但文本串本身是唯一的。

最后再分享一个小技巧

这个方案里的递归CTE代码本身不难，难的是把“位掩码表示集合”这个脑回路转过来。如果你对位运算不熟，建议先从最简单的问题练手：用SQL写一个函数判断两个集合是否有交集，再升级到判断数独某个空格的候选数字。一旦把位运算吃透了，你会发现它不仅能解数独，还能用在权限判断、标签筛选、排班冲突检测这类现实问题上。

我个人在这套代码里学到的最有价值的东西，其实是“在合适的抽象层级上建模”。数独的空间，二维数组是一种建模，文本串加掩码是另一种建模，后者在数据库里明显更顺手。周仟荣这套方案能在比赛中拿好名次，靠的不仅是SQL语法熟练，更是这种建模意识。对你来说，下一次遇到性能掉链子的SQL查询时，不妨也想想：有没有可能换一种数据表示，让数据库用一次位运算就解决问题？