1. 这道题真正在考什么声明式语言里的试错怎么做赛题公布那天我所在的数据库技术群里讨论最多的不是怎么解而是这题有什么实际意义。有人翻出Python十行回溯代码有人说用Excel自带求解器更快。说实话我第一反应也是这样。但真坐下来动手之后我发现仅用SQL处理数独这道题把SQL最反直觉、也最有意思的那一面翻了出来数独求解本质是试错回溯而SQL是声明式语言天生不擅长描述下一步该做什么。回溯法依赖三样东西可变状态、循环、栈。SQL里这三样全没有。没有for循环没有while没有函数调用栈连把某个格子的值改掉这种最基本的操作都要靠字符串拼接或集合运算绕弯子。所以这道题考的不是你会不会数独而是你能不能把一个典型的过程式逻辑完整翻译成集合操作和递归CTE。这个翻译能力恰恰是日常写SQL时最容易被忽视的部分——很多人把SQL当成查表工具却忘了它是图灵完备的查询语言。我最后跑通的方案核心思路可以概括成一句话放弃回退把所有可能的中间状态一次性铺开。过程式回溯是深度优先搜索走不通就往回退SQL版则是让递归CTE一层层展开所有分支每个分支保留一份独立的盘面快照走死的分支自然不会再往下延伸最后活下来的满格状态就是解。这就好比你不是在迷宫里一条道走到黑而是把每个岔路口的所有可能性同时画在地图上。如果你正准备参加类似的SQL比赛或者想把递归CTE真正用到实战里这篇文章应该能帮你省不少时间。我会把盘面编码、约束翻译、递归回溯、剪枝优化、方言差异全部拆开讲包括我第一次跑通时踩过的几个坑。这篇不是纯理论是完整跑过、能复现的方案。2. 开写前的三件事盘面编码、约束翻译、候选值集合2.1 盘面编码为什么用81位字符串而不是9x9表我见过两种主流编码方式。一种是把数独存成(row, col, value)三列的关系表另一种是压成一个81字符的字符串每行9个字符拼接0表示空格。我选后者原因很现实递归CTE里每生成一个分支状态就要复制一份盘面。字符串只要改一个字符就能得到新盘面substr可以精确定位到某个格子关系表则要处理多行自连接状态快照的构造成本明显更高。经典维基百科样例盘面编码如下后面所有代码都用它做测试530070000600195000098000060800060003400803001700020006060000280000419005000080079拆开看就是9行第1行530070000第2行600195000第3行098000060第4行800060003第5行400803001第6行700020006第7行060000280第8行000419005第9行000080079这种编码最大的好处是位置pos从1到81行号、列号、宫号全部可以通过简单的整数运算算出来。你不用建任何辅助表一个字符串就承载了整个盘面。2.2 行、列、宫三条约束怎么翻译成SQL数独只有三条规则同一行不重复、同一列不重复、同一宫内不重复。给定一个格子位置pos它所在的行、列、宫都能用公式算出来然后直接用substr去检查对应位置有没有和目标数字相同的字符。假设当前要填入的数字是digitn是循环变量三个方向的检查表达式如下约束方向涉及位置的计算公式检查方式行约束((pos-1)/9)*9 nn取1~9该行任意格子等于digit则冲突列约束(pos-1)%9 (n-1)*9 1n取1~9该列任意格子等于digit则冲突宫约束宫起始位置 (n/3)*9 (n%3)n取0~8该宫任意格子等于digit则冲突宫起始位置的计算是这里最容易写错的地方我单独说一下。先把格子分成三个行块第1~3行、第4~6行、第7~9行每个行块的起始偏移是((pos-1)/27)*27再看列块第1~3列、第4~6列、第7~9列列偏移是(((pos-1)%9)/3)*3。两者相加再加1才是宫在字符串里的实际起始位置。SQL里的位置索引从1开始不是从0开始这一步漏掉加1整个宫约束就全偏了。宫约束的完整检查写成SQL是这样NOT EXISTS ( SELECT 1 FROM generate_series(0, 8) AS n WHERE substr( board, ((pos - 1) / 27) * 27 (((pos - 1) % 9) / 3) * 3 (n / 3) * 9 (n % 3) 1, 1 ) digit::text )n从0到8n/3得到宫内行偏移n%3得到宫内列偏移一次性覆盖9个格子。这个公式我建议你自己拿笔推一遍比赛现场最耗时间的往往就是这类坐标换算。2.3 候选值的集合表达筛选而不是计算有了三条约束一个空格的候选值就不是算出来的而是筛出来的从1到9里把它所在行、列、宫已经出现的数字全部排除。用SQL来表达就是三条NOT EXISTS组合成一个整体条件。只要1~9里某个数字不违反行、列、宫中的任何一条它就是合法候选。候选值集合的完整判断逻辑如下NOT EXISTS (行检查) AND NOT EXISTS (列检查) AND NOT EXISTS (宫检查)这里我特别想强调一个点候选值不是一上来就算好的而是每条递归分支在决定填入数字时现算。因为每填一个数行、列、宫的局面都变了候选值集合也随之变化。这个动态计算是回溯法的核心也是递归CTE能胜任这件事的关键。3. 核心解法递归CTE把回溯变成状态分支枚举3.1 状态转移从搜索回退到展开所有分支普通回溯法的过程是选一个空格尝试填入某个数字递归下去如果后面走不动了回退到这一步换下一个数字。这个流程在SQL里没法直接写因为没有撤销操作。我的转换思路是这样的每个分支状态就是一份完整的盘面快照。初始状态是原始盘面从某个状态出发找出第一个空格的格子枚举它能填的所有数字每填一个数字就生成一份新的盘面快照加入下一轮递归。如果某个分支走到了死胡同某个空格没有任何合法候选它自然不会再产生子状态等同于过程式里的回退。递归CTE这样做不会产生重复状态因为每轮都是按固定顺序找第一个空格来填。一个状态是怎么来的路径是唯一的不会出现两条不同路径到达同一个盘面的情况。三个要素和过程式回溯一一对应选择LEFT JOIN generate_series(1,9)枚举候选数字约束三条NOT EXISTS过滤合法数字搜索递归CTE自动完成所有分支的展开和裁剪3.2 完整可运行的SQL代码下面这段就是我在PostgreSQL 16上跑通的完整代码直接复制就能用WITH RECURSIVE solve(board, pos) AS ( VALUES ( 530070000600195000098000060800060003400803001700020006060000280000419005000080079, POSITION(0 IN 530070000600195000098000060800060003400803001700020006060000280000419005000080079) ) UNION ALL SELECT substr(s.board, 1, s.pos - 1) || d.digit::text || substr(s.board, s.pos 1), POSITION(0 IN substr(s.board, 1, s.pos - 1) || d.digit::text || substr(s.board, s.pos 1)) FROM solve s LEFT JOIN generate_series(1, 9) AS d(digit) ON TRUE WHERE s.pos 0 AND NOT EXISTS ( SELECT 1 FROM generate_series(1, 9) AS n WHERE substr(s.board, ((s.pos - 1) / 9) * 9 n, 1) d.digit::text ) AND NOT EXISTS ( SELECT 1 FROM generate_series(1, 9) AS n WHERE substr(s.board, (s.pos - 1) % 9 (n - 1) * 9 1, 1) d.digit::text ) AND NOT EXISTS ( SELECT 1 FROM generate_series(0, 8) AS n WHERE substr( s.board, ((s.pos - 1) / 27) * 27 (((s.pos - 1) % 9) / 3) * 3 (n / 3) * 9 (n % 3) 1, 1 ) d.digit::text ) ) SELECT board FROM solve WHERE pos 0;我建议你第一次跑的时候先用这个经典样例。它空格数不算多分支量可控跑完大概能出结果。如果你想看中间某个状态长什么样把最后一行改成SELECT * FROM solve WHERE pos 0 LIMIT 20就能观察到递归过程中的盘面快照。3.3 代码逐段拆解第一行到第三行是递归CTE的初始项。VALUES里第一列是初始盘面第二列是POSITION(0 IN board)也就是第一个空格的位置。如果原始盘面一个空格都没有pos为0递归不会发生直接返回原盘面。UNION ALL之后的递归项里LEFT JOIN generate_series(1,9)负责对当前盘面尝试填入1到9。我特意用了LEFT JOIN而不是子查询是为了让每个合法数字都生成一条独立的新状态。这里generate_series是表函数在PostgreSQL里可以直接跟ON TRUE连接。三条NOT EXISTS前面已经解释过了再补充一个细节SQL中的整数除法。(s.pos - 1) / 9在PostgreSQL里是整除得到0到8的行索引(s.pos - 1) / 27得到0到2的行块索引。如果你用的是MySQL 8这里要写成DIV因为MySQL的/返回的是小数直接比较会出错。递归的终止条件是WHERE s.pos 0。当一个状态没有空格时POSITION(0 IN board)返回0这一行不再进入下一轮递归但它本身作为结果保留在solve表里。最后外层查询WHERE pos 0就是把所有填满的状态取出来——可能有1个也可能有多个取决于数独是否唯一解。4. 第一次跑通后我踩的三个坑深度、坐标、递归项限制4.1 坑一递归深度限制以及一次差点爆栈的调试数独最多81个空格理论上递归深度最多81层一般不会触发深度限制。但我调试时遇到过一次stack depth limit exceeded的报错原因不是深度真的到了81层而是递归分支里出现了状态重复——同一个盘面被反复生成导致无限递归。当时的情况是我把终止条件写错了递归项里用WHERE pos 0终止没错但某个分支的盘面始终有一个空格无法填满而那个空格的候选集合为空。理论上这个分支应该停止扩展但如果约束判断写错导致某个非法数字总是能通过检查这个分支就会一直填同一个空格产生逻辑死循环。不同数据库对递归深度的默认限制我也整理了一下建议比赛前确认清楚数据库递归关键字深度限制相关设置PostgreSQLWITH RECURSIVE没有专门的递归次数限制受max_stack_depth影响MySQL 8WITH RECURSIVEcte_max_recursion_depth默认1000SQL ServerWITH cte AS (...)OPTION (MAXRECURSION 0)表示不限制我的建议是如果你的测试盘面在递归中出现了异常缓慢或报错先用一个小盘面跑递归深度很容易观察。数独本身不会超过81层真正危险的是状态重复。4.2 坑二宫索引公式偏移一位导致假解我最开始写宫约束时把宫起始位置直接写成了((pos-1)/27)*27 (((pos-1)%9)/3)*3忘了加1。结果跑出来是个看起来完美的盘面每行每列都不重复但宫里有重复数字。这种假解比直接报错更难发现因为它不崩、不卡只是答案错。排查的过程我印象很深。我没有直接改代码而是写了一个辅助查询把1到81每个位置的宫坐标打出来和手算的对照表比对。很快发现第28位第4行第1列的宫起始位置算成了54而不是55。因为第4行属于第二个行块偏移是27列块偏移是0正确宫起始是270128才对。如果你也遇到类似问题我推荐一个笨办法先别管整个数独单独验证公式。把每个位置所在的宫第一个格子位置打印出来对照几组手算值确认无误再往下走。这个坑花了我将近一小时写下来就是想让你避开。4.3 坑三递归项里不能用聚合和窗口函数主版本跑通之后我想优化成MRV策略后面会详细讲就试图在递归项里先按空格统计候选数再选出候选数最少的格子。结果PostgreSQL直接报错递归CTE的递归项不允许使用聚合函数、窗口函数和DISTINCT。这是递归CTE一个很容易被忽略的限制。处理办法也很明确把统计和排序放到LATERAL子查询里。递归项本身只保留连接和过滤LATERAL内部可以做聚合再把结果作为递归项的一个字段返回。理解了这一点MRV的实现难度就降下来了。5. 拿分关键约束传播与MRV启发式怎么加进去5.1 先用约束传播把盘面烫平递归回溯能解所有有解数独但性能完全取决于分支数量。我实测下来经典样例算是中等难度比较快就能出结果但遇到一些极端盘面第一个空格就有6、7个候选值分支树瞬间膨胀递归可能卡到跑不完。所以我想做的第一个优化是约束传播在回溯之前先把所有唯一候选的空格全部填掉。如果一个空格的行、列、宫里已经有8个不同数字剩下的那个数字必然就是答案不需要试错。这个过程可以做成一个独立的递归CTE反复扫描盘面、填入唯一候选值直到盘面里不再有唯一候选空格。-- 示意找到唯一候选的空格并填入 -- 实际使用时需要把这段逻辑包进递归CTE的LATERAL中 SELECT pos, digit FROM ( SELECT p.pos, d.digit, COUNT(d.digit) OVER (PARTITION BY p.pos) AS cand_cnt FROM generate_series(1, 81) p LEFT JOIN generate_series(1, 9) d ON NOT EXISTS (行/列/宫冲突) WHERE substr(board, p, 1) 0 ) t WHERE cand_cnt 1 LIMIT 1;对简单盘面约束传播一轮接一轮到最后直接出解完全不需要回溯对困难盘面它也能把空格数降下来让回溯的搜索树小很多。这是所有优化里性价比最高的一步建议优先做。5.2 MRV永远先填候选数最少的格子约束传播做完之后剩下的空格都至少有两个候选值。这时候先填哪个空格就非常重要了。MRVMinimum Remaining Values最少剩余值启发式的思路是每次都选候选值最少的空格去尝试。直觉上很好理解候选值只有2个的格子猜对的概率是二分之一候选值有6个的格子猜对的概率是六分之一。先处理确定性高的格子可以更快暴露矛盾也能更早剪掉死分支。我对比过一个极端情况如果第一个格子有8个候选值它会立刻分出8个分支每个分支又各自分出更多如果先选一个只有2个候选值的格子整个搜索树的分支因子会小很多。对SQL版的递归CTE来说分支数直接决定物化行数和运行时间MRV带来的提升不是百分之几十而是数量级的差异。核心改动只有一处把找第一个空格换成找候选值最少的空格。由于递归项里不能用聚合这一步要放进LATERAL子查询-- 示意MRV选格逻辑放在递归项的 LATERAL 里 SELECT p AS pos FROM ( SELECT p.pos AS p, COUNT(d.digit) AS cnt FROM generate_series(1, 81) p LEFT JOIN generate_series(1, 9) d ON NOT EXISTS (行/列/宫冲突) WHERE substr(board, p, 1) 0 GROUP BY p ) t ORDER BY cnt, p LIMIT 1;把这段逻辑放进LATERAL后递归项就变成了先选出最优空格再枚举该空格的所有合法候选数字生成新分支。主框架完全不用动。5.3 多解、无解与方言适配解题过程中还有两个场景经常需要处理。一是判断数独是否有唯一解二是判断是否有解。做法都很直接有解SELECT board FROM solve WHERE pos 0 LIMIT 1是否唯一SELECT board FROM solve WHERE pos 0 LIMIT 2返回两行就说明至少有两个解无解SELECT count(*) FROM solve WHERE pos 0结果为0就是无解如果比赛环境不是PostgreSQL需要适配方言差异。我列一个常用对照表功能PostgreSQLMySQL 8SQL Server找子串位置POSITION(0 IN s)LOCATE(0, s)CHARINDEX(0, s)生成1~9generate_series(1,9)递归数字表或UNION ALL SELECTROW_NUMBER() OVER (...)配合数字表整数除法/DIV/字符串拼接||CONCAT()或CONCAT()递归深度控制无专门参数cte_max_recursion_depthOPTION (MAXRECURSION 0)我个人强烈建议用PostgreSQL来准备这类题目generate_series和POSITION配合递归CTE实在太顺手了。如果你只能用MySQL或SQL Server优先把数字生成表提前建好不要每次递归都临时拼。6. 回到2025赛题现场我的答题顺序与复盘心得如果我在赛场上再遇到这道题我不会直接写最复杂的那版而是按这个顺序来第一步先写约束传播版。它代码量小、思路简单能把easy和medium难度的盘面直接解掉。这道题如果按测试用例数量计分先把能拿的分拿稳最重要。第二步再写完整回溯版。这个版本保证所有有解数独都能解但性能受第一个空格候选数影响大。写了约束传播之后回溯要处理的空格已经少了一大半性能压力小很多。第三步跑通之后再考虑加MRV。如果时间不够我宁愿只换一行选格逻辑——把固定取POSITION(0 IN board)改成MRV选格——也不去动整体结构。每改动一次结构就意味着所有测试用例要重新验证一遍。说到验证我自己的习惯是准备三个不同难度的盘面一个简单盘面空格少、唯一候选多一个中等盘面经典样例那类一个困难盘面故意挖空很多、候选值分布很平均。三个盘面都能在合理时间内出解代码才算合格。只跑一个盘面通过不算数。最后聊一点个人体会。这道题给我最大的收获不是SQL能解数独这个结论而是我发现递归CTE表达遍历和分支搜索的能力被严重低估了。日常开发里有向无环图的路径遍历、BOM层级展开、组织树递归汇总本质上都是同一类问题从一个状态出发逐步生成后续状态。数独只是把这类问题放到了一个最显眼、最有趣的包装里。如果你第一次写完跑不动先别急着怀疑递归逻辑。第二条建议是我用实际时间换来的先检查盘面编码长度是不是81位再检查三个位置公式的索引偏移。这两处出错率最高而且都表现为答案不对但表面完整。确保它们没问题你的SQL数独求解器就成功了一大半。
1. 这道题真正在考什么声明式语言里的试错怎么做赛题公布那天我所在的数据库技术群里讨论最多的不是怎么解而是这题有什么实际意义。有人翻出Python十行回溯代码有人说用Excel自带求解器更快。说实话我第一反应也是这样。但真坐下来动手之后我发现仅用SQL处理数独这道题把SQL最反直觉、也最有意思的那一面翻了出来数独求解本质是试错回溯而SQL是声明式语言天生不擅长描述下一步该做什么。回溯法依赖三样东西可变状态、循环、栈。SQL里这三样全没有。没有for循环没有while没有函数调用栈连把某个格子的值改掉这种最基本的操作都要靠字符串拼接或集合运算绕弯子。所以这道题考的不是你会不会数独而是你能不能把一个典型的过程式逻辑完整翻译成集合操作和递归CTE。这个翻译能力恰恰是日常写SQL时最容易被忽视的部分——很多人把SQL当成查表工具却忘了它是图灵完备的查询语言。我最后跑通的方案核心思路可以概括成一句话放弃回退把所有可能的中间状态一次性铺开。过程式回溯是深度优先搜索走不通就往回退SQL版则是让递归CTE一层层展开所有分支每个分支保留一份独立的盘面快照走死的分支自然不会再往下延伸最后活下来的满格状态就是解。这就好比你不是在迷宫里一条道走到黑而是把每个岔路口的所有可能性同时画在地图上。如果你正准备参加类似的SQL比赛或者想把递归CTE真正用到实战里这篇文章应该能帮你省不少时间。我会把盘面编码、约束翻译、递归回溯、剪枝优化、方言差异全部拆开讲包括我第一次跑通时踩过的几个坑。这篇不是纯理论是完整跑过、能复现的方案。2. 开写前的三件事盘面编码、约束翻译、候选值集合2.1 盘面编码为什么用81位字符串而不是9x9表我见过两种主流编码方式。一种是把数独存成(row, col, value)三列的关系表另一种是压成一个81字符的字符串每行9个字符拼接0表示空格。我选后者原因很现实递归CTE里每生成一个分支状态就要复制一份盘面。字符串只要改一个字符就能得到新盘面substr可以精确定位到某个格子关系表则要处理多行自连接状态快照的构造成本明显更高。经典维基百科样例盘面编码如下后面所有代码都用它做测试530070000600195000098000060800060003400803001700020006060000280000419005000080079拆开看就是9行第1行530070000第2行600195000第3行098000060第4行800060003第5行400803001第6行700020006第7行060000280第8行000419005第9行000080079这种编码最大的好处是位置pos从1到81行号、列号、宫号全部可以通过简单的整数运算算出来。你不用建任何辅助表一个字符串就承载了整个盘面。2.2 行、列、宫三条约束怎么翻译成SQL数独只有三条规则同一行不重复、同一列不重复、同一宫内不重复。给定一个格子位置pos它所在的行、列、宫都能用公式算出来然后直接用substr去检查对应位置有没有和目标数字相同的字符。假设当前要填入的数字是digitn是循环变量三个方向的检查表达式如下约束方向涉及位置的计算公式检查方式行约束((pos-1)/9)*9 nn取1~9该行任意格子等于digit则冲突列约束(pos-1)%9 (n-1)*9 1n取1~9该列任意格子等于digit则冲突宫约束宫起始位置 (n/3)*9 (n%3)n取0~8该宫任意格子等于digit则冲突宫起始位置的计算是这里最容易写错的地方我单独说一下。先把格子分成三个行块第1~3行、第4~6行、第7~9行每个行块的起始偏移是((pos-1)/27)*27再看列块第1~3列、第4~6列、第7~9列列偏移是(((pos-1)%9)/3)*3。两者相加再加1才是宫在字符串里的实际起始位置。SQL里的位置索引从1开始不是从0开始这一步漏掉加1整个宫约束就全偏了。宫约束的完整检查写成SQL是这样NOT EXISTS ( SELECT 1 FROM generate_series(0, 8) AS n WHERE substr( board, ((pos - 1) / 27) * 27 (((pos - 1) % 9) / 3) * 3 (n / 3) * 9 (n % 3) 1, 1 ) digit::text )n从0到8n/3得到宫内行偏移n%3得到宫内列偏移一次性覆盖9个格子。这个公式我建议你自己拿笔推一遍比赛现场最耗时间的往往就是这类坐标换算。2.3 候选值的集合表达筛选而不是计算有了三条约束一个空格的候选值就不是算出来的而是筛出来的从1到9里把它所在行、列、宫已经出现的数字全部排除。用SQL来表达就是三条NOT EXISTS组合成一个整体条件。只要1~9里某个数字不违反行、列、宫中的任何一条它就是合法候选。候选值集合的完整判断逻辑如下NOT EXISTS (行检查) AND NOT EXISTS (列检查) AND NOT EXISTS (宫检查)这里我特别想强调一个点候选值不是一上来就算好的而是每条递归分支在决定填入数字时现算。因为每填一个数行、列、宫的局面都变了候选值集合也随之变化。这个动态计算是回溯法的核心也是递归CTE能胜任这件事的关键。3. 核心解法递归CTE把回溯变成状态分支枚举3.1 状态转移从搜索回退到展开所有分支普通回溯法的过程是选一个空格尝试填入某个数字递归下去如果后面走不动了回退到这一步换下一个数字。这个流程在SQL里没法直接写因为没有撤销操作。我的转换思路是这样的每个分支状态就是一份完整的盘面快照。初始状态是原始盘面从某个状态出发找出第一个空格的格子枚举它能填的所有数字每填一个数字就生成一份新的盘面快照加入下一轮递归。如果某个分支走到了死胡同某个空格没有任何合法候选它自然不会再产生子状态等同于过程式里的回退。递归CTE这样做不会产生重复状态因为每轮都是按固定顺序找第一个空格来填。一个状态是怎么来的路径是唯一的不会出现两条不同路径到达同一个盘面的情况。三个要素和过程式回溯一一对应选择LEFT JOIN generate_series(1,9)枚举候选数字约束三条NOT EXISTS过滤合法数字搜索递归CTE自动完成所有分支的展开和裁剪3.2 完整可运行的SQL代码下面这段就是我在PostgreSQL 16上跑通的完整代码直接复制就能用WITH RECURSIVE solve(board, pos) AS ( VALUES ( 530070000600195000098000060800060003400803001700020006060000280000419005000080079, POSITION(0 IN 530070000600195000098000060800060003400803001700020006060000280000419005000080079) ) UNION ALL SELECT substr(s.board, 1, s.pos - 1) || d.digit::text || substr(s.board, s.pos 1), POSITION(0 IN substr(s.board, 1, s.pos - 1) || d.digit::text || substr(s.board, s.pos 1)) FROM solve s LEFT JOIN generate_series(1, 9) AS d(digit) ON TRUE WHERE s.pos 0 AND NOT EXISTS ( SELECT 1 FROM generate_series(1, 9) AS n WHERE substr(s.board, ((s.pos - 1) / 9) * 9 n, 1) d.digit::text ) AND NOT EXISTS ( SELECT 1 FROM generate_series(1, 9) AS n WHERE substr(s.board, (s.pos - 1) % 9 (n - 1) * 9 1, 1) d.digit::text ) AND NOT EXISTS ( SELECT 1 FROM generate_series(0, 8) AS n WHERE substr( s.board, ((s.pos - 1) / 27) * 27 (((s.pos - 1) % 9) / 3) * 3 (n / 3) * 9 (n % 3) 1, 1 ) d.digit::text ) ) SELECT board FROM solve WHERE pos 0;我建议你第一次跑的时候先用这个经典样例。它空格数不算多分支量可控跑完大概能出结果。如果你想看中间某个状态长什么样把最后一行改成SELECT * FROM solve WHERE pos 0 LIMIT 20就能观察到递归过程中的盘面快照。3.3 代码逐段拆解第一行到第三行是递归CTE的初始项。VALUES里第一列是初始盘面第二列是POSITION(0 IN board)也就是第一个空格的位置。如果原始盘面一个空格都没有pos为0递归不会发生直接返回原盘面。UNION ALL之后的递归项里LEFT JOIN generate_series(1,9)负责对当前盘面尝试填入1到9。我特意用了LEFT JOIN而不是子查询是为了让每个合法数字都生成一条独立的新状态。这里generate_series是表函数在PostgreSQL里可以直接跟ON TRUE连接。三条NOT EXISTS前面已经解释过了再补充一个细节SQL中的整数除法。(s.pos - 1) / 9在PostgreSQL里是整除得到0到8的行索引(s.pos - 1) / 27得到0到2的行块索引。如果你用的是MySQL 8这里要写成DIV因为MySQL的/返回的是小数直接比较会出错。递归的终止条件是WHERE s.pos 0。当一个状态没有空格时POSITION(0 IN board)返回0这一行不再进入下一轮递归但它本身作为结果保留在solve表里。最后外层查询WHERE pos 0就是把所有填满的状态取出来——可能有1个也可能有多个取决于数独是否唯一解。4. 第一次跑通后我踩的三个坑深度、坐标、递归项限制4.1 坑一递归深度限制以及一次差点爆栈的调试数独最多81个空格理论上递归深度最多81层一般不会触发深度限制。但我调试时遇到过一次stack depth limit exceeded的报错原因不是深度真的到了81层而是递归分支里出现了状态重复——同一个盘面被反复生成导致无限递归。当时的情况是我把终止条件写错了递归项里用WHERE pos 0终止没错但某个分支的盘面始终有一个空格无法填满而那个空格的候选集合为空。理论上这个分支应该停止扩展但如果约束判断写错导致某个非法数字总是能通过检查这个分支就会一直填同一个空格产生逻辑死循环。不同数据库对递归深度的默认限制我也整理了一下建议比赛前确认清楚数据库递归关键字深度限制相关设置PostgreSQLWITH RECURSIVE没有专门的递归次数限制受max_stack_depth影响MySQL 8WITH RECURSIVEcte_max_recursion_depth默认1000SQL ServerWITH cte AS (...)OPTION (MAXRECURSION 0)表示不限制我的建议是如果你的测试盘面在递归中出现了异常缓慢或报错先用一个小盘面跑递归深度很容易观察。数独本身不会超过81层真正危险的是状态重复。4.2 坑二宫索引公式偏移一位导致假解我最开始写宫约束时把宫起始位置直接写成了((pos-1)/27)*27 (((pos-1)%9)/3)*3忘了加1。结果跑出来是个看起来完美的盘面每行每列都不重复但宫里有重复数字。这种假解比直接报错更难发现因为它不崩、不卡只是答案错。排查的过程我印象很深。我没有直接改代码而是写了一个辅助查询把1到81每个位置的宫坐标打出来和手算的对照表比对。很快发现第28位第4行第1列的宫起始位置算成了54而不是55。因为第4行属于第二个行块偏移是27列块偏移是0正确宫起始是270128才对。如果你也遇到类似问题我推荐一个笨办法先别管整个数独单独验证公式。把每个位置所在的宫第一个格子位置打印出来对照几组手算值确认无误再往下走。这个坑花了我将近一小时写下来就是想让你避开。4.3 坑三递归项里不能用聚合和窗口函数主版本跑通之后我想优化成MRV策略后面会详细讲就试图在递归项里先按空格统计候选数再选出候选数最少的格子。结果PostgreSQL直接报错递归CTE的递归项不允许使用聚合函数、窗口函数和DISTINCT。这是递归CTE一个很容易被忽略的限制。处理办法也很明确把统计和排序放到LATERAL子查询里。递归项本身只保留连接和过滤LATERAL内部可以做聚合再把结果作为递归项的一个字段返回。理解了这一点MRV的实现难度就降下来了。5. 拿分关键约束传播与MRV启发式怎么加进去5.1 先用约束传播把盘面烫平递归回溯能解所有有解数独但性能完全取决于分支数量。我实测下来经典样例算是中等难度比较快就能出结果但遇到一些极端盘面第一个空格就有6、7个候选值分支树瞬间膨胀递归可能卡到跑不完。所以我想做的第一个优化是约束传播在回溯之前先把所有唯一候选的空格全部填掉。如果一个空格的行、列、宫里已经有8个不同数字剩下的那个数字必然就是答案不需要试错。这个过程可以做成一个独立的递归CTE反复扫描盘面、填入唯一候选值直到盘面里不再有唯一候选空格。-- 示意找到唯一候选的空格并填入 -- 实际使用时需要把这段逻辑包进递归CTE的LATERAL中 SELECT pos, digit FROM ( SELECT p.pos, d.digit, COUNT(d.digit) OVER (PARTITION BY p.pos) AS cand_cnt FROM generate_series(1, 81) p LEFT JOIN generate_series(1, 9) d ON NOT EXISTS (行/列/宫冲突) WHERE substr(board, p, 1) 0 ) t WHERE cand_cnt 1 LIMIT 1;对简单盘面约束传播一轮接一轮到最后直接出解完全不需要回溯对困难盘面它也能把空格数降下来让回溯的搜索树小很多。这是所有优化里性价比最高的一步建议优先做。5.2 MRV永远先填候选数最少的格子约束传播做完之后剩下的空格都至少有两个候选值。这时候先填哪个空格就非常重要了。MRVMinimum Remaining Values最少剩余值启发式的思路是每次都选候选值最少的空格去尝试。直觉上很好理解候选值只有2个的格子猜对的概率是二分之一候选值有6个的格子猜对的概率是六分之一。先处理确定性高的格子可以更快暴露矛盾也能更早剪掉死分支。我对比过一个极端情况如果第一个格子有8个候选值它会立刻分出8个分支每个分支又各自分出更多如果先选一个只有2个候选值的格子整个搜索树的分支因子会小很多。对SQL版的递归CTE来说分支数直接决定物化行数和运行时间MRV带来的提升不是百分之几十而是数量级的差异。核心改动只有一处把找第一个空格换成找候选值最少的空格。由于递归项里不能用聚合这一步要放进LATERAL子查询-- 示意MRV选格逻辑放在递归项的 LATERAL 里 SELECT p AS pos FROM ( SELECT p.pos AS p, COUNT(d.digit) AS cnt FROM generate_series(1, 81) p LEFT JOIN generate_series(1, 9) d ON NOT EXISTS (行/列/宫冲突) WHERE substr(board, p, 1) 0 GROUP BY p ) t ORDER BY cnt, p LIMIT 1;把这段逻辑放进LATERAL后递归项就变成了先选出最优空格再枚举该空格的所有合法候选数字生成新分支。主框架完全不用动。5.3 多解、无解与方言适配解题过程中还有两个场景经常需要处理。一是判断数独是否有唯一解二是判断是否有解。做法都很直接有解SELECT board FROM solve WHERE pos 0 LIMIT 1是否唯一SELECT board FROM solve WHERE pos 0 LIMIT 2返回两行就说明至少有两个解无解SELECT count(*) FROM solve WHERE pos 0结果为0就是无解如果比赛环境不是PostgreSQL需要适配方言差异。我列一个常用对照表功能PostgreSQLMySQL 8SQL Server找子串位置POSITION(0 IN s)LOCATE(0, s)CHARINDEX(0, s)生成1~9generate_series(1,9)递归数字表或UNION ALL SELECTROW_NUMBER() OVER (...)配合数字表整数除法/DIV/字符串拼接||CONCAT()或CONCAT()递归深度控制无专门参数cte_max_recursion_depthOPTION (MAXRECURSION 0)我个人强烈建议用PostgreSQL来准备这类题目generate_series和POSITION配合递归CTE实在太顺手了。如果你只能用MySQL或SQL Server优先把数字生成表提前建好不要每次递归都临时拼。6. 回到2025赛题现场我的答题顺序与复盘心得如果我在赛场上再遇到这道题我不会直接写最复杂的那版而是按这个顺序来第一步先写约束传播版。它代码量小、思路简单能把easy和medium难度的盘面直接解掉。这道题如果按测试用例数量计分先把能拿的分拿稳最重要。第二步再写完整回溯版。这个版本保证所有有解数独都能解但性能受第一个空格候选数影响大。写了约束传播之后回溯要处理的空格已经少了一大半性能压力小很多。第三步跑通之后再考虑加MRV。如果时间不够我宁愿只换一行选格逻辑——把固定取POSITION(0 IN board)改成MRV选格——也不去动整体结构。每改动一次结构就意味着所有测试用例要重新验证一遍。说到验证我自己的习惯是准备三个不同难度的盘面一个简单盘面空格少、唯一候选多一个中等盘面经典样例那类一个困难盘面故意挖空很多、候选值分布很平均。三个盘面都能在合理时间内出解代码才算合格。只跑一个盘面通过不算数。最后聊一点个人体会。这道题给我最大的收获不是SQL能解数独这个结论而是我发现递归CTE表达遍历和分支搜索的能力被严重低估了。日常开发里有向无环图的路径遍历、BOM层级展开、组织树递归汇总本质上都是同一类问题从一个状态出发逐步生成后续状态。数独只是把这类问题放到了一个最显眼、最有趣的包装里。如果你第一次写完跑不动先别急着怀疑递归逻辑。第二条建议是我用实际时间换来的先检查盘面编码长度是不是81位再检查三个位置公式的索引偏移。这两处出错率最高而且都表现为答案不对但表面完整。确保它们没问题你的SQL数独求解器就成功了一大半。
