sudoku-dlx

一个用 C17 实现的数独求解器，核心算法是 Dancing Links / Algorithm X（DLX）。求解器可复用，支持 n^2 x n^2 方形宫数独；main.c 同时提供命令行工具和内置测试套件。

数独被转换成精确覆盖问题。设宫边长为 n，棋盘边长为 S = n * n：

因此矩阵共有 4 * S^2 个约束列。一个候选选择表示“格子 (r, c) 填数字 d”，它恰好覆盖 4 个约束列。空格会产生 S 个候选行；已有数字只保留对应数字的一个候选行，这样给定数字天然不会被改写。

搜索时使用 DLX 的四向十字链表做 cover / uncover，并按 MRV（Minimum Remaining Values）选择当前剩余候选最少的约束列。某列剩余候选为 0 立即回溯，为 1 时直接传播。所有候选节点来自预分配的静态数组，运行中不做动态内存分配。

make

默认 DLX_MAX_N=3，最大支持 9 x 9；同时也允许 4 x 4。若要支持 16 x 16 或 25 x 25，编译时调整宏：

make clean
make CFLAGS='-std=c17 -Wall -Wextra -pedantic -O2 -DDLX_MAX_N=5'

同一程序或库的所有翻译单元必须使用相同的 DLX_MAX_N。静态内存随该宏快速增长：

上面的规模包含节点池；总静态状态还会额外包含列计数和解栈数组，但数量级相同。

无参数运行完整测试：

./sudoku

求解单个题目：

./sudoku 530070000600195000098000060800060003400803001700020006060000280000419005000080079

从标准输入读取：

echo '530070000 600195000 098000060 ...' | ./sudoku -

题目串规则：

• 空白字符会被忽略。
• 0 或 . 表示空格。
• 1 到 9 表示数字 1 到 9。
• A 到 Z 或 a 到 z 表示 10 到 35。
• 符号总数决定棋盘规格：16 表示 4 x 4，81 表示 9 x 9，256 表示 16 x 16，625 表示 25 x 25。
• 默认构建只识别 16 和 81；更高的规格需要按上文调大 DLX_MAX_N。

退出码：

#include "sudoku_dlx.h"

uint8_t board[9][9] = { 0 };
board[0][0] = 5;

SolveStatus st = solve_sudoku(board, SUDOKU_DEFAULT_TIMEOUT_MS);
if (st == SOLVE_OK) {
    /* board 已被原地改写成完整解 */
}

通用接口接受行主序的一维棋盘：

uint8_t board[4 * 4] = { 0 };
SolveStatus st = solve_sudoku_n(board, 2, 1000);

n 是宫边长：2 表示 4 x 4，3 表示 9 x 9，依次类推。棋盘中的 0 表示空格，其余合法值为 1 到 n * n。

返回状态：

非 SOLVE_OK 状态下，输入棋盘保持原样。solve_last_search_nodes() 返回上一次搜索消耗的节点数，适合诊断和测试。

• timeout_ms 控制墙钟时间，使用 C11 timespec_get(TIME_UTC)。
• 0 或负值表示不启用墙钟限制。
• 默认墙钟上限是 SUDOKU_DEFAULT_TIMEOUT_MS，即 2000 毫秒。
• 搜索每 1024 个节点检查一次时间，摊薄系统时钟调用成本。
• DLX_MAX_SEARCH_NODES 是编译期节点预算，默认 5,000,000，可用 -D 覆盖。
• 墙钟或节点预算任一触达都会返回 SOLVE_TIMEOUT。
• 如果平台时钟不可用，求解器自动退化为只受节点预算限制。

实现使用全局静态状态：单线程使用安全，不可重入，也不能在多个线程中同时调用求解器。

运行完整测试和基准：

make test

内置覆盖包括：

