What happens when Sudoku scales?DRAFT
I have published a repository of 434,201 generated Sudoku instances, ranging from 6x6 to 36x36. The collection is the main result of my ModRef 2026 paper Scaling Sudoku as a Constraint Problem. The paper explains how I generated the instances and measures how their propagation-based hardness changes with size.
The change in scale is easier to see than to describe. The widget below shows one published base instance at each size. Its width stays fixed while the number of cells grows.
Generated instances at five sizes
Building the collection
In his 2005 paper Sudoku as a Constraint Problem, Helmut Simonis used published 9x9 Sudoku instances as a compact test bed for constraint modelling. He compared increasingly strong propagation schemes by asking which ones could solve a puzzle without search. I keep that experimental setup, but generate the instances and vary the grid size.
The repository starts with 32,000 unique-solution puzzles at sizes 6x6, 9x9, 16x16, 25x25, and 36x36. Another 402,201 instances are saved along 170,000 hardness walks.
A hardness walk starts from one of the generated puzzles and adds clues from its known solution. Whenever an easier propagation scheme becomes sufficient, that version of the puzzle is saved. The repository therefore contains both the difficult starting points and paths from them towards easier propagation categories.
Each puzzle comes as a text file with JSON metadata, and the repository includes tools for validating the corpus and selecting smaller subsets.
What changes with size
The figure adapts the cross-size summary from the paper. Each bucket names the weakest successful propagation scheme. Val uses value propagation, Dom uses the stronger domain-consistent model, and BS adds bounds shaving. Search means that none of the tested schemes solved the puzzle by propagation alone.
The shift with size is sharp. Every generated 6x6 and 9x9 starting puzzle is covered by the tested family. At 16x16, propagation alone solves 84.9%. None of the 1,000 generated 25x25 or 1,000 generated 36x36 starting puzzles are solved without search, even with domain-consistent propagation and domain shaving.
That does not make the larger puzzles isolated. Adding clues moves them towards easier propagation categories, but the walk gets longer. The average number of clues needed for a verified category drop grows from 1.20 at 6x6 to 24.12 at 36x36.
Within this generated corpus, the sufficient propagation scheme changes as the grid grows. Runtime is not the only difference. The comparison does have a limitation. Clue density is a feature of the generated puzzles, not an experimental parameter held fixed across sizes. Median fill rises from 27.8% at 6x6 to 52.2% at 36x36 because of the uniqueness-preserving clue-removal process. The comparison describes this collection, not every generalized Sudoku puzzle.
The hardness labels and walks provide several ways to choose a useful subset from the public repository. Those instances can then be reclassified or tested with other models and solvers. The paper documents the generation method and the experiments behind those labels.