上周末在数据库技术社群里看到有人转发一条赛报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)来跳过空格因为空格的值是01 (-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 ) candidatespg_popcount函数专门统计整数二进制表示里1的个数正好用来数候选数。在这一步之前必须先准备一张all_cells表包含所有81个位置的pos、r、c、box四个字段避免每次递归重复计算行列宫索引。找出候选数最少的那一格ORDER BY candidates.cnt, candidates.pos LIMIT 1ORDER 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不返回任何行整个递归分支自然就断掉了。反过来也成立——如果某一步走到死胡同某个空格候选数为0generate_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暴力回溯的对比给手头几个方案做了个简单对比。同样的谜题输入方案代码量首次解出时间我的笔记本实测备注PL/pgSQL过程式回溯约200行120至200毫秒每次候选检查都要查表Python暴力回溯约100行40至80毫秒内存中数组操作PostgreSQL递归CTE位运算约80行16至35毫秒纯SQL无存储过程说实话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查询时不妨也想想有没有可能换一种数据表示让数据库用一次位运算就解决问题