🧩 Constraint Solving POTD:Problem of the Day: Sudoku

[github-actions[bot]]

Problem Statement

Sudoku is played on a 9×9 grid partitioned into nine 3×3 boxes. Some cells are pre-filled with digits 1–9 (the clues). Fill every empty cell so that each row, each column, and each box contains every digit exactly once.

Small instance (a 4×4 "mini-Sudoku" with 2×2 boxes, digits 1–4). This puzzle has exactly one solution:

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

Unique solution:

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

Input: a partially filled grid. Output: a completed grid satisfying all row, column, and box constraints, or a proof that none exists.

As a constraint problem:

• Variables: x[r,c] ∈ {1..9} for each cell
• Constraints: alldifferent over each row, each column, and each box (27 constraints total)
• Givens: x[r,c] = v for each clue

Why It Matters

• Verification of hardware and software configurations: many real problems reduce to "fill a grid of finite-domain variables under all-different rules", such as assigning frequencies, timeslots, or register slots.
• Latin-square-style experiment design: row/column balance constraints in agricultural and clinical trials are structurally identical to Sudoku's row and column rules.
• Benchmark for solver technology: Sudoku is a standard teaching and testing problem for propagation and SAT solvers, and hard instances are used to compare solver heuristics.

Modeling Approaches

1. Constraint Programming (finite-domain)

• Variables: x[r,c] ∈ {1..9}
• Constraints: alldifferent(row r), alldifferent(col c), alldifferent(box b)
• Strength: the alldifferent global constraint has dedicated propagators (Régin's matching-based filtering), which remove values that cannot appear in any solution. This is much stronger than pairwise ≠ constraints.
• Trade-off: compact and readable. Propagation can stall on hard puzzles, so search with backtracking or restarts is still needed.

2. SAT (Boolean encoding)

• Variables: p[r,c,v] ∈ {0,1}, true iff cell (r,c) holds digit v (729 Booleans)
• Constraints:
  • Exactly-one per cell: at-least-one clause plus at-most-one pairwise clauses
  • At-most-one per (row, digit), (column, digit), and (box, digit)
  • Unit clauses for the givens
• Strength: unit propagation plus conflict-driven clause learning (CDCL) solves most puzzles in milliseconds, even hard ones.
• Trade-off: the encoding is larger and less readable, but it scales well and uses mature solvers.

Example Model (MiniZinc, CP)

include "alldifferent.mzn";

int: n = 9;
array[1..n, 1..n] of 0..9: givens;   % 0 = empty cell
array[1..n, 1..n] of var 1..n: x;

constraint forall(r, c in 1..n where givens[r,c] > 0)(x[r,c] = givens[r,c]);
constraint forall(r in 1..n)(alldifferent([x[r,c] | c in 1..n]));
constraint forall(c in 1..n)(alldifferent([x[r,c] | r in 1..n]));
constraint forall(br in 0..2, bc in 0..2)(
  alldifferent([x[3*br+i, 3*bc+j] | i, j in 1..3])
);

solve :: int_search(array1d(x), first_fail, indomain_min, complete) satisfy;

Key Techniques

Global alldifferent propagation

Naked singles (a cell with one remaining candidate) and hidden singles (a digit with one possible cell in a unit) are both special cases of Hall-set reasoning. A Hall set of size k is a set of k variables whose domains together contain only k values, so those values can be removed from every other variable. Propagators such as Régin's algorithm find these sets in polynomial time.

Search heuristics

Use minimum remaining values (MRV) or first-fail: branch on the empty cell with the fewest candidates. This keeps the search tree small and makes propagation more effective.

Exact cover and Dancing Links

Sudoku is an instance of exact cover: choose rows of a 0/1 matrix so that every column is covered exactly once. Knuth's Algorithm X with the Dancing Links data structure solves this with very fast backtracking, and it is a good alternative to a general solver for pure Sudoku.

Challenge Corner

1. Uniqueness: a well-designed puzzle has exactly one solution. How would you check uniqueness efficiently? Hint: solve once, add a clause or constraint that forbids the found solution, and solve again.
2. Minimal clues: what is the smallest number of clues that still yields a unique solution? This is an open-ended question. Known results say 17 clues is the minimum for a unique 9×9 puzzle.
3. Symmetry breaking: the grid has many symmetries, including digit relabelings and band/stack/row/column permutations. How would you add lex-ordering constraints so the solver does not explore equivalent solutions? Try it with a CP or SAT model and measure the speedup on hard puzzles.
4. Counting: the number of valid completed 9×9 grids is 6,670,903,752,021,072,936,960. Can you count solutions for a partial grid with a constraint solver, and how does the count change when you remove a clue?

References

• Rossi, van Beek & Walsh (eds.), Handbook of Constraint Programming, Elsevier, 2006. Chapter on global constraints, which covers alldifferent.
• Knuth, D. E., "Dancing Links", Millennial Perspectives in Computer Science, 2000 (arXiv: cs/0011047). Exact cover and Algorithm X.
• Biere, Heule, van Maaren & Walsh (eds.), Handbook of Satisfiability, IOS Press, 2009. Covers SAT encodings and CDCL solving.
• Régin, J.-C., "A Filtering Algorithm for Constraints of Difference in CSPs", AAAI-94. The matching-based alldifferent propagator.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · routed: haiku55 high · ~2 AIC · ⌖ ~2 AIC · ⊞ 4.1K · ◷

• expires on Nov 19, 2026, 3:33 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 #77423.