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.
Figures & tables
Figure 1: Two New York Times Sudoku Puzzles from July 23rd 2024 with candidates filled in
Figure 2: A rectangle is drawn between the cells where X-wing should be used
Website
Short Clauses (%)
Medium Clauses (%)
Long Clauses (%)
New York Times
Easy
67
33
0
Medium
17
71
13
Hard
15
72
13
Sudoku.org.uk
Gentle
24
67
9
Table 1: Clause Length Distribution across 5 websites
Website
Clause Length Distribution
Nishio Human Cycles with 4 Human Strategies
Nishio Human Cycles with 2 Human Strategies
NyTimes Sudokus
-0.80
0.84
0.68
Sudoku.org.uk
-0.47
0.84
0.81
Extreme Sudoku
-0.02
-0.002
-0.03
Sudoku of the Day
-0.75
0.89
0.83
Sudoku of the Day UK
-0.28
0.70
0.61
Table 2: Spearman’s Rank Correlation Coefficient between website-provided difficulty levels and two proposed metrics - Clause Length Distribution and Nishio Human Cycles. For Clause Length Distribution, I use the percentage of short clauses as the metric to calculate the correlation coefficient. Each puzzle is assigned an integer ranking based on the website’s difficulty level ordering (e.g. in New York Times, Easy puzzles are assigned 1, Medium puzzles are assigned 2, and Hard puzzles are assigned 3).
Nishio Human Cycles (50 Random Starts)
Percentage of Puzzles solved by Strategies
Difficulty
4 Strategies
2 Strategies
2 Strategies (%)
3 Strategies (%)
4 Strategies (%)
Easy
Mean
1.61
1.62
100
100
100
Median
1.58
1.60
Medium
Mean
6.74
12.40
0
52.5
62.5
Table 3: New York Times
Nishio Human Cycles (50 Random Starts)
Percentage of Puzzles solved by Strategies
Difficulty
4 Strategies
2 Strategies
2 Strategies (%)
3 Strategies (%)
4 Strategies (%)
Gentle
Mean
2.45
2.51
98
98
98
Median
2.38
2.4
Moderate
Mean
3.09
3.77
97
98
98
Table 4: Sudoku.org.uk
Nishio Human Cycles (50 Random Starts)
Percentage of Puzzles solved by Strategies
Difficulty
4 Strategies
2 Strategies
2 Strategies (%)
3 Strategies (%)
4 Strategies (%)
Evil
Mean
8.01
14.01
0
0
5
Median
6.63
10.09
Excessive
Mean
7.13
10.89
0
0
3
Table 5: Extreme Sudoku
Nishio Human Cycles (50 Random Starts)
Percentage of Puzzles solved by Strategies
Difficulty
4 Strategies
2 Strategies
2 Strategies (%)
3 Strategies (%)
4 Strategies (%)
Beginner
Mean
1.73
1.73
100
100
100
Median
1.72
1.70
Easy
Mean
2.09
2.14
100
100
100
Table 6: Sudoku of the Day
Nishio Human Cycles (50 Random Starts)
Percentage of Puzzles solved by Strategies
Difficulty
4 Strategies
2 Strategies
2 Strategies (%)
3 Strategies (%)
4 Strategies (%)
Easy
Mean
3.48
5.20
82
93
95
Median
2.83
3.43
Medium
Mean
4.01
5.49
78
90
90
Table 7: Sudoku of the Day UK
Figure 4: Nishio Human Cycles distribution over the 1320 Sudoku puzzle dataset. In this histogram, the width of each bin is is one Nishio Human Cycle.
Figure 5: Clause Length Distribution over the 1320 Sudoku puzzle dataset. In this histogram, the width of each bin is one percentage (short clauses).
Figure 6: Difficulty levels from the 5 websites classified into one of three universal categories based Mean and Median Nishio Human Cycles (from Tables 3 - 7 ).
Figure 7: Difficulty levels from the 5 websites classified into one of three universal categories based on Mean percentage of short clauses (from Table 1 ).
Figure 8: Three constructively identical Extreme Sudoku puzzles from three different difficulty levels: Egregious, Extreme, and Excessive. Given cells are shaded. Notice that the Nishio Human Cycles and Clause Length Distribution metrics are close across all three puzzles.
Difficulty Level
Constructively Identical Puzzles
Evil
44/60
Excessive
45/60
Egregious
50/60
Excruciating
54/60
Extreme
49/60
Table 8: Constructively identical puzzle counts for each Extreme Sudoku difficulty level (out of 60).
Nishio Human Cycles
Nishio Human Cycles
Website
4 Strategies
2 Strategies
Website
4 Strategies
2 Strategies
New York Times
Sudoku of the Day
Easy
Beginner
Mean
1
1
Mean
1
1
Median
1
1
Median
1
1
Medium
Easy
Table 9: Nishio Human Cycles (2 and 4 strategies) computed using the solver in Figure 9 on the five-website dataset.
Sudoku
Nishio Human Cycles
Platinum Blonde
1074.92
Golden Nugget
750.22
tarx0134
840.02
Red Dwarf
508.88
Table 10: Nishio Human Cycles for 4 Ultra-Hard Sudoku puzzles
Universal Category
Number of Puzzles from nikoli_100 dataset
Universal Easy
53
Universal Medium
24
Universal Hard
23
Table 11: Universal Classification via Nishio Human Cycles for the nikoli_100 dataset
Algorithmic solver effort is often assumed to align with perceived puzzle difficulty, but this assumption is rarely tested against human solving data. We evaluate this assumption for Nonograms, a popular logic puzzle similar to Sudoku in which numeric clues along each row and column determine a unique solution grid. We formulate Nonograms as a constraint satisfaction problem and solve them using existing SAT solvers. We then conduct a user study in which we collect data on both participant interactions and reported difficulty. We find that neither participants' reported difficulty nor their behavioural signals correlate meaningfully with SAT solver metrics; however, we find evidence that expertise moderates the relationship between solver metrics and reported difficulty. In this process, we uncover distinct, recurring solving strategies that indicate human preference for complex propagation, diverging from solver-measured complexity.
Changdao He, Yibing Ju, Jonathan Calver +1
Department of Computing Science, University of Alberta · Department of Computer Science, University of Toronto
Sudoku is a representative constraint satisfaction problem that requires global structural reasoning under strict discrete constraints. The existing works of solving Sudoku mainly focus on two dominant approaches, i.e., traditional heuristic and deep learning solver. However, they suffer from two complementary limitations: learning-based solvers lack hard correctness guarantees, while complete symbolic solvers are still prone to long-tail search. To address these shortcomings, we propose a novel diffusion model-guided approach, termed as DiBS, for the branch selection search process. Specifically, DiBS keeps the symbolic solver complete and uses the diffusion model as a branch-ordering guide. The core method is ranking candidate values under the current partial assignment and lightweight consistency signal. Furthermore, we provide an in-depth theoretical proof to reveal how it works and why it works. Experiments on the challenging Royle 17-clue Sudoku benchmark show that our DiBS substantially reduces search cost relative to strong heuristic baselines, especially in nodes, backtracks, and long-tail percentiles. Besides, these results confirm that learned global guidance is effective on hard instances where branch-order mistakes are most expensive. All codes are available at https://github.com/shanxierdan/DiBS.
Bo Liu, Yuan Xie, Yuan Gao +4
1Jilin University · 2The Chinese University of Hong Kong, Shenzhen · 3Southwest University +3
Neural solvers are built to deduce, branch, and revise intermediate states. The Lattice Deduction Transformer (LDT) appears to do exactly that. In clue-rich Sudoku, it does not: one forward pass commits essentially the entire grid (every blank cell on standard 6x6, 94-96% on augmented 9x9), turning the iterative solver into a one-shot predictor wrapped in an exact verifier. All hard-slice failures are decided before search begins, when the first pass confidently deletes a value required by the true solution. We call this first-pass poisoning. Adding learned branching, MRV, backtracking, value exclusion, and shared nogoods (CoLT) does not change which Sudoku instances are solved; it cuts repeated invalid derivations 1,497-fold. At the frozen training budget, constraint-graph attention alone matches full-CoLT accuracy, while positional tables recover only under substantially longer training, indicating an optimization and sample-efficiency advantage rather than an absolute capacity difference. The diagnosis predicts two effective interventions. Digit-permutation augmentation raises 9x9 accuracy from below 1% to 96.5 +/- 0.3 across three training seeds on a symmetry-disjoint split. Test-time union over symmetry-transformed passes raises all three hard-slice checkpoints from 72.8-78.9% to 100% without retraining. On from-scratch graph coloring, one-shot behavior disappears and search changes accuracy. In clue-rich completion, LDT-like systems are one-shot amortized predictors rather than learned search procedures: accuracy is determined by calibration and symmetry, while search primarily removes computational waste.