brozonoyer/sudoku-extreme-multi-solution

sudoku-extreme-multi-solution

A controlled multi-solution Sudoku dataset derived from `sapientinc/sudoku-extreme` by deleting clues from uniquely solvable puzzles, with exact, doubly verified solution counts stratified over N ∈ {1, 2, 3, 4, 6, 8, 16} and the complete solution set enumerated for every item.

Built to study how architectures handle solution multiplicity (many valid answers requiring a global consistent choice) separately from serial deduction depth — e.g. for evaluating latent-communication training as in the RELAY line of work (arXiv:2605.22967). Deleting clues never decreases the number of solutions (monotonicity), and the number of solutions is controlled by which and how many clues are deleted.

Final strata (post dedup + leakage filtering)

Constructions per item (construction field):

• —single_deletion (~80–100% of every N ≥ 2 stratum): one clue removed; N verified exactly by capped counting. This backbone is covariate-matched across strata: |SMD| ≤ 0.12 on clue count and tdoku rating vs the base corpus, deleted-cell geometry near-uniform, and predicting N from (source, clue count) is near chance (21.0% vs 19.2% majority baseline, train). Use this subset for clean across-N contrasts.
• —composed_n2 (20% of N ∈ {4, 8, 16}): k = 2, 3, 4 clues removed, each of which individually yields exactly 2 solutions; kept only when the combination yields exactly 2^k. Where the 2^k solutions are additionally a verified bijection with toggles of k disjoint unavoidable sets, num_plan_bits = k (48–67% of composed items); otherwise null.
• —deletion_search (10% of N ∈ {3, 6}): randomized monotone deletion search accepted exactly at the target count.
• —redundant_control (all of N = 1): deletions of jointly redundant clues; the puzzle stays uniquely solvable. Caveat: only clue-rich, low-rating parents admit such deletions, so this stratum (and composed_n2 at N = 8, 16) is not covariate-matched to the others (SMD on clues up to +4.1). Treat construction as a stratification variable; never pool blindly.

Verification

Every released item was:

1. 1.counted and enumerated exactly (cap N+1) by a bitmask MRV DFS C solver with node budgets (no timeouts among released items);
2. 2.re-counted by an independently implemented pure-Python reference solver with a deliberately different algorithm shape — 0 disagreements (58 of the 725,063 verified candidates skipped on node guard);
3. 3.checked so that every solution is a valid complete grid, consistent with all givens, pairwise distinct, and containing the parent's original solution.

Leakage guards

• —Grid-level registry: all 4.25M upstream answers were canonicalized (branch-and-bound minlex over the full symmetry group). No solution of any released train item is canonically equal to any upstream test-side answer, and vice versa; no canonical solution grid is shared between released train and test items. This dropped 28,497 items whose extra solutions crossed the split — upstream sources cluster in grid space (grids one unavoidable-set toggle apart straddle the base train/test split), so this check is not vacuous.
• —Exact joint dedup: items equivalent as (puzzle, solution-set) objects under the full Sudoku symmetry group were deduplicated by explicit isomorphism testing (41,936 dropped; upstream dedup was exact-string only and contains many symmetric re-posts).
• —Test split: ≤ 1 item per base puzzle and per canonical grid class. Train: ≤ 1 per (base puzzle, stratum), ≤ 2 per base puzzle, ≤ 4 per grid class. base_group_id is an opaque per-grid-class key for grouped evaluation.

Provenance caveat: parents are public, so the original unique solution of any item is recoverable in principle by matching clue patterns against sapientinc/sudoku-extreme (and the provenance config makes lineage explicit for analysis). Robust evaluation must be set-valued by design — this matters when evaluating models pretrained on web data, and is irrelevant for models trained from scratch here.

Recommended metrics

solutions is semantically an unordered set (stored sorted for determinism). Recommended: randomly permute solution order during training; evaluate with any-solution exact match, chimera rate (output mixes two solutions without being either), determined-cell accuracy (against determined_board), and coverage/diversity across sampling seeds. Do not treat solutions[0] as a canonical target.

The base rating (tdoku backtracks on the parent) does not transfer to derived puzzles; it is provided as a parent covariate only (base_rating).

Deduction annotations

deduction_* fields trace the 13 propagation-sound strategies of `sudoku-solver-tim` (brute force excluded — it is unsound for N > 1) run to stall/solve, with every committed cell verified against the full solution set (0 violations). Identical annotation of the parent is in base_deduction_steps / base_stall_reason: base → derived steps shift by only +0.0 to +0.3 on the single-deletion backbone, so multiplicity is not confounded with a jump in this deduction-depth proxy. This is a solver-specific proxy, not "seriality" in general. base_num_steps joins the parent's annotation (with brute force) from `brozonoyer/sapientinc-sudoku-extreme-timvink-sudoku-solver` at pinned revision a2af3813.

Schema (config default)

Cells are row-major, indices 0–80; blanks are .; grids are 81-char strings of 1–9.

`provenance` config (analysis-only; keep out of training pipelines): item_id, base_row (row in upstream CSV), deleted_cells (list[int32]), original_solution_index (position of the parent's answer inside solutions).

`sweep` config: per upstream puzzle, the full single-deletion sweep statistics: num_deletions, num_individually_redundant_clues (the puzzle is clue-minimal iff 0 — only 2.35% of parents are non-minimal), counts n_eq_{1,2,3,4,6,8,16}, n_other_multi, n_ge_17, num_timeouts. One publishable summary: deleting a single clue from these near-minimal puzzles yields ≥ 17 solutions 81.4% of the time; exactly 2 solutions only 2.3% of multi-solution deletions — the "N=2 is typical" folklore does not hold here.

Reproducibility

repro.json pins the upstream revision and file hashes, solver source and binary hashes, and package versions. generation/ contains all scripts (C solver, slurm pipelines, selection with frozen manifests) and stage reports including leakage.json. Selection is deterministic given a private salt (withheld to keep base_group_id opaque). Theory: uniqueness ⟺ hitting all unavoidable sets (McGuire, Tugemann & Civario, "There is no 16-Clue Sudoku", 2012); minimal unavoidable sets have size 4, hence num_ambiguous_cells ≥ 4 whenever N ≥ 2.

Attribution and citation

Derived from `sapientinc/sudoku-extreme` (upstream sources: tdoku benchmark collections, enjoysudoku forum collections, kaggle; no explicit upstream license — treat accordingly). Deduction annotations use timvink/sudoku-solver.

If you use this dataset, please cite the RELAY paper (arXiv:2605.22967) and link this dataset page.