🧩 Constraint Solving POTD:Problem of the Day: SAT Encoding of Sudoku

[github-actions[bot]]

Problem Statement

Sudoku as a Satisfiability Problem: Convert the classic 9×9 Sudoku puzzle into a Boolean satisfiability (SAT) formula and solve it using SAT techniques.

Concrete Instance

Consider a 9×9 Sudoku grid with some cells pre-filled. Example partial input:

5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

Input: A 9×9 grid with some fixed digits (1–9) and empty cells (blanks or '0').

Output: A completed 9×9 grid where:

• Each row contains digits 1–9 exactly once
• Each column contains digits 1–9 exactly once
• Each of the nine 3×3 boxes contains digits 1–9 exactly once
• All prefilled cells retain their values

Why It Matters

Sudoku solvers are used in puzzle generation, recreational mathematics competitions, and educational software. More importantly, Sudoku demonstrates how constraint problems map to SAT: it showcases the power of modern SAT solvers (CDCL algorithms) to handle structured combinatorial problems faster than naive backtracking.

Industrial connection: SAT techniques learned from Sudoku encoding transfer directly to hardware verification, cryptography analysis, and automated reasoning in formal methods.

---

Modeling Approaches

Approach 1: Naive SAT Encoding (Direct Variables)

Variables: For each cell (i, j) and digit d ∈ {1..9}, create a Boolean variable x[i][j][d] meaning "cell (i,j) contains digit d."

Constraints:

• Exactly-one: Each cell must contain exactly one digit:

  For each (i, j): (x[i][j][1] ∨ x[i][j][2] ∨ ... ∨ x[i][j][9]) ∧
                   (¬x[i][j][a] ∨ ¬x[i][j][b]) for all a ≠ b
  

• Row uniqueness: In each row, no digit repeats:

  For each row r and digit d: 
    at most one x[r][j][d] is true across all columns j
  

• Column uniqueness: In each column, no digit repeats (similar encoding)
• Box uniqueness: Within each 3×3 box, no digit repeats
• Pre-filled cells: For each given cell with value v:

  x[i][j][v] = true
  

Trade-offs:

• Pro: Straightforward to implement; standard CNF converters handle it well
• Con: Uses 9×9×9 = 729 variables; generates thousands of clauses; weak propagation of the "all-different" constraint

Example SAT Model (CNF-like pseudo-code)

Variables: x[i][j][d] for i,j in 1..9, d in 1..9

Clauses (CNF):
// Each cell has at least one digit
(x[0,0,1] ∨ x[0,0,2] ∨ ... ∨ x[0,0,9])
(x[0,1,1] ∨ x[0,1,2] ∨ ... ∨ x[0,1,9])
... (81 clauses)

// Each cell has at most one digit
(¬x[0,0,1] ∨ ¬x[0,0,2])
(¬x[0,0,1] ∨ ¬x[0,0,3])
... (81 * C(9,2) = 81 * 36 clauses)

// Row uniqueness: no two cells in a row share digit d
For row 0, digit 1:
  (¬x[0,0,1] ∨ ¬x[0,1,1])
  (¬x[0,0,1] ∨ ¬x[0,2,1])
  ... (9 choose 2 = 36 clauses per digit per row)

// Similarly for columns and boxes

// Fixed cells
x[0,0,5] = true    // if cell (0,0) is given as 5

Approach 2: Encoding with Cardinality Constraints (Improved SAT)

Variables: Same as Approach 1, but use specialized cardinality encoding.

Constraints:

• Exactly-one: Use a cardinality constraint (e.g., networks like Sorters or Totalizers):

  For each (i, j): Σ_d x[i][j][d] = 1
  

  This compiles to ~9 clauses per cell instead of quadratic pairwise clauses.

• Row/column/box uniqueness: Similarly use cardinality:

  For each row r and digit d: Σ_j x[r][j][d] ≤ 1
  

Trade-offs:

• Pro: Fewer clauses overall; enables unit propagation much earlier; modern SAT solvers exploit this
• Con: Slightly more complex encoding logic; requires cardinality compiler

Approach 3: Hybrid Constraint Programming (Not Pure SAT)

For reference, a CP model uses:

Variables: cells[i][j] ∈ {1..9}
Constraints: 
  all_different(row_i) for each row i
  all_different(col_j) for each column j
  all_different(box_k) for each 3×3 box k
  cells[i][j] = v_ij for each given cell

CP solvers propagate all_different globally, achieving bounds consistency in one operation. SAT must encode this explicitly.

---

Key Techniques

1. Unit Propagation & Conflict-Driven Clause Learning (CDCL)

SAT solvers like MiniSat and CaDiCaL use CDCL to:

• Propagate: Fix variables forced by unit clauses
• Learn: When a conflict arises, extract a new clause to avoid the same conflict
• Backtrack: Jump to the most recent decision that caused the conflict

For Sudoku, CDCL is remarkably effective because:

• The row/column/box constraints are highly redundant, generating useful learned clauses
• Each digit placement immediately triggers new implications

2. Preprocessing & Symmetry Breaking

Sudoku has symmetries: permuting rows within a band, columns within a stack, relabeling digits. A SAT preprocessor can:

• Add implied constraints (e.g., if digit 5 must appear in row 1, exclude it from other candidates early)
• Remove variables that don't affect satisfiability
• Detect and break symmetries explicitly to reduce search space

3. Heuristic Variable Selection

SAT solvers choose which variable to branch on using:

• VSIDS (Variable State Independent Decaying Sum): Prioritize frequently appearing variables
• Lexicographic: Simple but sometimes effective for structured problems
• Activity-based: Track which variables lead to quick conflicts

For Sudoku, a cell with fewer candidate digits (more constrained) should be branched first.

---

Challenge Corner

Extend & Explore:

1. Smaller Variants: How does SAT performance compare to CP on 4×4 Sudoku (using digits 1–4 and 2×2 boxes)?

2. Symmetry Breaking: Sudoku has symmetry under permutation of digits. Can you add explicit clauses that break this symmetry (e.g., "cell (0,0) = 1") without losing solutions?

3. Sampling & Counting: Instead of finding one solution, how would you modify the SAT encoding to count all valid Sudoku completions for a given puzzle? (Hint: use SAT-counting techniques.)

4. Uncertain Clues: What if some givens are unreliable? How could you encode a maximum satisfiability (MaxSAT) variant to find a solution that respects as many clues as possible?

---

References

1. Eén, N., & Sörensson, N. (2003). "An Extensible SAT-solver." In SAT 2003, pp. 502–518.

   • Describes MiniSat, the canonical CDCL solver; reference implementation for many techniques.

2. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Elsevier.

   • Chapter 4 covers SAT and encoding combinatorial problems; Section 4.1 gives Sudoku as a case study.

3. Järvisalo, M., Heule, M., & Biere, A. (2012). "Inprocessing Rules." In SAT 2012, pp. 405–416.

   • Modern preprocessing techniques that simplify Sudoku encodings.

4. Norvig, P. (2006). "Solving Every Sudoku Puzzle." Blog post.

   • Practical guide using backtracking and constraint propagation; shows why SAT can compete.

---

This problem demonstrates how to transform a visual puzzle into a logical formula. SAT solvers' strength at finding satisfying assignments makes them ideal for Sudoku, outperforming naive backtracking on larger or harder instances. Understanding this encoding is a gateway to industrial applications of SAT in verification and cryptanalysis.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 8.07 AIC · ⌖ 5.76 AIC · ⊞ 6K · ◷

• expires on Oct 7, 2026, 3:34 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 #64749.