Measuring Sudoku Difficulty: Formulation, Propagation and Uniqueness Certification
math.OC
Submitted: 2026-10-27
Updated: 2026-10-27
Comments: 43 pages, 8 figures, 32 tables, 3 appendices
License: http://creativecommons.org/licenses/by/4.0/
The gist: Finding a Sudoku completion and proving that the completion is unique are different computational tasks.
Abstract
Finding a Sudoku completion and proving that the completion is unique are different computational tasks. Despite both concerning the same puzzle, their computational effort need not be closely related. In this paper, we investigate how this relationship depends on the mathematical formulation, solver and measure of computational effort. Using 32,000 uniquely solvable puzzles and 64 harder instances, we compare integer programming formulations and CP-SAT. Further, we prove that the raw natural formulation has an extremely weak linear programming relaxation, even with uniqueness exclusions. Computational experiments show that the relationship between completion and certification effort depends on the formulation, puzzle population, solver and effort measure, rather than on the puzzle alone.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise