🧩 Constraint Solving POTD:Problem of the Day: Sudoku

[github-actions[bot]]

Problem Statement

Sudoku is a classic constraint satisfaction puzzle with a deceptively simple premise: fill a 9×9 grid divided into nine 3×3 blocks with digits 1–9 such that:

• Each digit appears exactly once in every row
• Each digit appears exactly once in every column
• Each digit appears exactly once in every 3×3 block

Concrete Instance (4×4 variant):

┌─────┬─────┐
│ 1 · │ · · │
│ · · │ · · │
├─────┼─────┤
│ · · │ · 2 │
│ · · │ · · │
└─────┴─────┘

Find values for the blanks (·) such that each row, column, and 2×2 block contains {1, 2, 3, 4}.

Why It Matters

Puzzle entertainment and education: Sudoku has introduced millions of people to the power of logical deduction and constraint reasoning, making it an accessible entry point to combinatorial problem-solving.

Prototype for harder problems: Variants and generalizations (Killer Sudoku, Samurai Sudoku, irregular grids) expose deeper algorithmic challenges that appear in real scheduling and configuration systems.

CSP solver benchmarking: Sudoku instances form a standard test suite for constraint solvers, especially for tuning propagation and search heuristics.

---

Modeling Approaches

Approach 1: Pure Constraint Programming (CP)

Decision variables: x[i,j] ∈ {1..9} for cell (i, j)

Constraints:

AllDifferent(x[i, 1], x[i, 2], ..., x[i, 9]) for each row i
AllDifferent(x[1, j], x[2, j], ..., x[9, j]) for each column j
AllDifferent(x[i, j] : i ∈ block_rows, j ∈ block_cols) for each 3×3 block
x[i, j] = clue  (for given cells)

Strengths:

• Native support for AllDifferent global constraint with strong arc consistency (AC3)
• Compact representation; easy to reason about
• Excellent propagation: each variable domain shrinks as constraints fire

Trade-offs: May require more search than specialized encodings; best with advanced value ordering heuristics.

---

Approach 2: Integer Linear Programming (MIP)

Decision variables: x[i,j,d] ∈ {0,1} (binary: cell (i,j) contains digit d)

Constraints:

Σ_d x[i,j,d] = 1  (each cell gets exactly one digit)
Σ_j x[i,j,d] = 1  (each digit appears once per row)
Σ_i x[i,j,d] = 1  (each digit appears once per column)
Σ_(i,j)∈block x[i,j,d] = 1  (each digit appears once per block)
x[i,j,d] = 1 if clue at (i,j) is d, else 0

Strengths:

• Leverages mature MIP solvers with cutting planes and branch-and-bound
• Scales to large instances with preprocessing techniques
• Clear linear structure for commercial solvers (CPLEX, Gurobi)

Trade-offs: 729 binary variables (vs. 81 domain variables in CP); weaker constraint propagation without specialized branching; overkill for small puzzles.

---

Key Techniques

1. Constraint Propagation (Arc Consistency)

Naked singles & hidden singles are the most powerful deduction techniques:

• Naked single: If a cell's domain shrinks to a single value, assign it.
• Hidden single: If a digit can go in only one cell within a row/column/block, place it there.

Efficient CP solvers iterate these rules to propagate the AllDifferent constraint, dramatically reducing search space before search begins.

2. Search Strategy with Intelligent Variable Ordering

Minimum remaining values (MRV) heuristic: Branch on the cell with the smallest domain first. For Sudoku, this is highly effective because constrained cells are resolved early, triggering cascading propagations.

Restart strategies: Rapid restarts with randomization help escape weak decision sequences; modern solvers use dynamic restart policies (e.g., Luby, Walsh sequences).

3. Symmetry Breaking

Sudoku has 5.47 × 10⁹ essentially different valid grids due to symmetries (row/column permutations, band/stack permutations, digit relabeling). Canonical forms or symmetry-breaking constraints can prune the search tree when enumerating all solutions.

---

Challenge Corner

Open Question: Standard Sudoku propagation (arc consistency + naked/hidden singles) solves most published puzzles without search. Why are some rare instances harder to solve with pure constraint propagation, and what global properties (e.g., density, block structure) make them difficult?

Extension: How would you model Sudoku with uncertainty—e.g., cells that might contain multiple candidate values due to noisy input? Would a probabilistic CSP or a soft constraint approach be more suitable?

---

References

1. Constraint Programming: A Concise Introduction — Apt, K. (Cambridge, 2003). Chapter on CSP fundamentals with Sudoku examples.
2. The Hidden Logic of Sudoku — Bartlett & Chartier (Scientific American, 2006). Popular explanation of logical deduction techniques.
3. Sudoku Solver Benchmark — Heule, M. & Walsh, T. SAT competitions and CSP benchmarks. Available at (www.satisfiability.org/redacted)
4. OR-Tools Sudoku Example — Google's Constraint Programming library documentation includes an optimized Sudoku solver in Python and C++.

---

Posted: 2026-08-18 | Category: Classic CSP

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 5.79 AIC · ⌖ 4.54 AIC · ⊞ 6.2K · ◷

• expires on Aug 25, 2026, 3:37 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #53975.