# Difficulty Rating of Sudoku Puzzles: An Overview and Evaluation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2014.

## Built on by (most cited first, 4 of 4)

- [Using Small MUSes to Explain How to Solve Pen and Paper Puzzles](https://mlsanity.com/paper/2104.15040/) (2021)
- [BiRating -- Iterative averaging on a bipartite graph of Beat Saber scores, player skills, and map difficulties](https://mlsanity.com/paper/2502.19742/) (2025)
- [Toward a Universal Characterization of Sudoku Puzzle Difficulty](https://mlsanity.com/paper/2507.21137/) (2025)
- [Evaluating SAT Solver Metrics as Predictors of Human-Perceived Nonogram Difficulty](https://mlsanity.com/paper/2608.23300/) (2026)

## Abstract (arXiv)

How can we predict the difficulty of a Sudoku puzzle? We give an overview of difficulty rating metrics and evaluate them on extensive dataset on human problem solving (more then 1700 Sudoku puzzles, hundreds of solvers). The best results are obtained using a computational model of human solving activity. Using the model we show that there are two sources of the problem difficulty: complexity of individual steps (logic operations) and structure of dependency among steps. We also describe metrics based on analysis of solutions under relaxed constraints -- a novel approach inspired by phase transition phenomenon in the graph coloring problem. In our discussion we focus not just on the performance of individual metrics on the Sudoku puzzle, but also on their generalizability and applicability to other problems.