Scaling Sudoku as a Constraint Problem

This paper revisits Helmut Simonis’s 2005 study of Sudoku as a constraint problem and extends it from the standard 9x9 grid to sizes 6x6, 9x9, 16x16, 25x25, and 36x36. The generated corpus contains 32,000 unique-solution base puzzles and more than 400,000 easier variants produced by adding clues back.

The complete 434,201-instance corpus is available separately, with the base puzzles, saved hardness-walk variants, JSON metadata, and corpus utilities.

The familiar propagation-based hardness categories remain useful, but their distribution changes sharply with size. All generated 6x6 and 9x9 starting puzzles, and 84.9% of the 16x16 puzzles, are solved without search by the tested propagation family. None of the 25x25 or 36x36 starting puzzles are. Hardness walks connect these larger puzzles to easier categories, but require increasingly many added clues to do so.