🧩 Constraint Solving POTD:Problem of the Day: Sudoku Constraint Satisfaction

[github-actions[bot]]

Problem Statement

Sudoku is a combinatorial puzzle where you fill a 9×9 grid divided into nine 3×3 blocks with digits 1–9 such that:

• Each row contains each digit exactly once
• Each column contains each digit exactly once
• Each 3×3 block contains each digit exactly once

A valid puzzle provides a partial assignment and has a unique solution.

Small instance (4×4 variant):

  1 2 | 3 4
  ----+----
  . . | 4 .
  . . | . .
  ----+----
  . . | . 2
  . 1 | . .

Input: Partially filled grid (givens).
Output: Completed grid satisfying all constraints, or "no solution."

Why It Matters

• Brain training & recreation: Millions solve Sudoku puzzles daily for mental challenge
• Algorithm testing: Sudoku is a benchmark for CSP solvers—easily scaled (NxN grids) and computationally interesting
• Logic puzzle design: Puzzle designers use constraint solvers to verify uniqueness and difficulty
• Educational tool: Teaches propagation and backtracking without complex domain knowledge

Modeling Approaches

Approach 1: Constraint Programming (CP) — Explicit All-Different

Variables: x[i,j] ∈ {1..9} for each cell (i,j)
           x[i,j] = given[i,j] for initial assignments

Constraints:
  - ∀ i ∈ [1..9]: AllDifferent(x[i,1], x[i,2], ..., x[i,9])     (rows)
  - ∀ j ∈ [1..9]: AllDifferent(x[1,j], x[2,j], ..., x[9,j])     (columns)
  - ∀ b ∈ [1..9]: AllDifferent(x[i,j] : (i,j) ∈ block_b)        (3×3 blocks)

Search: Label variables with domain reduction via arc consistency

Trade-offs:

• ✅ Highly expressive; leverages strong global constraint propagation
• ✅ Fast on instances with many givens
• ❌ Weaker on extremely sparse puzzles (requires more search)

Approach 2: SAT Encoding — Cardinality Constraints

Boolean variables: b[i,j,v] ∈ {True, False}  
  Meaning: b[i,j,v] = True iff cell (i,j) contains digit v

Constraints:
  - ∀ (i,j): Exactly-one(b[i,j,1], ..., b[i,j,9])             (each cell has one digit)
  - ∀ i,v: Exactly-one(b[i,1,v], ..., b[i,9,v])               (digit v once per row)
  - ∀ j,v: Exactly-one(b[1,j,v], ..., b[9,j,v])               (digit v once per column)
  - ∀ block_b, v: At-most-one(b[i,j,v] : (i,j) ∈ block_b)     (digit v ≤1 per block)
  - Givens: b[i,j,given[i,j]] = True

Solve with DPLL-based SAT solver

Trade-offs:

• ✅ Leverages mature SAT solvers (CaDiCaL, Kissat)
• ✅ Systematic inference via unit propagation
• ❌ Larger formula size; requires domain encoding overhead
• ❌ Less efficient than specialized CP for this domain

Key Techniques

1. Arc Consistency (AC-3/AC-2001)

Sudoku's row/column/block constraints are pairwise incompatible. AC enforces that every value in a cell's domain has a compatible value in neighboring cells. Iterative application often solves puzzles with many givens without search.

2. Hidden Singles & Naked Singles

• Naked single: If a cell has only one value left in its domain, assign it
• Hidden single: If a digit appears in only one cell within a row/column/block, assign it there
  These are special cases of constraint propagation and solve ~90% of everyday puzzles.

3. Search with Minimum Remaining Values (MRV) + Backtracking

When propagation stalls, branch on the cell with smallest domain (most constrained variable heuristic). Use nogood recording or conflict-driven learning to prune redundant search space. For hard puzzles, restart heuristics improve performance.

Challenge Corner

Question for readers:

Sudoku has 6.67 × 1021 valid grids but only ~5.5 × 1015 essentially different solutions (accounting for symmetry).

• Can you identify what symmetries preserve a valid Sudoku solution? (Hint: not just rotations!)
• How would you add symmetry-breaking constraints to a CP model to eliminate these redundant branches?
• What's the minimum number of givens required to guarantee a unique solution?

Try modeling a 4×4 Sudoku variant in your favorite solver and experiment with these questions.

References

1. Rossi, F., van Beek, P., & Walsh, T. (Eds.) Handbook of Constraint Programming. Elsevier, 2006.
   → Comprehensive treatment of CSP theory and Sudoku as a case study.

2. Felgenhauer, B., & Jarvis, F. "Enumerating possible Sudoku grids." 2005.
   → Definitive source on the count of valid Sudoku grids and symmetry analysis.

3. Lynce, I., & Ouaknine, J. "Sudoku as a SAT Problem." AAAI Workshop on Advances in Verification, 2006.
   → Demonstrates SAT encoding and solver comparison.

4. Russell, S., & Norvig, P. Artificial Intelligence: A Modern Approach (4th ed.), 2020. Ch. 6.
   → Accessible introduction to CSP with Sudoku examples and live solver demo.

---

Next problem: Stay tuned for scheduling, routing, packing, and more! 🎯

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

• expires on Aug 28, 2026, 3:38 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 #54778.