Optimi-Zi(n)g Sudoku-Solving
10 months ago
- #Zig
- #Sudoku-Solver
- #DLX-Algorithm
- Dancing-Links（DLX）算法通过稀疏矩阵建模约束条件和解，用于解决精确覆盖问题，例如数独。
- 数独被转化为精确覆盖问题，包含4类约束：行、列、3x3宫格及单元格约束，共4*9*9列。
- DLX算法流程包括：构建矩阵、预填充已知行、递归求解约束直至全部满足或失败。
- Zig语言实现的优化措施包括：减少内存分配、使用栈内存替代堆内存、启用编译器优化（`-Doptimize=ReleaseFast`）。
- 通过预分配内存、跳过冗余行设置、利用Hotspot分析性能热点，显著提升运行效率。
- 最终优化版本平均每题耗时0.061毫秒，未来可通过多线程实现进一步加速。
- 该项目验证了DLX算法在数独求解中的高效性，并暗示其对N皇后等问题的适配潜力。