1. 这个题目到底在考什么数独不是重点约束满足才是打开题目的第一眼我承认愣了一下数独用SQL这不是该开个Python脚本暴力回溯的活儿吗但冷静下来想这道题出得其实很刁钻。数独的规则就三句话——每行1到9不重复、每列1到9不重复、每个3x3宫格1到9不重复——这本质上是一个约束满足问题英文叫CSPConstraint Satisfaction Problem。而SQL最擅长的恰恰是集合操作、存在性判断、关系组合与过滤。把CSP塞给SQL不是开玩笑而是刚好打在SQL的强项上。你完全可以把这道题映射到真实的业务场景里排班系统里同一个员工同一时段不能出现在两个班次会议室系统里同一时间段不能有两拨人同时预定物流分配里同一订单不能重复分配给两辆卡车。这些全部是约束满足问题。数独只是在9x9的棋盘上把约束抽象到了极简形态所有规则透明、无噪声、无歧义。所以这道题表面在考数独实际考的是你如何用集合思维描述规则、如何用递归CTE做状态搜索。想明白这套思路回到业务里处理冲突检测、排班调度思路会通透很多。网上解这道题的思路大体分三个流派。第一派是纯集合运算加迭代排除不停计算每个格子当前还能填哪些数把唯一候选的格子直接填上然后再刷一遍盘面。这种写法不难但只能处理有大量唯一候选的题目遇到需要假设验证的难题立刻歇菜。第二派是递归CTE模拟回溯这也是大多数竞赛选手选择的正路每个状态就是当前盘面从中选一个空格枚举它的合法候选值每个候选值生成一个新分支继续往下走。第三派是干脆不用纯SQL在数据库里写PL/pgSQL或者存储过程循环填格。这种当然能跑但在仅用SQL的比赛规则下基本算作弊阅卷不会给你加分。这篇文章我把第二派的完整思路讲透附上直接能跑起来的PostgreSQL版本再给你MySQL 8、SQL Server、SQLite上的移植要点以及我实际跑下来遇到的各种坑。想直接看结论的跳到第3节想弄明白底层逻辑的我建议从头看。1.1 规则先行数独的三个约束怎么翻译先花两分钟把规则理一遍。标准9x9数独盘面上有若干已知数字其余位置留空。玩家的任务是在每个空格里填上1到9满足三个条件每一行恰好出现1到9各一次每一列恰好出现1到9各一次每个3x3宫格恰好出现1到9各一次。这里的恰好翻译成SQL语言就是没有重复更进一步就是不存在两个相同数字出现在同一行、同一列或同一宫。所以对一个待填格子它的合法数字集合可以写成全集1到9减去所在行已经出现的数字减去所在列已经出现的数字再减去所在宫已经出现的数字。集合的差集这不就是SQL的原生操作吗宫格编号是个常见的坑。9x9盘面中宫格分三大行区间1-3、4-6、7-9和三大列区间1-3、4-6、7-9。用整除运算可以统一表达(r-1)/3得到的是0、1、2三段索引所以判断两个格子是否同宫只需要同时满足行分段相等和列分段相等。这个写法在后文所有约束检查里都会反复出现。1.2 解题直觉从唯一候选到回溯人肉解数独通常用的策略是候选数排除先扫一遍盘面把每个空格能填的数圈出来哪个格子只剩一个候选就填哪个然后更新其他格子的候选。这个唯一候选法在SQL里可以用NOT EXISTS模拟把每行、每列、每宫已出现的数字算出来用NOT EXISTS把候选集合过滤掉。但这个方法有硬伤。它只能处理不需要猜想、顺着唯一候选一路推到底的题目。一旦遇到所有空格都有多个候选、必须假设一个再验证的情况就得引入回溯。回溯是什么就是一条路走不通退回上一个岔路口换条路再走。比如一个空格候选值是3和7你先填3往下填几步发现矛盾于是推倒重来填7再继续往下探。这个过程在命令式语言里靠函数递归调用栈实现在SQL里则要靠递归CTE。1.3 为什么递归CTE是仅用SQL的正解递归CTE把当前状态作为一个关系来持续迭代。对数独来说当前盘面是一行数据从当前盘面转移到下一个盘面是一行SQL表达式多个可选分支就是UNION ALL连接起来的多行结果。这个表达方式非常优雅不需要显式管理递归调用栈每个分支盘面就安静地待在结果集里直到填满或走到死路。递归CTE的结构也很有规律一段种子查询给出初始状态一段递归查询根据上一轮的所有状态生成新状态直到某次递归不再产出新行迭代自然结束。这跟编程里的递归函数是一个道理只不过函数的栈变成了关系表里的行集合。数独的递归深度就是空格数量最多81层完全在可控范围内。2. 数据建模把棋盘翻译成数据库能听懂的语句用SQL处理数独第一步不是写查询而是想清楚数据怎么存。建模方式不同后续约束检查的SQL写法天差地别。我试过两种主流建模各有优劣这里都展开讲。2.1 关系表建模一行一个格子最直观的做法是建一张表每一行对应盘面一个格子字段就三个r行号、c列号、v数字0表示未填。比如CREATE TABLE sudoku_board ( r INT NOT NULL, c INT NOT NULL, v INT NOT NULL DEFAULT 0, PRIMARY KEY (r, c), CHECK (r BETWEEN 1 AND 9), CHECK (c BETWEEN 1 AND 9), CHECK (v BETWEEN 0 AND 9) );把题目盘面INSERT进去已知数字填v未知填0。这张表就是盘面概念的规范化关系表达。接下来判断一个空格(r0, c0)能不能填数字nSQL写起来很直观SELECT n FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9)) AS nums(n) WHERE NOT EXISTS ( SELECT 1 FROM sudoku_board b WHERE b.v n AND ( b.r r0 -- 同一行已经有人占了n OR b.c c0 -- 同一列已经有人占了n OR ( (b.r - 1) / 3 (r0 - 1) / 3 AND (b.c - 1) / 3 (c0 - 1) / 3 -- 同一宫已经有人占了n ) ) );这个查询有意思的地方在于它把数独三条规则浓缩进了一个NOT EXISTS。规则本身几乎不需要额外写逻辑只需要把不合法情况描述清楚剩下的交给集合判断。这也是我说数独天生适合SQL的原因。关系表建模的优点是语义清晰、可读性强后续做候选数统计GROUP BY行、列、宫都很方便。缺点是在递归CTE里每做一步状态转移都要反复JOIN这张表而且一个当前盘面状态包含多条记录递归分支需要复制整批记录数据量会随深度膨胀写起来啰嗦。所以关系表建模更适合做基础教学和约束分析真放到递归回溯里我更推荐把它压成字符串。2.2 约束检查三组条件为什么能写进一个表达式关于上面那个NOT EXISTS多说一句奥妙。判断数字n能否放到(r0, c0)关键就是检查是否已经有一个同样等于n的格子和(r0, c0)在同一条约束链上。同一条约束链意思是同一行或者同一列或者同一宫。SQL里用一个OR把三种情况串起来只要存在任何一个格子满足b.v n且同行或同列或同宫就说明n已被占用不能再填。有人会觉得OR把三种情况混在一起不好理解。你可以拆成三个独立的NOT EXISTS再求交集读起来清楚性能差别在9x9的小棋盘上几乎可以忽略。但写递归CTE时表达式越短后面嵌套越不容易出错。所以我个人偏爱一个OR写完。还有一个容易忽略的点整数除法。PostgreSQL里(b.r - 1) / 3是两个整数相除结果是整数商也就是0、1、2正好对应上、中、下三段。这个设计让同一宫的判断不需要额外存储宫编号也不用手写区间判断。SQL Server和MySQL的整数除法行为也一致只是要注意别写成浮点除法。2.3 更轻的建模把盘面压成字符串接下来是我真正在题里用的建模方式把整个盘面表示成一个81字符的字符串从左到右、从上到下依次排出每一格的数字0代表空。比如经典题目530070000600195000098000060800060003400803001700020006060000280000419005000080079盘面上第pos个字符就是第(pos-1)/91行、第(pos-1)%91列的格子。想读某行某位置的值直接用substr截取子串即可。一个字符串就是一份完整的盘面状态递归CTE里每个分支只维护自己的字符串状态转移就是一次字符串拼接操作没有JOIN没有多行复制写起来干净利落。有朋友会问这不是把关系数据模型丢了吗话不能这么说。字符串在这里只是状态的一个紧凑编码SQL照样能对它做约束判断而且所有判断都落在同一个引擎能力上——字符串函数加集合过滤。这更接近状态机的思路状态值就是一个串转移规则就是一次字符串操作集合校验就是过滤条件。在性能上81个字符的字符串操作开销极低递归分支再多也不至于在JOIN上浪费时间。3. 核心实现递归CTE模拟回溯逐格填数有了字符串建模求解就变成一场递归状态搜索。这里直接把递归CTE的三段式拆开看再上完整代码。3.1 递归CTE三段式种子、递推、终止先普及递归CTE的基础写法。一个递归CTE通常长这样WITH RECURSIVE cte_name(columns) AS ( -- 种子查询产生初始集合 SELECT ... UNION ALL -- 递归查询基于上一轮的结果继续产生新行 SELECT ... FROM cte_name, ... WHERE ... ) SELECT * FROM cte_name;每一轮迭代把上一轮所有输出行作为输入通过递归查询生成下一轮输出。直到某一次递归查询不再产生任何新行迭代自然停止。对数独来说种子查询就是初始盘面那一串原始数字递归查询做一件事取出当前盘面中第一个空位枚举这个空位的所有合法候选值每个候选值生成一个新盘面作为一行输出终止条件隐含在递归查询里如果盘面里找不到空位就不产生新行迭代结束。这个设计的妙处在于回溯不需要像命令式语言那样显式退栈。某个分支走到矛盾候选值为空那一轮就不会产生新行分支自动消亡。某个分支把盘面填满也不会再产生新行最终留在结果集里。你只需要在最后加一个WHERE条件过滤出没有空位的盘面答案自然浮现。3.2 完整可运行的PostgreSQL求解SQL直接上代码。这是我在PostgreSQL 13以上版本跑通的核心版本WITH RECURSIVE puzzle AS ( SELECT 530070000600195000098000060800060003400803001700020006060000280000419005000080079::text AS board ), solve(board) AS ( -- 种子初始盘面 SELECT board FROM puzzle UNION ALL -- 递归填第一个空格 SELECT substr(m.board, 1, p.pos - 1) || c.fill || substr(m.board, p.pos 1) FROM solve m CROSS JOIN LATERAL ( SELECT strpos(m.board, 0) AS pos ) p CROSS JOIN LATERAL ( -- 生成1到9作为候选值 SELECT n::text AS fill FROM generate_series(1, 9) AS g(n) WHERE p.pos 0 ) c WHERE p.pos 0 AND NOT EXISTS ( -- 排除同行、同列、同宫已经出现过的数字 SELECT 1 FROM generate_series(1, 9) AS r(r) CROSS JOIN generate_series(1, 9) AS cc(c) WHERE ( r (p.pos - 1) / 9 1 OR c (p.pos - 1) % 9 1 OR ( (r - 1) / 3 ((p.pos - 1) / 9) / 3 AND (c - 1) / 3 ((p.pos - 1) % 9) / 3 ) ) AND substr(m.board, (r - 1) * 9 c, 1) c.fill ) ) SELECT board FROM solve WHERE strpos(board, 0) 0;跑出来的结果我按9位断行534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179可以拿原题手工验算行、列、宫全部满足1到9不重复。这段SQL乍一看有点绕尤其LATERAL和三个generate_series交叉JOIN我一点一点拆开说。先看puzzle这个CTE它只是把题目盘面字符串存成一行。strpos(board, 0)负责找到从左到右第一个空位的下标也就是pos。如果整个盘面已经没有0了strpos返回0外层WHERE直接滤掉递归不会在死分支上继续。LATERAL是PostgreSQL里很实用的特性它允许后面的子查询引用前面FROM项里的列。这里用了两个LATERAL第一个算出pos第二个基于pos生成候选数字c.fill。生成候选值时没有立刻做合法性过滤合法性过滤统一放到外层WHERE的NOT EXISTS里。这样写的好处是生成候选和校验候选两个逻辑分开读代码的人一眼就能看懂。关键NOT EXISTS部分用generate_series(1,9)把所有81个格子遍历一遍对每个格子(r, c)检查两点第一它和当前空位是否在同一行、同一列或同一宫第二它当前的值是否正好等于候选值fill。如果两者同时满足说明候选值在约束链上被占用了候选不合法整个分支被丢弃。反之候选合法递归查询生成一个新盘面substr(board,1,pos-1)是空位前的部分fill是填入的数字substr(board,pos1)是空位后的部分三段拼接成新状态。这套逻辑跑起来递归深度就是盘面中空格数量。上面这题有约30个空格最多递归30层。每层每个分支只填一个格子分支数量取决于每个空格的候选数通常1到9个。只要题目不是极端构造这个SQL在PostgreSQL里几秒内就能出结果。3.3 移植到MySQL、SQL Server和SQLite比赛时手头不一定有PostgreSQL但核心逻辑可以平移。要做的只有三件事替换空位查找函数、替换字符串截取函数、补一个生成1到9数字序列的替代品。先列替换关系PostgreSQL的strpos对应MySQL的LOCATE、SQL Server的CHARINDEX、SQLite的INSTRPostgreSQL的substr对应MySQL的SUBSTRING、SQL Server的SUBSTRING、SQLite的SUBSTRgenerate_series(1,9)这个生成数字序列的利器MySQL 8、SQL Server、SQLite都没有得用一个小递归CTE来造。以MySQL 8.0为例生成1到9可以写成WITH RECURSIVE nums AS ( SELECT 1 AS n UNION ALL SELECT n 1 FROM nums WHERE n 9 )然后把主查询里generate_series的位置换成nums字符串截取用SUBSTRING(board, pos, 1)找第一个0用LOCATE(0, board)。整个SQL的主体结构不用动。SQL Server的写法略有差异它不需要WITH RECURSIVE这个RECURSIVE关键字直接写WITH cte AS (...)就行。但SQL Server有个天坑默认最大递归次数是100。数独随便填几十个空格就肯定超过100个状态直接报错The statement terminated. The maximum recursion 100 has been exhausted。必须在查询末尾加OPTION (MAXRECURSION 0)把递归次数限制关掉。这是我当年第一次跑就踩上的坑排查了好一会儿。SQLite的话用WITH RECURSIVE开头生成数字序列和找空位都跟MySQL差不多注意字符串拼接用的是||这本来就跟标准SQL一致。SQLite对递归深度没有硬编码限制但太深的递归容易撞SQLITE_MAX_EXPR_DEPTH或内存上限极端盘面下需要留意。4. 性能与分支爆炸为什么简单回溯可能跑死SQL把数独解出来不等于完事真正麻烦的是性能。我一开始用递归SQL跑简单题秒出换个中等偏难的题开始卡后来又试了一个只有17个给定数字的极限题直接十几分钟没出结果。原因就是分支爆炸。4.1 搜索空间能有多大数独属于典型的组合难题。空格多的时候每个空格平均有4到5个候选值直接暴力的搜索树是指数型的。在SQL递归CTE里每一轮迭代的行数等于上一轮所有分支乘以各自的候选数最坏情况下乘法级数增长。比如某一层1000个分支每个继续分裂出5个状态下一轮就是5000行再下一轮25000行。递归CTE用UNION ALL把所有这些状态都存下来内存开销和调度负担急剧上升。所以能跑通和能跑快是两回事。简单题空格少、唯一候选多随便跑高难度题不剪枝极易把数据库跑得满头大汗。我还有一个直观体验同样的题目用递归CTE跑跟用Python写回溯跑SQL版本要慢两个数量级。原因不难理解每个分支状态都要生成新字符串、执行若干次子查询和NOT EXISTSSQL的行级迭代本身开销不小。4.2 MRV最少候选优先剪枝既然瓶颈在分支数量第一个优化思路是减少分支。不要在搜索中盲选第一个空格而是每次选择候选数字最少的空格去填。这叫MRV启发式Minimum Remaining Values最小剩余值也叫最大约束优先。说人话就是哪个格子最没得选就先动哪个这能极大削减搜索树宽度。在命令式编程里MRV很好实现扫一遍所有空格统计每个空格的候选数量选最小值递归。在SQL递归CTE里理论上也能做但每层都要对整个盘面做一次候选统计单次迭代代价翻倍换来的是总分支量大幅下降。我试过的经验是对高难度题MRV能把运行时从十几分钟压到几十秒收益非常明显。SQL大致是这样一个子查询SELECT pos, COUNT(*) AS cnt FROM ... GROUP BY pos ORDER BY cnt, pos LIMIT 1;不过说实话在纯SQL递归里做MRV代码复杂度会上升不少。比赛时如果不是特别刁钻的数据直接用顺序填第一个空格也能过想冲击满分效率MRV值得写。4.3 约束传播先扫掉唯一候选再递归另一个更有效的加速手段是约束传播。数独盘面上经常存在这样的空格它的候选数字经过行、列、宫排除后只剩一个。比如某空格所在行已有1、2、3所在列已有4、5、6所在宫已有7、8那它能填的只有9。这种叫唯一候选。对这类空格没必要进递归分支直接填掉即可。用SQL实现约束传播可以在递归之前或每一递归层开头先把所有唯一候选空格找出来批量填入一轮一轮刷直到盘面中没有唯一候选为止。填格子这个重复操作用递归CTE实现很自然每一轮扫描盘面给所有唯一候选空格填上数字盘面更新持续到没有可填的格子再进入需要猜测的回溯阶段。简单和中等级别的题目里约束传播能直接解掉大半根本不需要回溯。我拿一个中等题做过实验先约束传播刷盘把30个空格刷到只剩8个再递归这8个空格一瞬间出答案。这个组合拳比纯回溯快得多现在是我日常解数独题最常用的模式。但要注意约束传播和MRV结合要控制好代码量。比赛题通常不要求把一个高难度数独在1秒内解出来只要稳定给出答案、逻辑清晰就是上乘解法。优化是锦上添花别为了优化把正确性搞丢。4.4 递归深度和平台限制最后说一个所有递归CTE使用者都会撞上的问题递归是有边界的。分三个层面讲。第一是递归深度。PostgreSQL本身不设递归CTE迭代次数上限但受max_stack_depth影响默认值通常是2MB。极端盘面需要填81个空格时可能要执行SET max_stack_depth 4MB甚至更高。SQL Server则明确有MAXRECURSION默认100的限制必须用OPTION (MAXRECURSION 0)才不会被掐断。第二是递归CTE本身的语法限制。在PostgreSQL里递归部分不能使用聚合函数、窗口函数也不能多次引用递归CTE自身。如果我在递归查询里写两次FROM solve做JOIN或者对solve做GROUP BY直接报错。这逼着你把状态转移设计成单个递归引用加相关子查询的结构上面的SQL正是这个结构。需要做统计时通常得把统计放到递归CTE外面。第三是分支数量兑现到物理内存。递归CTE每轮的中间结果都活在内存临时表里分支爆炸时很容易撑爆work_mem然后开始写磁盘临时文件速度断崖式下跌。真遇到极端数据先做约束传播和MRV再考虑提高work_mem参数比如SET work_mem 256MB。这是最后手段不能当常规优化用。5. 实测踩坑与常见问题速查把实际运行、排查、翻车的过程整理成几个高频问题。这些问题你大概率也会碰到反正我是每个都踩过。5.1 递归CTE里最常踩的三个语法坑第一个坑是递归引用只能出现一次。我一开始想在递归查询里同时JOIN solve两次一次取当前盘面一次做统计结果PostgreSQL直接报错recursive reference to query solve must not appear more than once。意思是递归的每一轮只能基于上一轮的结果做一次变换不能在这个变换里自连接。遇到这种需求就得把统计逻辑拆出去。第二个坑是递归部分不允许窗口函数。比如我想在递归查询里用ROW_NUMBER()给分支编号再取第一个空位PostgreSQL会告诉你window function is not allowed in recursive query。解决办法是不要在里面用窗口函数而是把窗口计算放到外层。数独这个场景其实用不着窗口函数strpos找第一个0天然按序刚好绕开。第三个坑和列名作用域有关。LATERAL里引用的列名如果不小心和外层重名经常出现ambiguous column报错。我的习惯是给每个generate_series的表别名配自定义列名比如AS r(r)、AS cc(c)、AS g(n)宁可长一点也好过不知道它在引用谁。递归CTE本来就难读列名一乱就是折磨自己。5.2 明明有解却查不出来我遇到过SQL跑了很久没结果但用Python解明明有解的情况。排查之后发现两个原因。第一个是递归深度限制。SQL Server默认100层填几十个空格的题肯定超过导致递归被强制截断。这时不是题目没解是递归提前终止了解决办法就是OPTION (MAXRECURSION 0)。PostgreSQL一般不会有这个问题但如果你把盘面存成一行一行的表而不是字符串JOIN逻辑复杂起来也容易在某个环节引入死循环或异常分支。第二个原因是分支被错误过滤。如果在NOT EXISTS里把行列宫判断写漏一项比如忘记判断同一宫就会出现某些合法候选被放行但实际非法或所有合法候选全被过滤掉的情况。后者会导致分支提前死亡。调试阶段建议先用一张已知唯一解的简单题打印每一步盘面状态。用PostgreSQL可以临时把最终SELECT改成SELECT board FROM solve LIMIT 50看中间态长啥样非常管用。5.3 如何判断题目是否合法以及多解怎么处理数独题有一个隐含要求给定初始数字应该唯一决定一个解也就是题目合法且唯一。但实际比赛或测试数据不一定会给你保证。用SQL判断合法性其实就是在递归前做一次全局约束检查对所有已填数字看是否存在同行、同列、同宫重复。这条检查可以用一个NOT EXISTS完成查出重复就报题目不合法。多解情况也值得考虑。递归CTE天然会返回所有可行解因为每个能填满盘面的分支都会留在最终结果集里。想确认唯一解在外层做COUNT(*)如果大于1说明题目本身有多解通常意味着给定数字不足。这时即使你取到某个解也不能保证它是出题人期望的那个。竞赛题一般不会出现这种情况但拿网上随便找的题练手时会碰到明白这个逻辑就不会被答案对不上误导。5.4 性能优化参数小结给一个我实测中比较稳的参数组合适用于PostgreSQL跑这道题work_mem开到64MB以上防止中间结果集频繁落盘max_stack_depth调高到4MB以防极端递归深度触发栈保护题目很难时先在外面做约束传播把唯一候选全部填掉再进递归。MySQL 8没有MAXRECURSION参数但递归CTE默认最多1000次迭代递归造数字序列控制不好会很快触顶。SQL Server则必须记得OPTION (MAXRECURSION 0)。SQLite没有递归次数限制参数但SQLITE_MAX_EXPR_DEPTH限制嵌套表达式深度字符串拼接写太深也会报错。6. 一点个人体会写到最后说点题外话。这道题最让我感慨的地方不是SQL能解数独本身而是它逼你换一种思考方式。以前拿到问题我第一反应是用什么算法现在会多问一句这个问题天然的数据结构是什么。数独的数据结构就是位置到值的映射加上三条约束规则。把它编码成字符串还是表都只是选择不同的投影视角重要的是意识到规则本身可以被翻译成集合判断、状态转移可以被翻译成递归CTE。后来我把这套思路用到一个实际排班冲突检测的小工具里效果出奇地好。检验一周内每个员工是否被排了重叠时段本来打算写循环判断想了想这跟数独的约束检查有什么区别把班次表按员工、星期几、时间段展开行列宫换成了员工约束、日期约束、时段约束一条NOT EXISTS直接解决。这道数独题带来的收获远比会解数独大得多。如果你想试先把上面的PostgreSQL版本跑通再用约束传播优化一波然后挑一个只有17个已知数字的极限题试试水。最后留个小彩蛋把盘面字符串设成全0的空盘再跑你会亲眼看到递归CTE如何被分支爆炸折磨到怀疑人生这算是对性能分析最直观的验证。我试过之后再也不说SQL处理不了组合问题了。
