2025 NineData 第三届数据库编程大赛圆满举办！本次大赛由 NineData 和云数据库技术社区主办，并联合佰晟智算、达梦数据、 ITPUB、CSDN、IFclub、开源中国、DataFun、墨天轮等技术社区共同举办。本届大赛延续 "一条 SQL" 的核心挑战，设置题目为「用一条 SQL」解数独问题。查看赛题详情

以下是本次决赛第 4 名选手马尾蛟的参赛介绍：

第4名

马尾蛟

参赛选手：马尾蛟

选手简介：就职于某大型国际物流公司，从事数据科学多年

参赛数据库：PostgreSQL

性能评测：1 万级数据代码性能评测 13.875 秒

综合得分：83.4

以下是马尾蛟选手的代码说明思路简介：

---

1. 数据库选择

• 最终选择 PG 数据库

• 算力维度：PG 的递归 CTE 引擎对复杂逻辑的计算效率更好。

• 表达维度：PG 拥有 generate_series、overlay 以及对 LATERAL JOIN 的完美支持，这让我能用更简洁、更接近算法逻辑的 SQL 表达 MRV 剪枝策略。

• 物理维度：PG 在处理 81 位以上状态压缩或高频字符串变异时，底层开销更小。

2. 步骤分析

以官方测试数据中id = 996 的数据为例 。将其展开成 9宫格如图所示

2.1 外层框架

SELECT g.id,
       g.puzzle,
       regexp_replace(solution.result, '(.{9})(?=.)', '\1' || E'\n', 'g') AS result
FROM (
  SELECT * FROM game3.sudoku9_9
) g
CROSS JOIN LATERAL (
  ... 这里面是核心解题逻辑 ...
) solution
ORDER BY g.id;

FROM (...) g：把 sudoku9_9 表里的每一道题目（每一行）拿出来，标记为g

CROSS JOIN LATERAL (...)：使用 LATERAL  对于每一道题目 g，都单独启动一次括号里的计算程序，算出结果叫 solution，然后把结果贴回题目后面。

2.2 核心逻辑

在 WITH RECURSIVE 里面，定义了一堆“临时表”（CTE），相当于解题前的准备工作。

2.2.1 常量初始化

digits AS (
  SELECT n,
         (n - 1) AS idx,
         (1::bigint << (n - 1)) AS bit,  -- 重点！
         n::text AS digit_text
  FROM generate_series(1,9) n
),

结果如下：

这里预计算了 1-9 的二进制位特征。

例如数字 1 对应二进制 000000001，数字 9 对应 100000000。

收益：后续校验时，只需做一次“按位与（&）”操作即可判断数字是否冲突，比数值比较或字符串匹配快得多。

2.2.2 坐标映射

cells AS (
  SELECT pos,
         pos/9 AS r,
         pos%9 AS c,
         ((pos/9)/3)*3 + ((pos%9)/3) AS b, -- 算宫号
         substring(clean.s FROM pos + 1 FOR 1) AS ch
  FROM clean
  CROSS JOIN generate_series(0,80) AS gs(pos)
),

结果：

将 81 个字符的字符串展开成 81 行数据，并计算好每个格子所属的 r（行）、c（列）、b（宫）坐标。这是为了初始化掩码做准备。

2.2.3 状态初始化：位掩码生成

-- 行/列/宫掩码：每 9bit 表示一行/列/宫已用数字
  row_mask AS (
    SELECT coalesce(
             bit_or(set_bit(B'0'::bit(81), (pos/9)*9 + (8 - (ch::int - 1)), 1)),
             B'0'::bit(81)
           ) AS mask
    FROM cells
    WHERE ch <> '?'
  ),
  col_mask AS (
    SELECT coalesce(
             bit_or(set_bit(B'0'::bit(81), (pos%9)*9 + (8 - (ch::int - 1)), 1)),
             B'0'::bit(81)
           ) AS mask
    FROM cells
    WHERE ch <> '?'
  ),
  box_mask AS (
    SELECT coalesce(
             bit_or(set_bit(B'0'::bit(81), ((((pos/9)/3)*3 + ((pos%9)/3))*9) + (8 - (ch::int - 1)), 1)),
             B'0'::bit(81)
           ) AS mask
    FROM cells
    WHERE ch <> '?'
  ),
  -- todo：记录所有待填位置
  todo AS (
    SELECT coalesce(array_agg(pos ORDER BY pos), ARRAY[]::int[]) AS arr
    FROM cells
    WHERE ch = '?'
  ),
  seed AS (
    SELECT clean.s,
           row_mask.mask AS row_mask,
           col_mask.mask AS col_mask,
           box_mask.mask AS box_mask,
           todo.arr AS todo
    FROM clean, row_mask, col_mask, box_mask, todo
  ),

结果：

没有用 3 个数组存状态，而是用了 3 个 81位的二进制串。

row_mask 的结构：前 9 位表示第 0 行使用了哪些数字，第 10-18 位表示第 1 行...

set_bit：将已存在的数字对应的位置为 1。

bit_or：聚合操作，将所有格子的状态合并成一个最终的掩码。

通过这 3 个二进制串，全盘的约束状态被压缩在极小的内存中，读取效率极高。

2.2.4 递归

solver AS (
    -- 初始层
    SELECT s, row_mask, col_mask, box_mask, todo
    FROM seed
    UNION ALL
    -- 递归扩展：挑选一个空格尝试填数
    SELECT overlay(c.s placing d.digit_text FROM pick.pos + 1 FOR 1) AS s,
           set_bit(c.row_mask, pick.r*9 + (8 - d.idx), 1) AS row_mask,
           set_bit(c.col_mask, pick.cidx*9 + (8 - d.idx), 1) AS col_mask,
           set_bit(c.box_mask, pick.b*9 + (8 - d.idx), 1) AS box_mask,
           array_remove(c.todo, pick.pos) AS todo
    FROM solver c
    JOIN LATERAL (
      -- MRV：挑候选数最少的格子
      SELECT pos,
             pos / 9 AS r,
             pos % 9 AS cidx,
             ((pos / 9)/3)*3 + ((pos % 9)/3) AS b,
             mask_int,
             bit_count(((~mask_int) & 511)::bit(9)) AS free,
             ord
      FROM (
        SELECT pos,
               ord,
               pos / 9 AS r,
               pos % 9 AS cidx,
               ((pos / 9)/3)*3 + ((pos % 9)/3) AS b,
               (
                 (substring(c.row_mask from (pos/9)*9 + 1 for 9)::bit(9)::int) |
                 (substring(c.col_mask from (pos%9)*9 + 1 for 9)::bit(9)::int) |
                 (substring(c.box_mask from ((((pos/9)/3)*3 + ((pos%9)/3))*9) + 1 for 9)::bit(9)::int)
               ) AS mask_int
        FROM unnest(c.todo) WITH ORDINALITY AS todo(pos, ord)
      ) base
      ORDER BY free, ord
      LIMIT 1
    ) pick ON true
    JOIN digits d ON (pick.mask_int & d.bit) = 0
  )

 join lateral 内部结果

取出约束：对于每一个空格，从 row_mask、col_mask、box_mask 中截取对应的 9 位。

合并约束：使用 位或（|） 运算。比如行里有1，列里有2，宫里有3，运算结果就是 ...00111，表示 1,2,3 都不能填。（图中mask_int = 509 ，他对应的二进制为 111111101 ）

计算自由度：bit_count 计算有多少个位是 0（合法的候选数）。

排序 (ORDER BY free)：这是关键点， 不按顺序填，而是永远挑那个“自由度最小”的格子填。

如果一个格子只剩 1 个能填的数（自由度=1），立刻填它。

如果自由度不是1，比如一个格子，它有两个合法的候选数：1 和 4，此时 JOIN digits 会匹配成功两次，然后两个数据同时进入到下一轮递归。直到后面某一轮 有一个分支，他的自由度为0，JOIN digits 找不到匹配的数字，这条数据没能生成下一代，直接“断子绝孙”，从内存中消失。

2.2.5 收尾

SELECT s AS result
FROM solver
WHERE coalesce(array_length(todo, 1), 0) = 0
LIMIT 1

递归会产生很多中间状态，我只要那个 todo 数组长度为 0 的（也就是全填完了的）那一行。

LIMIT 1：如果有多解，我只要第一个。

3. 总结

快在“不用眼睛看”，而用“开关查”：没有用程序去一个个对比数字（1等于1吗？），而是把数字变成了二进制开关。检查冲突只需要一次CPU的“且运算”，这比比对字符快了几十倍。

快在“先做必做题”：普通程序是从第1格试到第81格。我的程序每一步都会看全盘，发现哪个格子“只剩一个能填的数”，就立刻先填它。这避免了瞎猜导致的走弯路（回溯）。

自动剪枝：如果其中一条路是错的（比如填了 1），后续一定会遇到‘无路可走’的格子，那条数据流就会因为 JOIN 不到候选数而自然终止。

其他尝试

• • 因为注意到一开始 主办方提供的机器为4C32G ，希望能够充分利用机器资源，但是各种尝试都不行。pg 的 cte 无法多线程。

  • 注意到，其实编译占了大部分时间，如果允许关闭编译 即 set jit= off ，那么 时间可以从1.2秒左右，优化到0.6 秒左右。

---

参赛完整SQL：

SELECT g.id,
       g.puzzle,
       -- 将 81 位结果每 9 位插入换行，便于人工核对
       regexp_replace(solution.result, '(.{9})(?=.)', '\1' || E'\n', 'g') AS result
