🧩 Constraint Solving POTD:Problem of the Day: Sudoku Solving via Constraint Propagation

[github-actions[bot]]

Problem Statement

Sudoku is a classic puzzle that challenges solvers to fill a 9×9 grid with digits 1–9 such that:

• Each row contains each digit exactly once
• Each column contains each digit exactly once
• Each of the nine 3×3 boxes contains each digit exactly once

Small Instance (4×4 Sudoku):

 2 | _
---+---
 _ | 1
---+---

Fill the 4×4 grid using digits {1, 2, 3, 4} under the same rules.

Input: A partially filled grid (clues).
Output: A complete grid satisfying all constraints, or "UNSAT" if no solution exists.

---

Why It Matters

Mathematical recreation & education: Sudoku demonstrates the power of declarative constraint solving—modeling a problem is often easier than writing search algorithms by hand.

Propagation algorithms in practice: Real-world scheduling, resource allocation, and product configuration problems use the same constraint propagation and search techniques that solve Sudoku efficiently.

Solver benchmarking: Sudoku instances are used to evaluate propagation strength, variable ordering heuristics, and branching strategies in constraint solvers.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision variables:
grid[i][j] ∈ {1..9} for each cell (i,j) in the 9×9 grid.

Constraints:

• AllDifferent(grid[i][0], ..., grid[i][8]) for each row i
• AllDifferent(grid[0][j], ..., grid[8][j]) for each column j
• AllDifferent cells in each 3×3 box

Trade-offs:

• ✅ Expressiveness: Naturally captures the problem structure.
• ✅ Propagation: Arc consistency and the AllDifferent global constraint prune the search space aggressively.
• ✅ Scalability: Solvers (Gecode, MiniZinc, OR-Tools) solve even hard 9×9 instances in milliseconds.

Approach 2: SAT Encoding

Decision variables:
For each cell (i,j) and digit d, introduce boolean variable x_{i,j,d} (true if cell (i,j) contains digit d).

Constraints:

• Cardinality: Each cell contains exactly one digit: ∑_d x_{i,j,d} = 1 (or via "at-most-one" clauses).
• Uniqueness per row: ¬(x_{i,j,d} ∧ x_{i,k,d}) for all j ≠ k (no two cells in row i contain digit d).
• Similar clauses for columns and boxes.

Trade-offs:

• ✅ Simplicity: Encodes into CNF, suitable for modern SAT solvers (Minisat, Glucose).
• ⚠️ Variable blowup: 9×9×9 = 729 variables (vs. 81 in CP).
• ⚠️ Propagation: Unit propagation is weaker than arc consistency; SAT solvers may explore larger search trees.
• ✅ Flexibility: Easy to add constraints (e.g., "at least 3 clues in row 1").

Example CP Model (MiniZinc)

int: n = 9;
int: box = 3;
array[1..n, 1..n] of 0..n: given;

var 1..n: grid[1..n, 1..n];

% Clues
constraint forall(i in 1..n, j in 1..n)(
  if given[i,j] > 0 then grid[i,j] = given[i,j] endif
);

% Rows
constraint forall(i in 1..n)(
  all_different([grid[i,j] | j in 1..n])
);

% Columns
constraint forall(j in 1..n)(
  all_different([grid[i,j] | i in 1..n])
);

% 3×3 boxes
constraint forall(bi in 0..box-1, bj in 0..box-1)(
  all_different([grid[i,j] | 
    i in 1+bi*box..1+(bi+1)*box-1,
    j in 1+bj*box..1+(bj+1)*box-1])
);

solve satisfy;

---

Key Techniques

1. Arc Consistency (AC-3 Algorithm)

Before searching, repeatedly remove values from cell domains that cannot participate in any valid solution. For Sudoku, if a row already contains the digit 5, remove 5 from all other cells in that row. Repeat until no more reductions occur. This "constraint propagation" phase often solves easy to moderate puzzles without search.

2. Global Constraint: AllDifferent

The AllDifferent constraint on a set of variables enforces that all take distinct values. Modern solvers use:

• Matching algorithms: Build a bipartite graph (variables ↔ values) and check if a perfect matching exists.
• Bounds consistency: If a value can only go to one variable, assign it immediately.

This is far more powerful than propagating pairwise inequality constraints.

3. Search Strategy: Minimum Remaining Values (MRV)

When branching, choose the cell with the fewest possible values. Sudoku solvers often branch on the most constrained cells first, dramatically reducing the search tree. Combine MRV with a good value ordering (e.g., try digits that appear least in neighboring boxes first).

---

Challenge Corner

1. Symmetry Breaking:
Sudoku puzzles have rotations, reflections, and digit permutations that preserve solutions. Can you add constraints to break these symmetries and speed up solving?

2. Minimal Puzzles:
A valid Sudoku puzzle has exactly one solution and uses the minimum number of clues (typically 17 for 9×9). Given a completed grid, how would you find or verify a minimal puzzle?

3. Hardness Classification:
What properties of clue placement (distribution across boxes, row/column density) correlate with puzzle difficulty? Can you design a heuristic to predict which instances will require deep search?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (eds.). Handbook of Constraint Programming. Elsevier, 2006.
   → Chapter on arc consistency algorithms and global constraints.

2. Stuckey, P. J. et al. The MiniZinc Handbook. (www.minizinc.org/redacted)
   → MiniZinc models and solver integration for puzzles.

3. Gomes, C. P., Sellmann, M. "Streamlined constraint reasoning." In Recent Advances in Constraints, 2004.
   → Techniques for boosting propagation in puzzles.

4. Sudoku Wikipedia: (en.wikipedia.org/redacted)
   → History, variants, and mathematical theory.

---

Next time: Scheduling problems and the power of job-shop formulations.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 5.93 AIC · ⌖ 3.22 AIC · ⊞ 6.1K · ◷

• expires on Aug 24, 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 #53648.