arXiv cs.AI· Arman Eisenkolb-Vaithyanathan·· 3 天前AI 评分12
如何统一刻画数独谜题难度：基于 SAT 与人类解题策略的通用评级系统
Toward a Universal Characterization of Sudoku Puzzle Difficulty
AI 导读
研究者提出两个数独难度指标：一是将谜题转为 SAT 问题后由子句长度分布刻画结构复杂度，二是用随机化 Nishio 回溯算法模拟人类解题并统计四种策略的调用次数。
正文 · AI 翻译
摘要：在本文中，我们试图回答“不同数独网站上的数独难度评级由什么构成？”这一问题。使用两种都能求解每一个数独谜题的截然不同的方法，我提出了两个新的指标来刻画数独难度。第一种方法基于将数独谜题转换为相应的可满足性（SAT）问题。第一个提出的指标源自 SAT 子句长度分布，它捕捉了数独谜题的结构复杂性，包括给定数字的数量及其所在的单元格。第二种方法通过在名为 Nishio 的回溯算法中交织四种流行的数独策略来模拟人类数独解题者。第二个指标通过统计在随机化 Nishio 的回溯迭代中应用数独策略的次数来计算。使用这两个指标，我分析了来自五个热门网站的一千多个数独谜题，以刻画每个网站中的每一个难度级别。我使用 Spearman 秩相关系数评估所提出的指标与网站标注难度级别之间的关系，发现 5 个网站中有 4 个存在强相关性。我使用基于这两个所提出指标的简单无监督分类器构建了一个通用评级系统。该评级系统能够将来自不同数独网站的单个谜题和整个难度级别分类为三个类别——通用简单、通用中等和通用困难——从而实现数独网站之间一致的难度映射。实验结果表明，对于 5 个数独网站中的 4 个，通用分类与网站标注的难度级别吻合良好。最后，我提出了一种可供早期数独练习者用来求解数独谜题的算法。
| 评论： | 25 页，9 幅图 |
| 主题： | 人工智能（cs.AI） |
| ACM 分类： | I.2.8 |
| 引用为： | arXiv:2507.21137 [cs.AI] |
| （或 arXiv:2507.21137v2 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2507.21137 arXiv 颁发的 DOI，经由 DataCite |
提交历史
来自：Arman Eisenkolb-Vaithyanathan [查看电子邮件]
[v1]
2025 年 7 月 22 日星期二 22:32:30 UTC（625 KB）
[v2]
2026 年 10 月 11 日星期日 23:29:34 UTC（752 KB）
来源：arXiv cs.AI · arxiv.org