{"id":"arxiv/2610.37411","url":"https://arxiv.org/abs/2610.37411","tags":["math.OC"],"score":0,"title":"Measuring Sudoku Difficulty: Formulation, Propagation and Uniqueness Certification","domain":"math.OC","source":"arxiv","authors":["Aled Williams"],"reviews":0,"subject":"math.OC","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-27","reactions":{}}