FROM (
  SELECT *
  FROM game3.sudoku9_9
) g
CROSS JOIN LATERAL (
  WITH RECURSIVE
  -- digits：缓存 1~9 及其位掩码
  digits AS (
    SELECT n,
           (n - 1) AS idx,
           (1::bigint << (n - 1)) AS bit,
           n::text AS digit_text
    FROM generate_series(1,9) n
  ),
  -- clean：去掉 puzzle 中的空白/换行
  clean AS (
    SELECT translate(g.puzzle, E'\r\n\t ', '') AS s
  ),
  -- cells：展开 81 个格子并标注行/列/宫
  cells AS (
    SELECT pos,
           pos/9 AS r,
           pos%9 AS c,
           ((pos/9)/3)*3 + ((pos%9)/3) AS b,
           substring(clean.s FROM pos + 1 FOR 1) AS ch
    FROM clean
    CROSS JOIN generate_series(0,80) AS gs(pos)
  ),
  -- 行/列/宫掩码：每 9bit 表示一行/列/宫已用数字
  row_mask AS (
    SELECT coalesce(
             bit_or(set_bit(B'0'::bit(81), (pos/9)*9 + (8 - (ch::int - 1)), 1)),
             B'0'::bit(81)
           ) AS mask
    FROM cells
    WHERE ch <> '?'
  ),
  col_mask AS (
    SELECT coalesce(
             bit_or(set_bit(B'0'::bit(81), (pos%9)*9 + (8 - (ch::int - 1)), 1)),
             B'0'::bit(81)
           ) AS mask
    FROM cells
    WHERE ch <> '?'
  ),
  box_mask AS (
    SELECT coalesce(
             bit_or(set_bit(B'0'::bit(81), ((((pos/9)/3)*3 + ((pos%9)/3))*9) + (8 - (ch::int - 1)), 1)),
             B'0'::bit(81)
           ) AS mask
    FROM cells
    WHERE ch <> '?'
  ),
  -- todo：记录所有待填位置
  todo AS (
    SELECT coalesce(array_agg(pos ORDER BY pos), ARRAY[]::int[]) AS arr
    FROM cells
    WHERE ch = '?'
  ),
  seed AS (
    SELECT clean.s,
           row_mask.mask AS row_mask,
           col_mask.mask AS col_mask,
           box_mask.mask AS box_mask,
           todo.arr AS todo
    FROM clean, row_mask, col_mask, box_mask, todo
  ),
  solver AS (
    -- 初始层
    SELECT s, row_mask, col_mask, box_mask, todo
    FROM seed
    UNION ALL
    -- 递归扩展：挑选一个空格尝试填数
    SELECT overlay(c.s placing d.digit_text FROM pick.pos + 1 FOR 1) AS s,
           set_bit(c.row_mask, pick.r*9 + (8 - d.idx), 1) AS row_mask,
           set_bit(c.col_mask, pick.cidx*9 + (8 - d.idx), 1) AS col_mask,
           set_bit(c.box_mask, pick.b*9 + (8 - d.idx), 1) AS box_mask,
           array_remove(c.todo, pick.pos) AS todo
    FROM solver c
    JOIN LATERAL (
      -- MRV：挑候选数最少的格子
      SELECT pos,
             pos / 9 AS r,
             pos % 9 AS cidx,
             ((pos / 9)/3)*3 + ((pos % 9)/3) AS b,
             mask_int,
             bit_count(((~mask_int) & 511)::bit(9)) AS free,
             ord
      FROM (
        SELECT pos,
               ord,
               pos / 9 AS r,
               pos % 9 AS cidx,
               ((pos / 9)/3)*3 + ((pos % 9)/3) AS b,
               (
                 (substring(c.row_mask from (pos/9)*9 + 1 for 9)::bit(9)::int) |
                 (substring(c.col_mask from (pos%9)*9 + 1 for 9)::bit(9)::int) |
                 (substring(c.box_mask from ((((pos/9)/3)*3 + ((pos%9)/3))*9) + 1 for 9)::bit(9)::int)
               ) AS mask_int
        FROM unnest(c.todo) WITH ORDINALITY AS todo(pos, ord)
      ) base
      ORDER BY free, ord
      LIMIT 1
    ) pick ON true
    JOIN digits d ON (pick.mask_int & d.bit) = 0
  )
  SELECT s AS result
  FROM solver
  WHERE coalesce(array_length(todo, 1), 0) = 0
  LIMIT 1
) solution
ORDER BY g.id;

《数据库编程大赛》

下一次再聚！

感谢大家对本次《数据库编程大赛》的关注和支持，欢迎加入技术交流群，更多精彩活动不断，欢迎各路数据库爱好者来挑战！