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

[github-actions[bot]]

Problem Statement

Sudoku is a logic puzzle where you fill a 9×9 grid with digits 1–9 such that:

• Each row contains all digits 1–9 exactly once
• Each column contains all digits 1–9 exactly once
• Each of the nine 3×3 boxes contains all digits 1–9 exactly once

A typical instance provides 20–30 pre-filled cells ("givens") and asks you to complete the grid uniquely.

Small Instance Example

Here's a 4×4 variant (filling with digits 1–4, each 2×2 box is a region):

Input:                  Solution:
+--+--+          +--+--+
|1 | 3|          |1 2|3 4|
|  |  |          |4 3|1 2|
+--+--+    →     +--+--+
|  |  |          |2 1|4 3|
|  |2 |          |3 4|2 1|
+--+--+          +--+--+

Input specification: A grid with some cells pre-filled (the "givens"), rest unknown.
Output specification: All cells assigned values 1–9 such that all constraints are satisfied, with a unique solution.

---

Why It Matters

Commercial impact: Sudoku appears in newspapers, mobile apps, and puzzle games—millions of solves daily. Publishers need solvers that can generate puzzles with unique solutions efficiently.

Algorithmic benchmark: Sudoku is a canonical benchmark for testing CSP solvers and SAT encodings. A well-tuned solver should solve even hard instances in milliseconds.

Education: Sudoku is familiar to a broad audience, making it an excellent vehicle for teaching backtracking, constraint propagation, and search heuristics.

---

Modeling Approaches

Approach 1: Pure CSP (Constraint Programming)

Paradigm: Declarative constraint satisfaction.

Decision variables: For each cell (i,j), a variable x[i][j] ∈ {1..9}.

Constraints:

• all_different(x[i][0], x[i][1], ..., x[i][8]) for each row i
• all_different(x[0][j], x[1][j], ..., x[8][j]) for each column j
• all_different(x[b1][b2] | (b1,b2) in box b) for each 3×3 box b
• x[i][j] = given_value[i][j] for each given cell

Strengths:

• High-level, declarative, easy to express.
• Modern CP solvers (Gecode, CP-SAT, Minizinc) have specialized global constraints (alldifferent) with powerful arc-consistency propagation.

Trade-offs:

• Requires a dedicated CP solver.
• Search space still large (9^(81 - #givens)); relies on propagation to prune.

Example Model (MiniZinc pseudo-code)

int: N = 9;
int: B = 3;  % block size

array[1..N, 1..N] of 0..N: given;  % 0 = unknown
array[1..N, 1..N] of var 1..N: x;

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

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

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

% Given cells
constraint forall(i in 1..N, j in 1..N where given[i,j] > 0) (
  x[i, j] = given[i, j]
);

solve satisfy;

Approach 2: SAT Encoding

Paradigm: Satisfiability solving.

Decision variables: Binary variables y[i][j][d] where y[i][j][d] = true iff cell (i,j) contains digit d.

Constraints (CNF clauses):

• Existence: For each cell, at least one digit is assigned: y[i][j][1] ∨ y[i][j][2] ∨ ... ∨ y[i][j][9]
• Uniqueness: For each cell, at most one digit: ¬y[i][j][d] ∨ ¬y[i][j][d'] for d < d'
• Row constraint: For each digit d, at most one occurrence per row: ¬y[i][j][d] ∨ ¬y[i][j'][d] for j < j'
• Similar for columns and boxes.

Strengths:

• Highly optimized SAT solvers (CaDiCaL, Kissat) available; can exploit recent SAT advances.
• Compact encoding once you eliminate symmetries.

Trade-offs:

• Encoding blows up the variable/clause count (81 cells × 9 digits = 729 variables).
• Loses structure of "all_different"—SAT solver must re-discover it through unit propagation.
• Less intuitive to humans; harder to tweak for problem-specific insights.

---

Key Techniques

1. Arc Consistency Propagation (AC-3 / AC variants)

Apply this repeatedly during search:

• For each cell and digit value, check if it appears as the only remaining possibility.
• Propagate: when a cell is forced to a single value, remove that value from all cells in the same row, column, and box.
• Impact: Reduces search space dramatically before branching.

2. Hidden Singles & Pairs (Sudoku-Specific Techniques)

• Hidden Single: If a digit can only go in one cell of a row/column/box, assign it immediately (stronger than AC-3 alone).
• Pointing Pairs: If a digit in a box occurs only in one row of that box, eliminate it from the rest of that row (outside the box).
• Impact: Many Sudoku instances can be solved entirely by propagation, without search.

3. Variable/Value Ordering Heuristics

• Minimum Remaining Values (MRV): Branch on the cell with fewest possible values—fails fast if infeasible.
• Least Constraining Value (LCV): Try digit values that leave the most flexibility for other cells.
• Impact: Good heuristics can reduce search tree size by orders of magnitude.

---

Challenge Corner

Q: How would you extend Sudoku to a Killer Sudoku or Sudoku with inequality constraints?

In Killer Sudoku, cells are grouped into cages with a sum constraint (e.g., a cage of 3 cells must sum to 17, with no repeated digits within the cage).

• What new decision variables or constraints would you add?
• How would propagation change? Would you need a specialized constraint for sum + all_different?

Q: Can you identify symmetries in Sudoku, and how would symmetry-breaking constraints help reduce the search space?

Sudoku has symmetries: rows can be permuted within bands, columns within stacks, digits can be relabeled. If you fix one solution, symmetry-breaking constraints rule out equivalent permutations, speeding up solver performance.

---

References

1. Gecode Documentation — Global Constraints: (www.gecode.org/redacted)
   Covers the all_different constraint and its propagation algorithms.

2. de la Banda, M.G., Stuckey, P.J. (2003). "Reasoning about Gloabl Constraints" — comprehensive survey of constraint semantics and propagation.

3. Lynce, I., Ouaknine, J. (2006). "Sudoku as a SAT Problem" — demonstrates SAT encoding with empirical comparison to CP solvers.

4. Simonis, H. (2005). "Sudoku as a Constraint Problem" — classic tutorial on modeling Sudoku in CP and highlighting propagation techniques.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 31.1K · ◷

• expires on Jun 1, 2026, 12:39 PM UTC

[github-actions[bot]]

This discussion was automatically closed because it expired on 2026-06-01T12:39:27.255Z.

Closed by Workflow