arXiv：cs.AI· Arman Eisenkolb-Vaithyanathan·· 5 小时前
如何统一刻画数独谜题难度：跨数独网站难度的通用评级方法
Toward a Universal Characterization of Sudoku Puzzle Difficulty
AI 导读
研究提出两个新指标来刻画数独难度：一是基于 SAT 子句长度分布，捕捉给定数字数量及其位置的结构复杂度；二是模拟人类解题，统计四种数独策略在随机化 Nishio 回溯中的调用次数。
正文
Abstract:In this paper we try to answer the question "What constitutes Sudoku difficulty rating across different Sudoku websites?" Using two distinct methods that can both solve every Sudoku puzzle, I propose two new metrics to characterize Sudoku difficulty. The first method is based on converting a Sudoku puzzle into its corresponding Satisfiability (SAT) problem. The first proposed metric is derived from SAT Clause Length Distribution which captures the structural complexity of a Sudoku puzzle including the number of given digits and the cells they are in. The second method simulates human Sudoku solvers by intertwining four popular Sudoku strategies within a backtracking algorithm called Nishio. The second metric is computed by counting the number of times Sudoku strategies are applied within the backtracking iterations of a randomized Nishio. Using these two metrics, I analyze more than a thousand Sudoku puzzles across five popular websites to characterize every difficulty level in each website. I evaluate the relationship between the proposed metrics and website-labeled difficulty levels using Spearman's rank correlation coefficient, finding strong correlations for 4 out of 5 websites. I construct a universal rating system using a simple, unsupervised classifier based on the two proposed metrics. This rating system is capable of classifying both individual puzzles and entire difficulty levels from the different Sudoku websites into three categories - Universal Easy, Universal Medium, and Universal Hard - thereby enabling consistent difficulty mapping across Sudoku websites. The experimental results show that for 4 out of 5 Sudoku websites, the universal classification aligns well with website-labeled difficulty levels. Finally, I present an algorithm that can be used by early Sudoku practitioners to solve Sudoku puzzles.
| Comments: | 25 pages, 9 Figures |
| Subjects: | Artificial Intelligence (cs.AI) |
| ACM classes: | I.2.8 |
| Cite as: | arXiv:2507.21137 [cs.AI] |
| (or arXiv:2507.21137v2 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2507.21137 arXiv-issued DOI via DataCite |
Submission history
From: Arman Eisenkolb-Vaithyanathan [view email]
[v1]
Tue, 22 Jul 2025 22:32:30 UTC (625 KB)
[v2]
Sun, 11 Oct 2026 23:29:34 UTC (752 KB)
来源：arXiv：cs.AI · arxiv.org