# Toward a Universal Characterization of Sudoku Puzzle Difficulty

arXiv: https://arxiv.org/abs/2507.21137 · HTML: https://mlsanity.com/paper/2507.21137/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 21 references that are in the map.
- First posted on arXiv 22 Jul 2025.

## Builds on (most cited first, 6 of 6)

- [Large Language Model Guided Tree-of-Thought](https://mlsanity.com/paper/2305.08291/) (2023)
- [Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles](https://mlsanity.com/paper/2409.10502/) (2024)
- [Sudoku-Bench: Evaluating creative reasoning with Sudoku variants](https://mlsanity.com/paper/2505.16135/) (2025)
- [Explaining Puzzle Solutions in Natural Language: An Exploratory Study on 6x6 Sudoku](https://mlsanity.com/paper/2505.15993/) (2025)
- [Difficulty Rating of Sudoku Puzzles: An Overview and Evaluation](https://mlsanity.com/paper/1403.7373/) (2014)
- [Minuet: A method to solve Sudoku puzzles by hand](https://mlsanity.com/paper/1812.06778/) (2018)

## Abstract (arXiv)

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.