数独求解（Dancing Links）
把数独变成精确覆盖问题，Rust + WebAssembly 用舞蹈链求解，并和朴素回溯比较搜索量
选一道题点「求解」，或点格子后用键盘 / 数字面板自己出题 | 「反暴力」那道题：舞蹈链几十步解完，朴素回溯要试几千万次
📖 原理说明
数独的规则可以换个角度看：一共有 324 条「必须恰好满足一次」的约束——81 个格子每格恰好填一个数、每行每个数字恰好出现一次、每列、每宫也一样；而在某格填某数（共 729 种选择）会同时满足其中 4 条。解数独就是挑出一组选择，让每条约束恰好被满足一次，这叫精确覆盖问题。Knuth 的 X 算法配合「舞蹈链」数据结构，是解这类问题的经典方法。
🧮算法原理
选择 (行 r, 列 c, 数字 d) → 满足 {格(r,c)，行 r 有 d，列 c 有 d，宫 b 有 d}729 行 × 324 列的 0/1 矩阵，每行恰好 4 个 1
- X 算法
- 每一步挑出剩余选项最少的那条约束（比如某格只剩一个候选数，或某行的某个数字只剩一个位置），依次尝试满足它的每个选择：选中后，把与它冲突的选择全部划掉，然后递归；走不通就恢复现场换下一个。「先处理最受限的约束」让搜索几乎不走弯路，人工解数独时的「唯一候选数」「唯一位置」两种技巧都自然包含在里面。
- 舞蹈链
- 矩阵用十字交叉的循环双向链表存储，只保存 1 的位置。删除一个节点只需让左右邻居互相指向（L[R[x]] = L[x]，R[L[x]] = R[x]），而节点自己仍记得原来的邻居，回溯时一句 L[R[x]] = R[L[x]] = x 就能原样放回。删除和恢复都是 O(1)，回溯时链表节点像在「跳舞」，因此得名。
- 朴素回溯
- 按从左到右、从上到下的顺序逐格尝试 1~9，与行、列、宫冲突就换下一个，全都不行就退回上一格。它不会优先处理最受限的格子，一旦前面的格子选错，要到很久以后才发现。「反暴力」那道题专门针对这一点：第一行的正确答案是 987654321，朴素回溯每一格都要从 1 试到最后，要搜索约 7000 万个节点。
- 唯一性检查
- 找到第一个解之后继续搜索，找到第二个解就停下，这样就知道题目是唯一解、多解还是无解。动画演示只播放找到第一个解之前的过程：蓝色数字是正在尝试的格子，数字消失就是回溯。
🔄Rust 与 JavaScript 的分工
- JS点「求解」时 JS 把 81 个数字传给
sudoku_solve(题目, 算法, 节点上限)；「动画演示」调用 sudoku_trace 取回搜索过程中每一步的填入与撤销。
- RustRust 检查已知数字有没有冲突，然后建立 729 × 324 的舞蹈链（或朴素回溯的行、列、宫位掩码），搜索并统计节点数，返回结果、节点数和解。
- JSJS 显示答案，或按速度回放搜索过程；「两种算法对比」把两种算法的节点数和耗时列成表。
⚡性能要点
- 实测（桌面 Chromium）：各道题舞蹈链都在 45~2700 个节点、2ms 以内解完。朴素回溯在简单题上也很快（入门题约 4600 个节点），但 Arto Inkala 2012「世界最难」要约 207 万个节点，「反暴力」题要约 6900 万个节点、将近 1 秒，是舞蹈链的一百多万倍。
- 所谓「最难」是针对人工解法说的：这些题需要高级推理技巧，对舞蹈链来说只是多试了几千步。朴素回溯的耗时主要取决于前几行的答案在 1~9 中排得多靠后。
- 朴素回溯的搜索上限是 2 亿个节点，超过就停下并报告「超出搜索上限」，以免长时间卡住页面。
源码crates/algorithms/sudoku/src/dlx.rscrates/algorithms/sudoku/src/naive.rswww/sudoku/index.js