• 经典 9 x 9 题目。
• 17 提示数题目。
• AI Escargot、Inkala 2012 等高难度题目。
• 高回溯构造题、空棋盘。
• 无解、行冲突、宫冲突、数值越界、空指针。
• 通用棋盘接口，默认构建覆盖 4 x 4。
• 编译期降低节点预算后的 TIMEOUT 路径。

调试内存和未定义行为可用：

make debug

本机参考结果（2026-09-13，macOS，默认构建，非性能承诺）：

求解器可编译为 WebAssembly，并附带一个单页面前端：

make wasm            # 需要 wasm32 目标的 clang 和 wasm-ld（macOS 可 brew install lld）
make web             # 生成 web/index.html，内嵌 base64 wasm 的单文件页面
make pages           # 把成品页同步到 docs/，供 GitHub Pages 部署
node web/smoke.mjs   # wasm 冒烟测试：求解、空盘、无解、非法局面

• web/index.html 是构建产物：内嵌 base64 wasm 的零依赖单文件页面，浏览器直接打开即可；源模板是 web/template.html（直接打开模板会提示先运行 make web）。开发时也可用 python3 -m http.server 提供页面。
• wasm 模块约 4 KB，以 -DDLX_NO_LIBC 编译：无 libc 依赖，时钟不可用，超时自动退化为只受节点预算限制。
• 导出接口见 wasm_shim.c：JS 直接读写线性内存中的 81 字节棋盘缓冲，调用 solve_current(timeout_ms)，读取状态码与搜索节点数。

前端固定为标准 9 x 9，交互方式：

• 单击选中格子，数字键盘 1-9 填入；双击或长按（约 0.5 秒，触摸屏）清除自填内容；键盘 1-9 与退格、删除键同样有效。双击采用自建检测而非 dblclick 事件，iOS Safari 上同样有效。
• 「提示」开关（说明行右侧）：开启后选中格子时，数字键盘自动禁用与该格行/列/宫冲突的数字，键盘输入同样被拦截；关闭后恢复。
• 黑色数字为题目格，不可选也不可修改；求解补出的数字以另一颜色显示，状态行给出耗时与节点数。
• 「重来」清除全部自填与求解格、回到题目初始状态；其下拉菜单中的「清空整局」还原空盘。
• 生成按钮随机产出一个局面：从基底解做保真变换（数字重排、行/列/宫带置换）后随机抠空到 30~36 个提示数，保证有解，不保证唯一解。
• 下拉可载入五道内置题目：经典题目、17 提示数、AI Escargot、Inkala 2012、高回溯构造。
• 工具行「…」按钮为下拉复合：主按钮打开系统文件对话框，菜单「直接粘贴」弹出模态框（带行号）粘贴文本；二者都接受 81 个 0-9 或 . 符号的局面文本（忽略空白与换行），格式不符时提示实际识别到的符号数。载入后下拉框显示文件名或「粘贴的局面」，超长时前段自动缩略成 …，选择内置题目即恢复。

仓库根的 docs/ 目录就是站点(make pages 从 web/index.html 同步而来, 含 .nojekyll),部署只需推送后在仓库设置中选择:

Settings → Pages → Source: Deploy from a branch → Branch: main,Folder: /docs

线上页面地址:https://ca1e.github.io/sudoku-dlx/

页面内容改动后重新 make pages 并提交 docs/ 即可发布,无需任何 CI。

若只把求解器嵌入其他 C/C++ 项目，建议只编译并链接 sudoku_dlx.c，不要把 main.c 带进库。调用前让用户提供原棋盘副本，可以避免成功求解时覆盖原始题目。由于实现使用静态池，嵌入式场景应先按目标最大棋盘设置 DLX_MAX_N，再确认静态内存预算。

• tholman/github-corners(MIT):页面右上角的 GitHub 角标直接采用该项目的官方代码,仅替换了跳转地址。
• Knuth, Donald E. Dancing Links (2000):DLX / Algorithm X 的原始论文,本项目核心算法来源。