Scaling Sudoku as a Constraint Problem

fit text

2005 → 2026

paragraph

Mikael Z. Lagerkvist · ModRef 2026

1 / 21

Read each hardness tag from left to right

table
Tag groupWhat it records
Val · Bnd · DomBase propagation: value, bounds-consistent, or domain-consistent
BS · DSShaving: bounds shaving or full-domain singleton shaving
Chan · Same · Cmat · RbmAdditional redundant models and channeling constraints
SearchNo tested propagation tag solved the instance without search
paragraph

Example · ValBS = value propagation + bounds shaving

2 / 21

6×6

layout: columns

Puzzle

figureGenerated 6 by 6 Sudoku instance with eight written hints

Instance

unordered list
  • Size · 6×6
  • Cells · 36
  • Hardness · ValChan
  • Generation · 0.302 s
3 / 21

9×9

layout: columns

Puzzle

figureGenerated 9 by 9 Sudoku instance with 24 written hints

Instance

unordered list
  • Size · 9×9
  • Cells · 81
  • Hardness · DomBS
  • Generation · 2.212 s
4 / 21

16×16

layout: columns

Puzzle

figureGenerated 16 by 16 Sudoku instance with 95 written hints

Instance

unordered list
  • Size · 16×16
  • Cells · 256
  • Hardness · Search
  • Generation · 33m 12.139s
5 / 21

25×25

layout: columns

Puzzle

figureGenerated 25 by 25 Sudoku instance with 269 written hints

Instance

unordered list
  • Size · 25×25
  • Cells · 625
  • Hardness · Search
  • Generation · 1h 13m 15.700s
6 / 21

36×36

layout: columns

Puzzle

figureGenerated 36 by 36 Sudoku instance with 646 written hints

Instance

unordered list
  • Size · 36×36
  • Cells · 1,296
  • Hardness · Search
  • Generation · 1h 27m 55.493s
7 / 21

A tag records the weakest scheme that finishes without search

figureTwo unique-solution, locally minimal Sudoku instances tagged by the weakest tested propagation scheme that solves them
If no tested scheme finishes by propagation alone, the tag is Search.
8 / 21

Generation and hardness tagging answer different questions

figureConstruction and propagation-tagging pipeline producing a public corpus of 434,201 Sudoku instances
Generate unique puzzles first; measure propagation afterwards.
9 / 21

The 9×9 corpus occupies 8 of 19 propagation schemes

figureNineteen-node Simonis-style propagation lattice with occupancy of generated nine-by-nine starting instances
For 9×9 starts, occupied endpoints test an implication; empty nodes provide no test.
10 / 21

Search-free coverage first breaks at 16×16

figureSearch-free rates are 100%, 100%, 84.9%, 0%, and 0% as grids scale from 6×6 to 36×36
Coverage falls from 100% at 9×9 to 84.9% at 16×16, then to 0% at 25×25 and 36×36.
11 / 21

Walks: Start from generated 16×16

layout: columns

Puzzle

figure16 by 16 Search puzzle at the start of a six-transition hardness walk
Dark ink: base hints.

Hardness path

unordered list
  • ▶ Search · 91 hints · +0
12 / 21

Walks: One added hint reaches DomDS

layout: columns

Puzzle

figure16 by 16 walk puzzle at DomDS with one new hint circled in rose
Rose circle: new hint on this transition.

Hardness path

unordered list
  • Search · 91 hints · +0
  • ▶ DomDS · 92 hints · +1
13 / 21

Walks: A second hint reaches DomBS

layout: columns

Puzzle

figure16 by 16 walk puzzle at DomBS with earlier additions boxed in blue and the new hint circled in rose
Blue square: earlier addition · rose circle: new.

Hardness path

unordered list
  • Search · 91 hints · +0
  • DomDS · 92 hints · +1
  • ▶ DomBS · 93 hints · +2
14 / 21

Walks: Ten more hints reach BndDS

layout: columns

Puzzle

figure16 by 16 walk puzzle at BndDS with previous additions boxed and ten new hints circled
Previous additions stay boxed; this transition is circled.

Hardness path

unordered list
  • Search · 91 hints · +0
  • DomDS · 92 hints · +1
  • DomBS · 93 hints · +2
  • ▶ BndDS · 103 hints · +12
15 / 21

Walks: One more hint reaches BndBS

layout: columns

Puzzle

figure16 by 16 walk puzzle at BndBS with prior additions boxed and one new hint circled
The shape change identifies the newest hint without color.

Hardness path

unordered list
  • Search · 91 hints · +0
  • DomDS · 92 hints · +1
  • DomBS · 93 hints · +2
  • BndDS · 103 hints · +12
  • ▶ BndBS · 104 hints · +13
16 / 21

Walks: Eleven more hints reach ValBS

layout: columns

Puzzle

figure16 by 16 walk puzzle at ValBS with earlier additions boxed and eleven new hints circled
The path is cumulative; only the newest delta is circled.

Hardness path

unordered list
  • Search · 91 hints · +0
  • DomDS · 92 hints · +1
  • DomBS · 93 hints · +2
  • BndDS · 103 hints · +12
  • BndBS · 104 hints · +13
  • ▶ ValBS · 115 hints · +24
17 / 21

Walks: Forty added hints finally reach Val

layout: columns

Puzzle

figureFinal 16 by 16 Val puzzle with 24 earlier added hints boxed and 16 newly added hints circled
40 cumulative additions: 24 boxed earlier · 16 circled now.

Hardness path

unordered list
  • Search · 91 hints · +0
  • DomDS · 92 hints · +1
  • DomBS · 93 hints · +2
  • BndDS · 103 hints · +12
  • BndBS · 104 hints · +13
  • ValBS · 115 hints · +24
  • ▶ Val · 131 hints · +40
18 / 21

The 434,201-instance corpus

table
GridBasesWalksSaved variantsExact local minimality
6×610,00050,00049,515100.0%
9×910,00050,00092,456100.0%
16×1610,00050,000167,026100.0%
25×251,00010,00046,079100.0%
36×361,00010,00047,1250.2%
quote

Corpus total · 32,000 bases + 402,201 saved walk variants = 434,201 instances. Exact local minimality is certified for only 0.2% of the 36×36 bases.

19 / 21

9×9 checks the setup; 16×16 separates propagation schemes

layout: columns

9×9 · sanity check

fit text

100%

paragraph

10,000 bases

paragraph

Mostly one tag

16×16 · discriminator

fit text

84.9%

paragraph

10,000 bases

paragraph

Several tags + 15.1% Search

quote

Consequence · Start with tagged 16×16. Add 25×25 and 36×36 when the question is size scaling or missing reasoning.

20 / 21

Scale changes what Sudoku benchmarks measure

fit text

9×9 is simple. 16×16 and up more interesting.

figureQR code for the Scaled Sudoku Instances repository
github.com/zayenz/scaled-sudoku-instances
paragraph

434,201 instances to explore.

21 / 21