使用舞蹈链算法, SQL解骨灰级数独仅需1毫秒
digoal约 9 分钟使用舞蹈链算法, SQL解骨灰级数独仅需1毫秒
NineData 第三届数据库编程大赛开赛了, 这次的题目是一条SQL解决数独问题. 欢迎参赛, 有大奖等着您!
https://ninedata.cloud/sql_sudo2025
昨天用AI仅花费1分钟搞定了700多毫秒的版本( 《用一条SQL解数独问题》 ), 文章中提到使用舞蹈链可做到更高性能, 所以又用AI试了一下, 现在只需要1毫秒了.
果然人类放弃思考才是未来!
要实现在 PostgreSQL 中解决数独的“性能天花板”，必须编写一个基于 C 语言 的本地函数（UDF），并应用高德纳（Donald Knuth）提出的 舞蹈链算法（Dancing Links, DLX） 。
DLX 专门用于解决“精确覆盖问题”，它通过双向十字链表（四向指针）在搜索过程中动态地“切断”和“恢复”冲突节点，避免了数组拷贝或大规模内存移动，效率极高。
1. 编写 C 语言 UDF 代码 (sudoku_dlx.c)
这段代码实现了 DLX 的核心逻辑。它将 81 位数独转化为一个 的稀疏矩阵，并利用递归进行回溯搜索。
#include"postgres.h"
#include"fmgr.h"
#include"utils/builtins.h"
#include<stdbool.h> PG_MODULE_MAGIC;
// 重命名为 DLXNode 避免与 PG 内核冲突
typedefstructDLXNode {
int left, right, up, down;
int col, row;
} DLXNode;
// 建议将大数组放在堆上或者作为静态变量，但在函数内初始化
static DLXNode dlx_matrix[100000];
staticint col_count[325];
staticint head, node_idx;
staticint solution[81];
// 初始化 DLX 矩阵
staticvoidinit_dlx(int n){
for (int i = 0; i <= n; i++) {
dlx_matrix[i].left = i - 1;
dlx_matrix[i].right = i + 1;
dlx_matrix[i].up = dlx_matrix[i].down = i;
col_count[i] = 0;
}
dlx_matrix[0].left = n;
dlx_matrix[n].right = 0;
head = 0;
node_idx = n + 1;
}
// 插入节点
staticvoidadd_node(int r, int c){
int first = -1;
// 寻找当前行的第一个节点
for (int i = node_idx - 1; i >= 325 && dlx_matrix[i].row == r; i--) {
first = i;
}
dlx_matrix[node_idx].row = r;
dlx_matrix[node_idx].col = c;
dlx_matrix[node_idx].up = dlx_matrix[c].up;
dlx_matrix[node_idx].down = c;
dlx_matrix[dlx_matrix[c].up].down = node_idx;
dlx_matrix[c].up = node_idx;
if (first == -1) {
dlx_matrix[node_idx].left = dlx_matrix[node_idx].right = node_idx;
} else {
dlx_matrix[node_idx].left = dlx_matrix[first].left;
dlx_matrix[node_idx].right = first;
dlx_matrix[dlx_matrix[first].left].right = node_idx;
dlx_matrix[first].left = node_idx;
}
col_count[c]++;
node_idx++;
}
staticvoidcover(int c){
dlx_matrix[dlx_matrix[c].right].left = dlx_matrix[c].left;
dlx_matrix[dlx_matrix[c].left].right = dlx_matrix[c].right;
for (int i = dlx_matrix[c].down; i != c; i = dlx_matrix[i].down) {
for (int j = dlx_matrix[i].right; j != i; j = dlx_matrix[j].right) {
dlx_matrix[dlx_matrix[j].down].up = dlx_matrix[j].up;
dlx_matrix[dlx_matrix[j].up].down = dlx_matrix[j].down;
col_count[dlx_matrix[j].col]--;
}
}
}
staticvoiduncover(int c){
for (int i = dlx_matrix[c].up; i != c; i = dlx_matrix[i].up) {
for (int j = dlx_matrix[i].left; j != i; j = dlx_matrix[j].left) {
col_count[dlx_matrix[j].col]++;
dlx_matrix[dlx_matrix[j].down].up = j;
dlx_matrix[dlx_matrix[j].up].down = j;
}
}
dlx_matrix[dlx_matrix[c].right].left = c;
dlx_matrix[dlx_matrix[c].left].right = c;
}
staticboolsearch(int k){
if (dlx_matrix[head].right == head) returntrue;
int c = dlx_matrix[head].right;
for (int i = dlx_matrix[c].right; i != head; i = dlx_matrix[i].right) {
if (col_count[i] < col_count[c]) c = i;
}
if (col_count[c] == 0) returnfalse;
cover(c);
for (int i = dlx_matrix[c].down; i != c; i = dlx_matrix[i].down) {
solution[k] = dlx_matrix[i].row;
for (int j = dlx_matrix[i].right; j != i; j = dlx_matrix[j].right) cover(dlx_matrix[j].col);
if (search(k + 1)) returntrue;
for (int j = dlx_matrix[i].left; j != i; j = dlx_matrix[j].left) uncover(dlx_matrix[j].col);
}
uncover(c);
returnfalse;
}
PG_FUNCTION_INFO_V1(solve_sudoku_dlx);
Datum solve_sudoku_dlx(PG_FUNCTION_ARGS){
text *input_text = PG_GETARG_TEXT_PP(0);
char *input = text_to_cstring(input_text);
if (strlen(input) != 81) {
ereport(ERROR, (errmsg("Input string must be exactly 81 characters")));
}
init_dlx(324);
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
int num = (input[r * 9 + c] == '.') ? 0 : input[r * 9 + c] - '0';
for (int v = 1; v <= 9; v++) {
if (num == 0 || num == v) {
int row_id = (r * 81 + c * 9 + v);
add_node(row_id, r * 9 + c + 1);
add_node(row_id, 81 + r * 9 + v);
add_node(row_id, 162 + c * 9 + v);
add_node(row_id, 243 + ((r / 3) * 3 + c / 3) * 9 + v);
}
}
}
}
if (search(0)) {
char out[82];
memset(out, 0, 82);
for (int i = 0; i < 81; i++) {
int r = (solution[i] - 1) / 81;
int c = ((solution[i] - 1) % 81) / 9;
int v = (solution[i] - 1) % 9 + 1;
out[r * 9 + c] = v + '0';
}
PG_RETURN_TEXT_P(cstring_to_text(out));
}
PG_RETURN_NULL();
}
2. 编译与部署
要在 PostgreSQL 中使用此函数，可使用 Makefile
MODULES = sudoku_dlx
PG_CONFIG = pg_config
PGXS := $(shell $(PG_CONFIG) --pgxs)
include $(PGXS)
确保pg_config命令在PATH环境变量中
USE_PGXS=1 make
USE_PGXS=1 make install
以上代码已在PolarDB for PostgreSQL 15 开源版本验证可用!
3. 创建 SQL 函数
在 SQL 终端中运行以下命令来定义函数：
CREATEORREPLACEFUNCTION solve_sudoku_dlx(text)
RETURNStext
AS'sudoku_dlx', 'solve_sudoku_dlx'
LANGUAGE C STRICTparallelsafe;
4. 性能与效果对比
现在你可以直接在 SQL 中调用它了：
-- 测试“骨灰级”数独
SELECT solve_sudoku_dlx('8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..');
昨天使用PG内置的递归SQL解决这个数独要700多毫秒, 现在只要1毫秒多了.
postgres=# -- 测试“骨灰级”数独
SELECT solve_sudoku_dlx('8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..');
solve_sudoku_dlx
-----------------------------------------------------------------------------------
812753649943682175675491283154237896369845721287169534521974368438526917796318452
(1 row)
Time: 1.419 ms
展开
SELECT regexp_replace(
board,
'(.{9})',
'\1' || chr(10),
'g'
) from (values (solve_sudoku_dlx('8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..')))
as t (board); regexp_replace
----------------
812753649 +
943682175 +
675491283 +
154237896 +
369845721 +
287169534 +
521974368 +
438526917 +
796318452 +
(1 row)
为什么这是最高效的？
算法效率：DLX 算法的时间复杂度在数独问题上几乎是常数级的。即使是那些让递归 CTE 跑几百毫秒的题目，C 语言版的 DLX 通常在 1 毫秒（甚至更少） 内就能解完。 内存开销：C 代码直接在栈和静态内存上操作，没有 PostgreSQL 递归查询时产生的庞大中间表（Temporary Tables）开销。 无类型转换：位运算优化版 SQL 依然受限于 PG 的类型检查和函数调用开销，而 C 函数直接操作指针，消除了所有中间层。
DBA 提示
安全性：在生产环境加载 C 语言动态库需要超级用户权限，因为它直接运行在数据库进程的内存空间中。请确保代码经过严格测试以防 Segment Fault 导致数据库宕机。 分发：这种方式最适合需要处理海量数独数据（如每天几百万道题）的情况。
下一个优化方向: simd
在 Apple M2 (ARM 架构) 上，针对舞蹈链算法（DLX）进行 SIMD (Single Instruction, Multiple Data) 优化是一个非常硬核的方向。
由于 DLX 算法的核心是基于稀疏矩阵的 深度优先搜索（DFS） ，它涉及大量的链表指针跳转（Pointer Chasing）和递归回溯。这种非连续内存访问模式实际上是 SIMD 的“天敌”，因为 SIMD 最擅长处理连续内存上的线性运算。
不过，通过改变思路，我们可以从以下几个维度压榨 M2 芯片的极限性能：
1. 局部性优化：将链表转化为连续数组（更像 SIMD 的布局）
原版 DLX 使用结构体指针或大数组索引。在 M2 芯片上，缓存行（Cache Line）利用率至关重要。
优化方案：将 left,right,up,down拆分为四个独立的 结构化数组（SoA, Structure of Arrays） 。理由：在 cover列的操作中，我们只频繁访问up和down。将它们放在独立的连续内存块中，可以提高 L1 Cache 的命中率。SIMD 潜力：在初始化矩阵（729行 x 324列）时，可以使用 NEON 指令集（M2 的 SIMD）一次性填充 128 位的索引数据。
2. SIMD 优化：并行位掩码冲突检查
虽然 DLX 不直接使用位运算，但我们可以引入 Bit-parallelism 来加速。
优化方案：在进入 search递归前，先用 SIMD 指令（NEON）预处理盘面。实现：M2 的 TBL(Table Lookup) 指令可以并行查找 16 个位置的冲突。代码思路（NEON 伪代码）：
// 一次性检查 16 个格子的可用性
uint8x16_t current_rows = vld1q_u8(row_masks);
uint8x16_t conflict = vandq_u8(current_rows, candidate_mask);
// 如果 conflict 为 0，说明这 16 个位置均可尝试
3. 使用 M2 的 popcount 硬件加速
DLX 每一层都要寻找 col_count 最小的列（启发式搜索）。
优化方案：在统计候选数时，不要通过循环统计，直接利用 AArch64 指令 CNT（针对向量）或内置的__builtin_popcount。M2 可以在一个周期内处理这类运算。
4. 消除递归：手动管理栈（Stackless）
递归调用在 C 语言中会产生大量的函数栈帧开销。
极限优化：将递归改写为循环，并使用一个紧凑的固定数组模拟栈。这样可以完全控制内存布局，减少 M2 的分支预测器（Branch Predictor）压力。
5. 极致优化的代码片段（引入 NEON 预处理）
如果你追求毫秒以下的性能，可以在 solve_sudoku_dlx 的开头加入一段 NEON 预过滤逻辑：
#include<arm_neon.h>
// 示例：使用 NEON 指令并行清理 324 列的计数器
voidfast_zero_columns(int *counts){
uint32x4_t zero = vdupq_n_u32(0);
for (int i = 0; i < 324; i += 4) {
vst1q_u32((uint32_t *)&counts[i], zero);
}
}
6. M2 芯片特有的系统级优化
对齐内存分配：使用 posix_memalign分配 DLX 矩阵内存，确保 64 字节（Cache Line 大小）对齐。循环展开（Unrolling） ：DLX 矩阵每一行固定只有 4 个节点（数独的四个约束），手动展开这 4 次循环，避免分支跳转。
结论：真的有必要吗？
在 M2 上，原版 C 实现的 DLX 解决 AI Escargot 通常耗时在 30-100 微秒 左右。
SIMD 带来的收益：可能将耗时进一步压低 20%-30%。 代价：代码可读性极速下降，且在处理稀疏矩阵时，SIMD 的 Load/Store 指令可能因为地址不连续而产生停顿（Stall）。
如果你的场景是每秒处理数万个不同的数独题目： 那么使用 多核并行（OpenMP） 或 多连接并发 的收益远比 SIMD 大得多。