arXiv:2507.21137cs.AI2025-07

提出两种新方法,统一衡量不同网站的数独难度。

Project Patti: Why can You Solve Diabolical Puzzles on one Sudoku Website but not Easy Puzzles on another Sudoku Website?

  • 将数独转为逻辑问题,分析命题长度分布
  • 模拟人类解法策略,统计使用次数衡量难度
  • 构建通用评级系统,跨平台匹配难易程度

本文旨在回答“不同数独网站的难度标准是什么?”这一问题。通过两种可解所有数独谜题的方法,提出两个新度量标准:第一种基于将数独转化为可满足性(SAT)问题,利用SAT命题长度分布捕捉谜题结构复杂性,包括已知数字的数量及其位置;第二种通过在回溯算法Nishio中融合四种常见数独策略,模拟人类解题过程,统计在随机化Nishio迭代中策略被调用的次数作为难度指标。基于这两个指标,分析了来自五个主流网站超过一千个数独谜题,对各网站难度等级进行刻画。采用斯皮尔曼秩相关系数评估指标与网站标注难度之间的关系,发现4/5网站存在强相关性。进一步构建一个基于双指标的简单无监督分类器,实现对单个谜题及整个难度等级的统一分类——通用简单、通用中等、通用困难,从而实现跨平台难度映射。实验表明,4/5网站的通用分类与原网站标注高度一致。最后,提出一套适合初学者使用的解题算法。

原文摘要 · Abstract (English)

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.

数独难度评级逻辑推理无监督学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。