编程比赛我参加过不少但像这样把规则卡得死死的还是头一回不能用存储过程不能声明变量不能建临时表只给一条 SELECT却要解出一道数独。当时我盯着题目看了几分钟第一反应是主办方是不是来砸场子的。后来静下心盘了一圈脑子里冒出来的方案只有一个——PostgreSQL 递归 CTE。最后这条 SQL 帮我拿到了第4名成绩不算顶好但思路我自己挺满意。今天把整条 SQL 从建模、递归到剪枝逐段拆开给同样在啃 PostgreSQL 递归 CTE 的朋友当个参考。先说结论数独本质不是数字题而是一个在 9x9 矩阵上做约束满足的搜索问题。SQL 平时确实不擅长干这个但 WITH RECURSIVE 天生就是表达尝试、失败、再尝试这种递归过程的工具。只要把盘面建模建对了把剪枝条件翻译成 NOT EXISTS一条 SQL 落地完全可行。1. 比赛现场规则为什么把所有人逼向递归CTE1.1 一道看似不可能的赛题那场比赛的规则相当狠程序主体只能是一条 SQL 语句数据库任选但不准写存储过程、不准用外部脚本、不准建辅助表。题目给一个标准9x9数独盘面要求把解出来运行时间还有上限。当时会场的反应很有意思。不少人第一反应是SQL 解数独开玩笑吧。有人想用 SQL Server 的 CLR 扩展有人想用 Oracle 的 MODEL 子句还有人试图把一个现成 Python 求解器通过外部表拉进来——全被规则挡回去了。剩下能做文章的基本就是各家数据库对递归查询的支持程度。我为什么立刻想到递归 CTE因为数独的求解过程本质上就是一个深度优先搜索找一个空格试填一个数字检查约束不行就换下一个数字再不行就回溯。这个每次基于当前状态生成新状态的过程和递归 CTE 的迭代语义几乎完全吻合。只要每一轮递归代表填好一个格子之后的新盘面最后当盘面里没有空格时自然就是答案。1.2 为什么我押注PostgreSQL备选其实有 MySQL 8、SQLite、PostgreSQL。MySQL 8 虽然也支持 WITH RECURSIVE但它的递归默认深度限制是 1000数独最多递归 81 层理论上够用问题是 MySQL 没有原生 generate_series造一个 1 到 9 的候选数字序列还得再套一层递归代码会变得很啰嗦。SQLite 的递归 CTE 也能写但字符串函数相对简单处理 81 位盘面替换时不够顺手。PostgreSQL 的优势在于三个点组合起来很舒服generate_series(1,9)直接生成候选数字overlay()可以精确替换字符串中的某个字符position()能快速定位盘面中的空格。这三个函数拼在一起正好覆盖了找空格、试数字、写回盘面的完整循环。而且 PostgreSQL 的 WITH RECURSIVE 语义非常干净递归分支里可以直接引用上一层的结果集不需要额外语法糖。当然选择 PostgreSQL 还有一个现实原因比赛机器上预装了 PG省去了折腾环境的功夫。如果现场只有 MySQL我大概率也能写出来但代码会长不少后面我会提到差异点。2. 数独的数据库建模把81个格子压缩成一串字符2.1 为什么用81位字符串而不是9行9列的表拿到数独后第一个要解决的问题是怎么用关系模型表达一个 9x9 盘面最直观的想法是建一张二维表比如cells(row, col, value)九个格子一行递归时往表里插数据。但真写起来会发现这条路很难走递归 CTE 每一轮返回的是一个结果集如果你想用一个结果集代表一个盘面那必须把同一时刻的 81 个格子聚合成一行输出聚合本身就很麻烦。而如果你想用多条记录代表一个盘面那就必须在每一轮递归里维护当前盘面的所有格子稍微一写就会变成多个递归路径的笛卡尔积状态根本兜不住。所以我换了个思路把整个盘面压成一个长度固定为 81 的字符串。第 1 个字符代表第 1 行第 1 列第 2 个字符代表第 1 行第 2 列按行优先排下去。空格用.表示已填数字直接用字符 1 到 9。这样设计有一个决定性的好处递归 CTE 的每一行就是一个完整的盘面状态。递归每走一步字符串上被替换一个字符新盘面作为新的一行进入下一轮。整个搜索树天然被一行一状态的组织方式承载既不需要临时表也不需要拼接多条记录。比赛标准题目的初始盘面我把它存成了这样53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28...419..5.....8..79你看到的那一长串其实就是题目给的 9 行拼在一起。这个建模方式看着笨实际操作却非常稳后面几条 SQL 操作全是围绕字符串位置展开的。2.2 定位格子pos怎么换算成行、列、宫字符串方案的核心问题是坐标换算。盘面里的位置用一个从 1 到 81 的整数pos表示但这个pos必须能换算回第几行、第几列、第几个宫否则剪枝条件根本写不出来。换算公式不复杂但容易算错。我直接列成表目标计算公式行号0开始(pos - 1) / 9列号0开始(pos - 1) % 9行内第i个格子的位置((pos - 1) / 9) * 9 i 1列内第i个格子的位置(pos - 1) % 9 i * 9 1宫行组((pos - 1) / 9) / 3宫列组((pos - 1) % 9) / 3宫内第i个格子的位置宫行组 * 27 宫列组 * 3 (i / 3) * 9 (i % 3) 1这里要注意PostgreSQL 里两个整数相除是向下取整的整除所以(pos - 1) / 9正好是行号不用再套 floor。宫的位置想不明白时可以把它拆成两步先确定这个格子落在哪个 3x3 宫再确定宫里第几个位置。宫的左上角是整个宫的第一个格子偏移量(i / 3) * 9 (i % 3)负责在宫内从左到右、从上到下扫一遍。2.3 为什么每次只填第一个空格很多第一次接触这个思路的人会问递归时为什么不把盘面上所有空格一次性都填了答案是一次只填一个空格才能保证递归路径是逐步收敛的。每填一个格子盘面就更完整一点后续空格的候选数字也会因为新约束而减少。如果一次填多个格子相当于同时做了多个猜测任何一个格子的错误都会让整条路径报废回溯成本极高。那为什么偏偏选position(. in board)找到的第一个空格而不是选一个候选数最少的空格从算法角度候选最少的空格MRV 启发式确实能更快收敛。但在单条 SQL 里实现 MRV 需要为每个盘面再跑一轮统计代码量会明显上涨。比赛里我在代码可读性和运行速度之间做了权衡——先跑通、再优化后面我会单独讲性能实测。3. 递归CTE逐行拆解种子、尝试、剪枝、出口3.1 完整解法SQL先看成品先把成品亮出来后面再逐段解释。这条 SQL 在 PostgreSQL 12 以上的版本可以直接跑我实际验证用的是 PG 16WITH RECURSIVE solve(board) AS ( -- 种子初始盘面81个字符. 表示空格 SELECT 53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28...419..5.....8..79 UNION ALL -- 递归找第一个空格尝试填入1-9中不冲突的数字 SELECT overlay(board placing d::text FROM sp FOR 1) FROM solve, LATERAL ( SELECT gs AS d, position(. in board) AS sp FROM generate_series(1, 9) AS gs WHERE NOT EXISTS ( SELECT 1 FROM generate_series(0, 8) AS i WHERE substr(board, ((sp - 1) / 9) * 9 i 1, 1) d::text OR substr(board, (sp - 1) % 9 i * 9 1, 1) d::text OR substr(board, (((sp - 1) / 9) / 3) * 27 (((sp - 1) % 9) / 3) * 3 (i / 3) * 9 (i % 3) 1, 1) d::text ) ) cand WHERE position(. in board) 0 ) SELECT board FROM solve WHERE position(. in board) 0;执行完最后一条 SELECT返回的那一行就是一个完整解。3.2 种子与递归分支WITH RECURSIVE的迭代语义先看WITH RECURSIVE solve(board) AS (...)这个骨架。它由两部分组成中间用UNION ALL连接第一个分支是种子查询也就是递归的起点。这里只有一行把初始盘面字符串填进去。这一行会进入solve结果集并成为第一轮递归的输入。第二个分支是递归查询它引用了solve自身。PostgreSQL 的执行方式是拿上一轮solve产出的所有行作为输入执行递归查询再把新结果合并进solve接着进入下一轮。直到某次递归查询一行都产不出来迭代结束。这个上一轮结果喂给下一轮的机制和我解数独时脑子里的搜索过程完全一致。每次递归输入一行盘面输出若干个新盘面——每一个都是填好一个格子后的分支。UNION ALL在这里是刻意选的。搜索路径之间不可能出现完全相同的盘面所以不需要UNION去重UNION ALL还能少一次去重排序开销。不过要提醒一句如果你真的担心递归路径太多想靠去重来压状态UNION大概率救不了你因为数独的搜索路径重复概率极低去重只会白耗 CPU。3.3 核心循环找空格、造候选、填进去递归分支的执行顺序可以拆成四步第一步从当前盘面board里找到第一个空格位置sp。我用position(. in board)完成它返回第一次出现.的位置范围是 1 到 81。如果盘面已经完整position()返回 0最后一行WHERE position(. in board) 0就会拦住这个盘面不让它继续递归。第二步生成 1 到 9 的候选数字。这里的技巧是CROSS JOIN LATERAL配合generate_series(1, 9)。LATERAL子查询只做两件事把generate_series生成的整数命名为d把position(. in board)的结果命名为sp。之所以放在 LATERAL 里是因为后面 NOT EXISTS 的剪枝条件要反复用到sp也方便阅读。第三步对每个候选数字d做约束检查。如果数字d已经出现在当前空格所在的行、列或 3x3 宫里这个候选就要被丢掉。检查用NOT EXISTS实现这是整条 SQL 的剪枝核心下一节单独展开。第四步如果候选数字通过了检查就把新盘面写回。写回用的是overlay(board placing d::text FROM sp FOR 1)含义是把board从sp位置开始的一个字符替换成数字d的文本形式。每一步都对应搜索算法的一个环节找空格是选未填位置造候选是枚举可能性剪枝是约束传播写回是生成子状态。3.4 NOT EXISTS剪枝行、列、宫三层检查NOT EXISTS子查询是整个思路的精髓也是很多人抄 SQL 时最容易抄错的地方。它的逻辑是如果存在任意一个位置使得候选数字d与已有数字冲突那么这个候选就不可行。检查分成三层每一层都从generate_series(0, 8) AS i生成 0 到 8 共 9 个序号用来遍历对应的一组格子。行检查这行代码substr(board, ((sp - 1) / 9) * 9 i 1, 1) d::text含义是取当前空格所在行的第i个格子。(sp - 1) / 9是行号* 9跳到这一行的起点再加i 1是因为字符串位置从 1 开始。如果这一格里已经有数字且正好等于候选d说明行冲突。列检查这行substr(board, (sp - 1) % 9 i * 9 1, 1) d::text(sp - 1) % 9是列号 1是让位置落到第 0 行的这一列再加i * 9向下走 9 行。这样i从 0 到 8 正好扫完一整列。宫检查最绕substr(board, (((sp - 1) / 9) / 3) * 27 (((sp - 1) % 9) / 3) * 3 (i / 3) * 9 (i % 3) 1, 1) d::text((sp - 1) / 9) / 3是宫的行组((sp - 1) % 9) / 3是宫的列组。前者乘以 27 跳到目标宫所在的大行后者乘以 3 跳到目标宫所在的大列。后面(i / 3) * 9 (i % 3)用来在宫内按三行三列移动i为 0 到 8 时先左到右扫第一行的三个格子再换行继续扫最后就能覆盖整个宫。三条检查用OR连接只要任意一个冲突成立NOT EXISTS就整体不通过候选数字被丢弃。这个写法看起来简单但推导坐标时很容易犯边界错误。我实际调试时吃过亏宫检查里的(i / 3) * 9 (i % 3)一开始写成了(i / 3) * 3 (i % 3)结果宫内第二行直接跳到第三行检查漏了一整行跑出来的解明显有重复数字。这个坑后面会再提一次。3.5 出口与终态没有空格就是完整解递归不会永远跑下去因为每轮至少要把一个空格变成数字。标准数独的递归深度最多 81 层递归分支的 WHERE 条件保证盘面完整后就停止扩展。但要注意最终solve结果集里不仅有完整解还会混着大量中间状态的半成品盘面。完整解的特征是字符串里没有任何.所以position(. in board) 0。最后一条 SELECT 干的就是这件事把满足条件的行筛出来。如果题目有多个解这条 SELECT 会返回多行如果想只取一个解加LIMIT 1就行。4. 剪枝与性能实测从天文数字到几十毫秒4.1 分支数量级与递归工作集不懂行的人可能觉得81 个空格每个试 9 个数字最坏情况就是 9 的 81 次方这谁敢跑但实际上数独约束极强每一次填数字都会同步排除同行、同列、同宫里其他空格的候选搜索树没有想象中那么恐怖。以我比赛用的那道题为例肉眼观察可以发现第一个空格周围已经有 5、3、7 等数字约束候选很快就只剩下两三个。整棵搜索树的分支会随着递归深入不断收窄实际展开的行数大概在几十万这个量级。PostgreSQL 处理这种量级的数据也就是几十毫秒到几百毫秒的事。真正需要关注的是递归工作集的内存。递归 CTE 每轮迭代都要保留上一轮所有存活路径的盘面如果某道题比较变态路径行数涨到几百万行work_mem 不够时 PostgreSQL 会把中间结果刷到磁盘临时文件里。表现不是报错而是速度明显变慢。我在比赛里提前做了两件事一是用SET work_mem 64MB给递归查询更多内存缓冲二是用SET statement_timeout 30s做保护防止某条递归路径失控把整个会话拖死。4.2 实测数据与两个尝试过的优化为了说明问题我在自己的笔记本上重新跑了这道标准题PG 16默认配置。优化前完整 SQL 的执行时间大概稳定在 100 毫秒以内返回唯一解。这个成绩已经够用我后来还手痒试了两个优化思路简单汇报一下。第一次尝试是改变空格选择策略。把填第一个空格改成填候选数字最少的空格理论上能大幅压缩搜索树。实现方式大致是在递归分支里先对所有空格做一次聚合统计每个空格的可行候选数量再选出最小值对应的位置去填充。这个思路没问题但放在单条 SQL 里会让递归分支变得非常长聚合还要再刮一层子查询代码可维护性断崖式下跌。实测性能提升确实有但没快到值得牺牲可读性的程度所以最终版本保留了第一个空格策略。第二次尝试是调整 NOT EXISTS 里的检查顺序。SQL 优化器不保证 OR 条件按左边的写法从左到右执行所以试图通过调整行、列、宫三个子条件的先后顺序来提前短路基本是心理安慰。真想让检查更快可以改用d::text NOT IN (SELECT ...)之类的集合写法但效果也有限不值得为它破坏统一性。4.3 这条SQL在比赛机器上需要注意的边界有几个细节是赛后才总结出来的PostgreSQL 对递归 CTE 里的相关子查询比较敏感。我在旧版本 PG 上实验时遇到过 recursive reference to query must not appear within a subquery 这类报错但同一段 SQL 在新版本上没问题。如果读者在自己的环境里跑不通优先确认 PG 版本是否 12 以上再检查有没有在子查询里直接写了solve而不是只引用solve的列。类型问题也坑过不少人。generate_series(1, 9)生成的是整数而substr()返回的是文本。直接拿整数和文本比PostgreSQL 会报operator does not exist: text integer。所以要记得加d::text。忘了这个转换是这条 SQL 最常见的报错来源。还有一点字符串里的.不能想当然写成0。如果用 0 表示空格position(., ...)就失灵了递归入口直接找不到空格整条 SQL 只会返回初始盘面。题面给的 0 和空格在建模时是两码事我在比赛前排查环境时就把这个坑记在了笔记里。5. 赛后扩展递归CTE在生产环境还能怎么用5.1 同一套思路解决其他约束搜索问题比赛结束后我发现这套单条 SQL 求解约束搜索的思路远不止能解数独。凡是每一步产生一个状态状态满足某些约束最后到达终态的问题都能用同样的模板改造。比如八皇后问题。棋盘可以建模成一个长度 8 的字符串第 i 个字符表示第 i 行皇后所在的列。递归时每行放一个皇后剪枝条件变成新皇后不能和已有皇后同列、同对角线检查时用字符串位置换算斜线坐标就行。把数独 SQL 里的行/列/宫检查换成两个对角线差判断代码量基本持平。再比如图的路径搜索。组织架构的上下级关系、商品 BOM 的多层展开、地铁换乘路径这类问题天然就是树形递归。递归 CTE 处理这类需求有一个普通 JOIN 无法替代的优势它能按层展开而且在展开过程中动态过滤循环引用。数独里每轮替换一个字符图里每轮追加一个节点本质上是同一个计算模型。我还拿这个思路处理过一个配置解析类的需求一段带嵌套括号的文本需要按层级展开。递归 CTE 每一轮匹配一对括号把内容抽出来放到下一层最后得到一颗配置树。这比在应用层写状态机要省事也更容易做数据血缘追踪。5.2 递归CTE的三个常见坑正因为递归 CTE 在很多场景里好用它的坑也值得单独列一列。第一个坑是忘记写终止条件。数独的终止条件写在WHERE position(. in board) 0很多图遍历的递归则依赖WHERE NOT EXISTS判断节点是否已访问。一旦忘记终止条件PostgreSQL 不会自动帮你停下来。它不会像 MySQL 那样直接报递归深度超限而是会一直迭代到你设置的statement_timeout触发或者占满临时空间。线上环境操作前至少要先看一眼pg_stat_activity和临时文件目录。第二个坑是 UNION 和 UNION ALL 的选择。理论上 UNION 可以去重防止重复路径但它也意味着每一轮迭代都要排序去重。对递归路径天然不重复的场景比如数独、组织树用 UNION 纯属浪费。反过来如果递归确实会产生大量重复状态比如某些图遍历里节点可以从不同路径到达那 UNION 能有效压制状态暴涨。这是一道权衡题不是固定答案。第三个坑是递归分支里对外层列的引用方式。PostgreSQL 对递归自引用的位置有限制直接写FROM solve的子查询在某些版本里会报错但像这条数独 SQL 一样只在相关子查询里引用外层board列通常没问题。遇到奇怪报错时第一反应应该是查 PG 版本和递归引用写法而不是怀疑 SQL 逻辑本身。5.3 一点个人体会现在回看这场比赛最值钱的其实不是那句一条 SQL 解数独的噱头而是建模这一步的取舍。同一个数独如果我用 9 行 9 列的关系表建模后面的递归几乎写不下去换成 81 字符的字符串一切都变得顺理成章。很多看起来SQL 做不到的问题卡住你的往往不是 SQL 本身而是你还没找到那个让问题适配 SQL 的表示方式。我把这条 SQL 发到团队里之后有同事拿去解了另一道题也有同事把递归模板套到了业务树展开上。如果你手头也有一类每次基于状态生成新状态的问题建议先想清楚三个问题状态是什么、每一步怎么变、怎么判断收敛。想明白了剩下交给数据库去跑就行。