比赛群里的消息到现在还在刷屏一是有不少人问“SQL 也能解数独”二是问得更具体的“位运算到底是怎么个玩法”我趁记忆还热把这次用 PostgreSQL 解题的全过程整理成文。这道题表面上是数独骨子里是一个集合约束问题SQL 最擅长的就是集合而位运算则是把集合塞进一个整数里的高效手段。整篇你会看到常规 SQL 解法为什么会慢、位运算怎么把候选集变成一个 9 位二进制数、以及我为了拿名次在递归里加的几层剪枝。先说结论数独不是数学题是逻辑题用集合的视角去看每一步都是在做“排除法”。PostgreSQL 的递归 CTE、LATERAL 子查询、聚合函数 bit_or以及字符串切片能力刚好能把这套排除法完整表达出来。位运算的优势不在于“炫技”而在于它把集合运算压缩成了整数上的与、或、非在千百万次迭代里省掉的不只是代码行数而是数量级的扫描成本。1. 这题怎么会想到用位运算1.1 数独的本质是集合约束数独的规则三句话每行 1-9 不重复每列 1-9 不重复每宫3x3 小方块1-9 不重复。把这三句话翻译成数据处理语言就是每个空格的可选值等于“全集 {1..9}” 减去“同一行已出现值、同一列已出现值、同一宫已出现值”的并集。一个空格能填什么不取决于别的花哨条件只取决于三个集合。既然要频繁做“取并集、取补集、判断某个值是否在集合里”那就天然适合位运算一行、一列、一宫各用一个整数每个二进制位代表一个数字是否出现过。1 表示已出现0 表示没出现。数字 d 对应的位是 d-1也就是1 (d-1)。这个映射是我解题时最重要的一个决策。因为一旦把“集合”落成“整数”PostgreSQL 里大量现成的整数运算符和聚合函数都能直接上而不是用 EXISTS、IN、POSITION 这种逐条匹配的方式。1.2 常规 SQL 解法的三个硬伤比赛现场不少选手用的是传统思路把棋盘存成 9 行递归里逐个空格尝试 1-9每试一个数字就扫描一次当前行、列、宫有没有重复。听起来很直接但实际写起来有三个很吃亏的地方。第一冲突检查成本高。填一个空格要检查三个区域每个区域最多 9 个格子如果用字符串表达棋盘状态那每层递归都在做 81 字符的切片和 POSITION状态一深字符扫描量直线上升。第二候选集合无法复用。常规写法里同一个空格在不同递归深处会被反复重新计算候选值因为每次填完一个数字整行的状态都变了前一层算过的东西基本作废。第三分支选择傻。大多数选手按空格坐标从小到大顺序尝试1 到 9 挨个试。遇到需要回溯的题搜索树会非常胖。我后面会讲把“候选数最少的空格优先处理”这个启发式做成排序比任何事后优化都管用。1.3 位运算天然适配的三个理由位运算版方案里三个区域集合是三个整数row_mask、col_mask、box_mask。任意空格的候选掩码是511 ~(row_mask | col_mask | box_mask)。511 是(19)-1也就是二进制低 9 位全 1对应集合{1,2,...,9}。为什么说这个表达天然适配第一集合运算变成常数时间的整数运算一次 OR 合并三个区域一次 NOT 取补集一次 AND 求交集不管你之前处理过多少格子开销都一样。第二PostgreSQL 有bit_or聚合函数可以直接对一组已填数字做按位或一行 SQL 就能算出某个区域“已出现哪些数字”。第三判断一个集合里有几个候选值用pg_popcount统计二进制里的 1 就可以这个函数在 PostgreSQL 13 之后都有老版本可以用字符串替换数 0 凑合。这套模型一旦建立整个求解过程就变成一个非常干净的“状态转移”棋盘状态是多行递归产生的每个状态里嵌着若干整数掩码而不是一堆需要反复 JOIN 的关系表。2. 环境准备与关键知识点2.1 比赛环境与工具比赛用的是 PostgreSQL 15客户端连接后直接在 SQL 编辑器里写查询。我个人环境是本地 Windows 跑一个 PostgreSQL 15 实例用 DBeaver 连。比赛不允许使用外部程序也就是不能把棋盘抽出去用 Python 算完再把答案塞回来所有逻辑必须落在 SQL 里。用 PostgreSQL 有一个很重要的优势它的WITH RECURSIVE语法非常成熟能承担真正的递归搜索同时LATERAL子查询可以在递归内部做“对当前状态求候选值”这种依赖上下文的计算。加上字符串函数left、right、substring都很顺手用它做状态传递几乎不需要额外建临时表。2.2 棋盘输入与状态表达比赛给的棋盘就是一个 81 个字符的字符串0 表示空格。我第一反应是拆成行、列、值三列存进临时表但后来发现这种关系型表达在递归里很啰嗦。递归每次要传递整个棋盘状态用临时表要么每次 DELETE/INSERT要么每层递归保留一份快照读写成本都高。最终我选择把棋盘编码成字符串作为递归 CTE 的一个字段。字符在字符串里的位置 p从 1 开始对应着坐标行号(p - 1) / 9 1列号(p - 1) % 9 1宫号0 到 8(((p - 1) / 9) / 3) * 3 ((p - 1) % 9) / 3这个坐标映射是整个实现的地基不能算错。宫号公式尤其容易错我一开始写成 1-based结果候选计算全偏后来统一切成 0-based 才理顺。2.3 位掩码的三板斧正式写代码前把三个核心操作讲明白1 (v - 1)把数字 v 转成掩码。数字 5 是1 4 16二进制第 4 位为 1。bit_or(1 (v - 1))对一组已填数字求并集。这是 PostgreSQL 的聚合函数输入一堆整数掩码输出按位或的结果。511 ~m对掩码取补集并把范围限制在低 9 位。得到的是该区域还没有出现过的数字集合。数字集合和掩码之间互转是这套解法里最高频的操作我建议在草稿纸上先写三遍再动手后面所有 SQL 都基于这三个式子展开。3. 核心实操候选集计算与确定性求解3.1 一次查询算出全盘所有候选先给一个可以直接跑的核心片段。我把棋盘字符串写死方便读者本地复现。这段代码干的事是把 81 个字符拆成带坐标的格子用bit_or聚合出每行、每列、每宫的“已出现掩码”然后对每个空格求候选掩码。WITH board AS ( SELECT p, (p - 1) / 9 1 AS r, (p - 1) % 9 1 AS c, (((p - 1) / 9) / 3) * 3 ((p - 1) % 9) / 3 AS b, substring(530070000600195000098000060800060003400803001700020006060000280000419005000080079 FROM p FOR 1)::int AS v FROM generate_series(1, 81) p ), row_m AS ( SELECT r, COALESCE(bit_or(1 (v - 1)), 0)::int AS m FROM board WHERE v 0 GROUP BY r ), col_m AS ( SELECT c, COALESCE(bit_or(1 (v - 1)), 0)::int AS m FROM board WHERE v 0 GROUP BY c ), box_m AS ( SELECT b, COALESCE(bit_or(1 (v - 1)), 0)::int AS m FROM board WHERE v 0 GROUP BY b ) SELECT b.p, b.r, b.c, 511 ~(COALESCE(rm.m, 0) | COALESCE(cm.m, 0) | COALESCE(bm.m, 0)) AS cand FROM board b LEFT JOIN row_m rm ON rm.r b.r LEFT JOIN col_m cm ON cm.c b.c LEFT JOIN box_m bm ON bm.b b.b WHERE b.v 0 ORDER BY b.p;这一段是我比赛时最早就跑通的查询。重点要说的是COALESCE如果一个区域内没有任何已填数字bit_or是 NULLNULL 参与位运算会直接把结果变成 NULL进而把整个候选掩码污染成 NULL。这是最典型的坑后来我在所有聚合处都包了一层 COALESCE。你跑一下这个查询会看到每个空格的候选都是一个 0 到 511 之间的整数。比如第 1 行第 3 列行内已有 5、3列内已有 8宫内已有 5、3、6、9、8最终剩{1,2,4,7}掩码是 75二进制1001011的四个 1 位正好对应数字 1、2、4、7。这个输出可以拿来和人工推理核对我当时就是靠这种单格核对发现宫号公式写反的。3.2 唯一候选格先填确定性层拿到全盘候选以后最自然的策略不是直接开递归而是先“白捡”那些只可能填一个数字的空格。候选掩码里只有 1 个位为 1说明这个格子的值被行、列、宫三个方向夹逼得死死得很不用猜。在代码里这种情况就是pg_popcount(cand) 1。我写了一个函数每次处理一个唯一候选格返回新的棋盘字符串CREATE FUNCTION fill_once(s text) RETURNS text LANGUAGE sql AS $$ WITH board AS ( SELECT p, (p - 1) / 9 1 AS r, (p - 1) % 9 1 AS c, (((p - 1) / 9) / 3) * 3 ((p - 1) % 9) / 3 AS b, substring(s FROM p FOR 1)::int AS v FROM generate_series(1, 81) p ), cands AS ( -- 候选计算逻辑同上一节略 SELECT p, cand, 511 ~(...) AS cand1 ... ) SELECT left(s, p - 1) || d || right(s, 81 - p) FROM cands CROSS JOIN LATERAL generate_series(1, 9) d WHERE cand_count 1 AND (cand1 (1 (d - 1))) 0 LIMIT 1 $$;这个函数的意义在于把整个求解过程拆成两层外层用普通 SQL 反复调用fill_once把所有能确定的格子全部填完直到返回值不再变化说明棋盘进入“必须猜”的阶段再交给递归回溯。实际比赛里大部分题目在确定性层就能解掉一大半空格搜索树的深度和宽度都缩了一大截。很多选手一上来就递归白白把确定性步骤的迭代次数也算进搜索里慢是必然的。3.3 从掩码还原数字的两种姿势填一个空格时需要从候选掩码知道到底该填哪个数字。最省事的是generate_series(1, 9)配合(mask (1 (d - 1))) 0判断这个写法通用且直观前面已经用到。另一个姿势是把掩码转成 bit 串再数 1SELECT mask::bit(9) :: text;比如 75 转成01001011从低位到高位第 1、2、4、7 位是 1对应数字 1、2、4、7。这种写法在调试时非常舒服因为你能直观看到“哪些位还开着”。但要统计候选个数时比pg_popcount慢很多所以我只在人工核对时用 bit 串代码里全部用pg_popcount。4. 递归回溯 MRV 让搜索量骤减4.1 状态编码与递归框架确定性层跑完以后剩下的空格通常各自有 2 到 5 个候选。这时候必须做回溯选一个空格尝试填某个数字递归往下如果走不下去就回到上一层换数字。在 SQL 里我利用WITH RECURSIVE的并行特性写搜索。每一轮递归产生棋盘状态的新副本每个副本代表一条搜索路径。核心框架如下WITH RECURSIVE search(s) AS ( SELECT 530070000600195000098000060800060003400803001700020006060000280000419005000080079::text UNION ALL SELECT left(s, t.p - 1) || g.d::text || right(s, 81 - t.p) FROM search CROSS JOIN LATERAL ( SELECT p, cand, cnt FROM bit_candidates(s) WHERE cnt 0 ORDER BY cnt, p LIMIT 1 ) t CROSS JOIN LATERAL generate_series(1, 9) g(d) WHERE (t.cand (1 (g.d - 1))) 0 ) SELECT DISTINCT s FROM search WHERE position(0 IN s) 0;这里的bit_candidates(s)是前面候选计算逻辑包成的函数输入棋盘字符串输出每个空格的位置、候选掩码、候选个数。由于函数里已经用到了bit_or聚合整个回调在递归里算得上轻量。LATERAL 的妙处在于它让“选空格”这个动作和“当前的棋盘字符串 s”强绑定。每一条递归路径有各自的 s因此各有各的候选集互不干扰。这正是 SQL 处理回溯的天然姿势不手动维护调用栈而是靠递归行的多路展开。4.2 MRV 启发式先填最难的空格搜索性能的关键不在递归本身而在“选哪个空格先填”。我选了候选个数最少的空格这就是经典的 MRVMinimum Remaining Values启发式说人话就是哪个空格最没得选就先处理哪个。上面代码里ORDER BY cnt, p就是 MRV 的实现。候选越少接下来产生的分支就越少整个搜索树就越窄。我拿常规顺序按坐标从小到大和 MRV 各跑了一遍常规顺序经常在难题上跑几十秒还在原地磨蹭MRV 基本上几秒内就出结果。这个差距甚至比位运算本身还大。结合确定性层整个流程变成反复填唯一候选空格直到棋盘稳定对每个空格计算候选掩码选候选数最少的那个对该空格的每个候选数字分别递归展开递归路径上重复步骤 1这个“确定性优先 MRV 分支”的组合让我在比赛里几乎没有遇到任何一道题需要走深超过几十层的回溯。深搜最怕的是又深又宽这个组合把两边都压住了。4.3 与常规方案的真实性能对照比赛结束后我拉了一张对照表用同一台机器、同一道题跑了三种实现。数据不敢说多严谨但趋势很有代表性方案候选计算方式分支策略一道普通题的耗时感受常规字符串扫描每步用 POSITION 扫行、列、宫按坐标顺序试 1-9十几秒到几十秒关系表集合判断建临时表记录已填数EXISTS 查冲突按坐标顺序试 1-95 到 15 秒左右位运算 MRVbit_or 聚合并集整数与/非求候选唯一候选优先最少候选空格优先稳定在 1 秒内到 3 秒位运算版本不只是块头小关键是它把“算一次候选”的成本从 O(81) 的字符串扫描降到了 O(1) 的整数运算。递归成千上万次以后这个差距就是秒级和分钟级的差距。比赛环境下还有 statement_timeout常规方案最容易死在超时上。5. 比赛踩坑记录与优化清单5.1 五个自查点动手前先确认我把自己调试过程中踩过的坑整理成一份自查清单后来比赛时我每写一个版本都会先过一遍。第一bit_or对空组返回 NULL所有聚合处必须套COALESCE(..., 0)。第二数字 d 对应的掩码是1 (d - 1)不是1 d这个偏离会让所有候选集合整体错位一位而且看起来煞有介事特别难发现。第三宫号用 0-based 计算(((p - 1) / 9) / 3) * 3 ((p - 1) % 9) / 3不要混用 1-based 的除法。第四字符串索引从 1 开始但很多语言习惯是 0 开始left(s, p - 1)和right(s, 81 - p)的思路要想清楚。第五递归里如果发现某个空格候选掩码变成 0说明当前路径已经矛盾要让这条路径直接消失而不是继续填。5.2 调试技巧先在 4x4 上验证位掩码在 9x9 数独里是 9 位在 4x4 迷你数独里就是 4 位。比赛前我在本地先用 4x4 的棋盘把整个递归框架跑通因为 4x4 的棋盘小、状态少所有逻辑错误都能更早暴露出来。而且 4x4 的宫号公式、字符串拼接逻辑和 9x9 完全同构只是集合从 511 变成 15改一个数字就能跑。这个建议对所有人都适用。不要一上来直接盯着 81 字符的大字符串调试bug 藏在一堆数字里很难定位。先把模型缩小验证算法本身正确再放大到真实题目是效率最高的路径。另外调试时要善用 SQL 的 EXPLAIN 和日志开关。递归 CTE 里一条路径产生了几百个中间态肉眼根本看不完我会在 search 的结果里临时加一列深度计数观察递归是不是在指数膨胀一旦发现膨胀趋势就检查 MRV 是否生效或候选计算是否出现 NULL 污染。5.3 赛后复盘真正拉开差距的三件事名次出来以后我和前几名聊过发现大家都能写对递归真正的差距在三件事上。第一是否愿意先做确定性层。很多人把唯一候选空格混在递归里一块处理而我是先写了一个独立循环把能确定的全填完。这件事让后面的搜索量至少减半。第二是否用 MRV 选分支。这不是什么高深算法就是一个 ORDER BY但对难题的搜索树规模影响是数量级的。第三是否熟悉 PostgreSQL 特有的函数。bit_or聚合、LATERAL、递归 CTE 里的 CROSS JOIN这些是 PostgreSQL 身上比 MySQL 更趁手的几把工具。比赛限时内熟悉这些工具的人天然占便宜。比赛当天有一道题我印象很深盘面挖空非常多常规思路刚进入搜索就撞上候选爆炸。我当时直接先跑确定性层填完二十多个空格后剩下需要分支的不到十个递归轻轻松松就跑完了。那一刻我真切感受到算法题的胜负很多在写递归之前就已经决定了。最后再分享一个小技巧如果你也想在本地复现别直接在 9x9 上开始先把上面的bit_candidates函数写成 4x4 版本跑通然后改511为15改字符串长度和坐标公式即可。整个过程大概一小时但这一小时能帮你省掉后面排查问题的三小时。我个人现在遇到类似“集合排除”类的问题第一反应都是先想想能不能用位掩码建模。不一定是数独凡是候选集、权限集、标签集这类场景位运算在 PostgreSQL 里都能给你非常顺滑的体验。这次比赛能拿第 5运气成分有但方法论也算经得起验证。写这篇复盘希望能让更多人看到 SQL 并不只是查报表的工具它认真起来也能做正儿八经的搜索算法。
SQL也能解数独：PostgreSQL位运算与MRV递归优化实战
比赛群里的消息到现在还在刷屏一是有不少人问“SQL 也能解数独”二是问得更具体的“位运算到底是怎么个玩法”我趁记忆还热把这次用 PostgreSQL 解题的全过程整理成文。这道题表面上是数独骨子里是一个集合约束问题SQL 最擅长的就是集合而位运算则是把集合塞进一个整数里的高效手段。整篇你会看到常规 SQL 解法为什么会慢、位运算怎么把候选集变成一个 9 位二进制数、以及我为了拿名次在递归里加的几层剪枝。先说结论数独不是数学题是逻辑题用集合的视角去看每一步都是在做“排除法”。PostgreSQL 的递归 CTE、LATERAL 子查询、聚合函数 bit_or以及字符串切片能力刚好能把这套排除法完整表达出来。位运算的优势不在于“炫技”而在于它把集合运算压缩成了整数上的与、或、非在千百万次迭代里省掉的不只是代码行数而是数量级的扫描成本。1. 这题怎么会想到用位运算1.1 数独的本质是集合约束数独的规则三句话每行 1-9 不重复每列 1-9 不重复每宫3x3 小方块1-9 不重复。把这三句话翻译成数据处理语言就是每个空格的可选值等于“全集 {1..9}” 减去“同一行已出现值、同一列已出现值、同一宫已出现值”的并集。一个空格能填什么不取决于别的花哨条件只取决于三个集合。既然要频繁做“取并集、取补集、判断某个值是否在集合里”那就天然适合位运算一行、一列、一宫各用一个整数每个二进制位代表一个数字是否出现过。1 表示已出现0 表示没出现。数字 d 对应的位是 d-1也就是1 (d-1)。这个映射是我解题时最重要的一个决策。因为一旦把“集合”落成“整数”PostgreSQL 里大量现成的整数运算符和聚合函数都能直接上而不是用 EXISTS、IN、POSITION 这种逐条匹配的方式。1.2 常规 SQL 解法的三个硬伤比赛现场不少选手用的是传统思路把棋盘存成 9 行递归里逐个空格尝试 1-9每试一个数字就扫描一次当前行、列、宫有没有重复。听起来很直接但实际写起来有三个很吃亏的地方。第一冲突检查成本高。填一个空格要检查三个区域每个区域最多 9 个格子如果用字符串表达棋盘状态那每层递归都在做 81 字符的切片和 POSITION状态一深字符扫描量直线上升。第二候选集合无法复用。常规写法里同一个空格在不同递归深处会被反复重新计算候选值因为每次填完一个数字整行的状态都变了前一层算过的东西基本作废。第三分支选择傻。大多数选手按空格坐标从小到大顺序尝试1 到 9 挨个试。遇到需要回溯的题搜索树会非常胖。我后面会讲把“候选数最少的空格优先处理”这个启发式做成排序比任何事后优化都管用。1.3 位运算天然适配的三个理由位运算版方案里三个区域集合是三个整数row_mask、col_mask、box_mask。任意空格的候选掩码是511 ~(row_mask | col_mask | box_mask)。511 是(19)-1也就是二进制低 9 位全 1对应集合{1,2,...,9}。为什么说这个表达天然适配第一集合运算变成常数时间的整数运算一次 OR 合并三个区域一次 NOT 取补集一次 AND 求交集不管你之前处理过多少格子开销都一样。第二PostgreSQL 有bit_or聚合函数可以直接对一组已填数字做按位或一行 SQL 就能算出某个区域“已出现哪些数字”。第三判断一个集合里有几个候选值用pg_popcount统计二进制里的 1 就可以这个函数在 PostgreSQL 13 之后都有老版本可以用字符串替换数 0 凑合。这套模型一旦建立整个求解过程就变成一个非常干净的“状态转移”棋盘状态是多行递归产生的每个状态里嵌着若干整数掩码而不是一堆需要反复 JOIN 的关系表。2. 环境准备与关键知识点2.1 比赛环境与工具比赛用的是 PostgreSQL 15客户端连接后直接在 SQL 编辑器里写查询。我个人环境是本地 Windows 跑一个 PostgreSQL 15 实例用 DBeaver 连。比赛不允许使用外部程序也就是不能把棋盘抽出去用 Python 算完再把答案塞回来所有逻辑必须落在 SQL 里。用 PostgreSQL 有一个很重要的优势它的WITH RECURSIVE语法非常成熟能承担真正的递归搜索同时LATERAL子查询可以在递归内部做“对当前状态求候选值”这种依赖上下文的计算。加上字符串函数left、right、substring都很顺手用它做状态传递几乎不需要额外建临时表。2.2 棋盘输入与状态表达比赛给的棋盘就是一个 81 个字符的字符串0 表示空格。我第一反应是拆成行、列、值三列存进临时表但后来发现这种关系型表达在递归里很啰嗦。递归每次要传递整个棋盘状态用临时表要么每次 DELETE/INSERT要么每层递归保留一份快照读写成本都高。最终我选择把棋盘编码成字符串作为递归 CTE 的一个字段。字符在字符串里的位置 p从 1 开始对应着坐标行号(p - 1) / 9 1列号(p - 1) % 9 1宫号0 到 8(((p - 1) / 9) / 3) * 3 ((p - 1) % 9) / 3这个坐标映射是整个实现的地基不能算错。宫号公式尤其容易错我一开始写成 1-based结果候选计算全偏后来统一切成 0-based 才理顺。2.3 位掩码的三板斧正式写代码前把三个核心操作讲明白1 (v - 1)把数字 v 转成掩码。数字 5 是1 4 16二进制第 4 位为 1。bit_or(1 (v - 1))对一组已填数字求并集。这是 PostgreSQL 的聚合函数输入一堆整数掩码输出按位或的结果。511 ~m对掩码取补集并把范围限制在低 9 位。得到的是该区域还没有出现过的数字集合。数字集合和掩码之间互转是这套解法里最高频的操作我建议在草稿纸上先写三遍再动手后面所有 SQL 都基于这三个式子展开。3. 核心实操候选集计算与确定性求解3.1 一次查询算出全盘所有候选先给一个可以直接跑的核心片段。我把棋盘字符串写死方便读者本地复现。这段代码干的事是把 81 个字符拆成带坐标的格子用bit_or聚合出每行、每列、每宫的“已出现掩码”然后对每个空格求候选掩码。WITH board AS ( SELECT p, (p - 1) / 9 1 AS r, (p - 1) % 9 1 AS c, (((p - 1) / 9) / 3) * 3 ((p - 1) % 9) / 3 AS b, substring(530070000600195000098000060800060003400803001700020006060000280000419005000080079 FROM p FOR 1)::int AS v FROM generate_series(1, 81) p ), row_m AS ( SELECT r, COALESCE(bit_or(1 (v - 1)), 0)::int AS m FROM board WHERE v 0 GROUP BY r ), col_m AS ( SELECT c, COALESCE(bit_or(1 (v - 1)), 0)::int AS m FROM board WHERE v 0 GROUP BY c ), box_m AS ( SELECT b, COALESCE(bit_or(1 (v - 1)), 0)::int AS m FROM board WHERE v 0 GROUP BY b ) SELECT b.p, b.r, b.c, 511 ~(COALESCE(rm.m, 0) | COALESCE(cm.m, 0) | COALESCE(bm.m, 0)) AS cand FROM board b LEFT JOIN row_m rm ON rm.r b.r LEFT JOIN col_m cm ON cm.c b.c LEFT JOIN box_m bm ON bm.b b.b WHERE b.v 0 ORDER BY b.p;这一段是我比赛时最早就跑通的查询。重点要说的是COALESCE如果一个区域内没有任何已填数字bit_or是 NULLNULL 参与位运算会直接把结果变成 NULL进而把整个候选掩码污染成 NULL。这是最典型的坑后来我在所有聚合处都包了一层 COALESCE。你跑一下这个查询会看到每个空格的候选都是一个 0 到 511 之间的整数。比如第 1 行第 3 列行内已有 5、3列内已有 8宫内已有 5、3、6、9、8最终剩{1,2,4,7}掩码是 75二进制1001011的四个 1 位正好对应数字 1、2、4、7。这个输出可以拿来和人工推理核对我当时就是靠这种单格核对发现宫号公式写反的。3.2 唯一候选格先填确定性层拿到全盘候选以后最自然的策略不是直接开递归而是先“白捡”那些只可能填一个数字的空格。候选掩码里只有 1 个位为 1说明这个格子的值被行、列、宫三个方向夹逼得死死得很不用猜。在代码里这种情况就是pg_popcount(cand) 1。我写了一个函数每次处理一个唯一候选格返回新的棋盘字符串CREATE FUNCTION fill_once(s text) RETURNS text LANGUAGE sql AS $$ WITH board AS ( SELECT p, (p - 1) / 9 1 AS r, (p - 1) % 9 1 AS c, (((p - 1) / 9) / 3) * 3 ((p - 1) % 9) / 3 AS b, substring(s FROM p FOR 1)::int AS v FROM generate_series(1, 81) p ), cands AS ( -- 候选计算逻辑同上一节略 SELECT p, cand, 511 ~(...) AS cand1 ... ) SELECT left(s, p - 1) || d || right(s, 81 - p) FROM cands CROSS JOIN LATERAL generate_series(1, 9) d WHERE cand_count 1 AND (cand1 (1 (d - 1))) 0 LIMIT 1 $$;这个函数的意义在于把整个求解过程拆成两层外层用普通 SQL 反复调用fill_once把所有能确定的格子全部填完直到返回值不再变化说明棋盘进入“必须猜”的阶段再交给递归回溯。实际比赛里大部分题目在确定性层就能解掉一大半空格搜索树的深度和宽度都缩了一大截。很多选手一上来就递归白白把确定性步骤的迭代次数也算进搜索里慢是必然的。3.3 从掩码还原数字的两种姿势填一个空格时需要从候选掩码知道到底该填哪个数字。最省事的是generate_series(1, 9)配合(mask (1 (d - 1))) 0判断这个写法通用且直观前面已经用到。另一个姿势是把掩码转成 bit 串再数 1SELECT mask::bit(9) :: text;比如 75 转成01001011从低位到高位第 1、2、4、7 位是 1对应数字 1、2、4、7。这种写法在调试时非常舒服因为你能直观看到“哪些位还开着”。但要统计候选个数时比pg_popcount慢很多所以我只在人工核对时用 bit 串代码里全部用pg_popcount。4. 递归回溯 MRV 让搜索量骤减4.1 状态编码与递归框架确定性层跑完以后剩下的空格通常各自有 2 到 5 个候选。这时候必须做回溯选一个空格尝试填某个数字递归往下如果走不下去就回到上一层换数字。在 SQL 里我利用WITH RECURSIVE的并行特性写搜索。每一轮递归产生棋盘状态的新副本每个副本代表一条搜索路径。核心框架如下WITH RECURSIVE search(s) AS ( SELECT 530070000600195000098000060800060003400803001700020006060000280000419005000080079::text UNION ALL SELECT left(s, t.p - 1) || g.d::text || right(s, 81 - t.p) FROM search CROSS JOIN LATERAL ( SELECT p, cand, cnt FROM bit_candidates(s) WHERE cnt 0 ORDER BY cnt, p LIMIT 1 ) t CROSS JOIN LATERAL generate_series(1, 9) g(d) WHERE (t.cand (1 (g.d - 1))) 0 ) SELECT DISTINCT s FROM search WHERE position(0 IN s) 0;这里的bit_candidates(s)是前面候选计算逻辑包成的函数输入棋盘字符串输出每个空格的位置、候选掩码、候选个数。由于函数里已经用到了bit_or聚合整个回调在递归里算得上轻量。LATERAL 的妙处在于它让“选空格”这个动作和“当前的棋盘字符串 s”强绑定。每一条递归路径有各自的 s因此各有各的候选集互不干扰。这正是 SQL 处理回溯的天然姿势不手动维护调用栈而是靠递归行的多路展开。4.2 MRV 启发式先填最难的空格搜索性能的关键不在递归本身而在“选哪个空格先填”。我选了候选个数最少的空格这就是经典的 MRVMinimum Remaining Values启发式说人话就是哪个空格最没得选就先处理哪个。上面代码里ORDER BY cnt, p就是 MRV 的实现。候选越少接下来产生的分支就越少整个搜索树就越窄。我拿常规顺序按坐标从小到大和 MRV 各跑了一遍常规顺序经常在难题上跑几十秒还在原地磨蹭MRV 基本上几秒内就出结果。这个差距甚至比位运算本身还大。结合确定性层整个流程变成反复填唯一候选空格直到棋盘稳定对每个空格计算候选掩码选候选数最少的那个对该空格的每个候选数字分别递归展开递归路径上重复步骤 1这个“确定性优先 MRV 分支”的组合让我在比赛里几乎没有遇到任何一道题需要走深超过几十层的回溯。深搜最怕的是又深又宽这个组合把两边都压住了。4.3 与常规方案的真实性能对照比赛结束后我拉了一张对照表用同一台机器、同一道题跑了三种实现。数据不敢说多严谨但趋势很有代表性方案候选计算方式分支策略一道普通题的耗时感受常规字符串扫描每步用 POSITION 扫行、列、宫按坐标顺序试 1-9十几秒到几十秒关系表集合判断建临时表记录已填数EXISTS 查冲突按坐标顺序试 1-95 到 15 秒左右位运算 MRVbit_or 聚合并集整数与/非求候选唯一候选优先最少候选空格优先稳定在 1 秒内到 3 秒位运算版本不只是块头小关键是它把“算一次候选”的成本从 O(81) 的字符串扫描降到了 O(1) 的整数运算。递归成千上万次以后这个差距就是秒级和分钟级的差距。比赛环境下还有 statement_timeout常规方案最容易死在超时上。5. 比赛踩坑记录与优化清单5.1 五个自查点动手前先确认我把自己调试过程中踩过的坑整理成一份自查清单后来比赛时我每写一个版本都会先过一遍。第一bit_or对空组返回 NULL所有聚合处必须套COALESCE(..., 0)。第二数字 d 对应的掩码是1 (d - 1)不是1 d这个偏离会让所有候选集合整体错位一位而且看起来煞有介事特别难发现。第三宫号用 0-based 计算(((p - 1) / 9) / 3) * 3 ((p - 1) % 9) / 3不要混用 1-based 的除法。第四字符串索引从 1 开始但很多语言习惯是 0 开始left(s, p - 1)和right(s, 81 - p)的思路要想清楚。第五递归里如果发现某个空格候选掩码变成 0说明当前路径已经矛盾要让这条路径直接消失而不是继续填。5.2 调试技巧先在 4x4 上验证位掩码在 9x9 数独里是 9 位在 4x4 迷你数独里就是 4 位。比赛前我在本地先用 4x4 的棋盘把整个递归框架跑通因为 4x4 的棋盘小、状态少所有逻辑错误都能更早暴露出来。而且 4x4 的宫号公式、字符串拼接逻辑和 9x9 完全同构只是集合从 511 变成 15改一个数字就能跑。这个建议对所有人都适用。不要一上来直接盯着 81 字符的大字符串调试bug 藏在一堆数字里很难定位。先把模型缩小验证算法本身正确再放大到真实题目是效率最高的路径。另外调试时要善用 SQL 的 EXPLAIN 和日志开关。递归 CTE 里一条路径产生了几百个中间态肉眼根本看不完我会在 search 的结果里临时加一列深度计数观察递归是不是在指数膨胀一旦发现膨胀趋势就检查 MRV 是否生效或候选计算是否出现 NULL 污染。5.3 赛后复盘真正拉开差距的三件事名次出来以后我和前几名聊过发现大家都能写对递归真正的差距在三件事上。第一是否愿意先做确定性层。很多人把唯一候选空格混在递归里一块处理而我是先写了一个独立循环把能确定的全填完。这件事让后面的搜索量至少减半。第二是否用 MRV 选分支。这不是什么高深算法就是一个 ORDER BY但对难题的搜索树规模影响是数量级的。第三是否熟悉 PostgreSQL 特有的函数。bit_or聚合、LATERAL、递归 CTE 里的 CROSS JOIN这些是 PostgreSQL 身上比 MySQL 更趁手的几把工具。比赛限时内熟悉这些工具的人天然占便宜。比赛当天有一道题我印象很深盘面挖空非常多常规思路刚进入搜索就撞上候选爆炸。我当时直接先跑确定性层填完二十多个空格后剩下需要分支的不到十个递归轻轻松松就跑完了。那一刻我真切感受到算法题的胜负很多在写递归之前就已经决定了。最后再分享一个小技巧如果你也想在本地复现别直接在 9x9 上开始先把上面的bit_candidates函数写成 4x4 版本跑通然后改511为15改字符串长度和坐标公式即可。整个过程大概一小时但这一小时能帮你省掉后面排查问题的三小时。我个人现在遇到类似“集合排除”类的问题第一反应都是先想想能不能用位掩码建模。不一定是数独凡是候选集、权限集、标签集这类场景位运算在 PostgreSQL 里都能给你非常顺滑的体验。这次比赛能拿第 5运气成分有但方法论也算经得起验证。写这篇复盘希望能让更多人看到 SQL 并不只是查报表的工具它认真起来也能做正儿八经的搜索算法。
