The Sudoku-to-SAT Reduction: How to Translate One Problem Into Another
A worked example of a polynomial-time reduction: encoding a Sudoku puzzle as a Boolean satisfiability (SAT) instance. The reduction is a mechanical translator, not a solver — a fast SAT solver automatically becomes a fast Sudoku solver, illustrating why all NP-complete problems are interchangeable.
A polynomial-time reduction converts one problem into another so mechanically that solving the second automatically solves the first. Encoding Sudoku as SAT is a clean worked example. (For why this matters across all of NP, see What a Resolution of P versus NP Would Actually Look Like and P vs NP Problem: Fundamentals Explained.) ## Step 1: Variables For a 4×4 Sudoku, create one Boolean variable for every (cell, value) pair: ``` X[row][col][value] X[1][1][1] = 'cell (1,1) contains the number 1' ``` That is 4 × 4 × 4 = 64 variables. A standard 9×9 puzzle uses 9 × 9 × 9 = 729 variables. ## Step 2: Encode the rules as clauses Each rule becomes a set of logical clauses in conjunctive normal form: - **Every cell has at least one value**: a clause OR-ing all values for that cell. - **No cell has two values**: pairwise 'not both' clauses. - **Each row, column, and box contains each number exactly once**: similar at-least-one and at-most-one constraints. ## Step 3: Add the givens A pre-filled cell becomes a one-literal (unit) clause. If cell (1,1) is the number 3, add the clause (X[1][1][3]). ## What the reduction demonstrates You did not write a Sudoku solver — you wrote a **translator**. The translation itself is simple and runs in polynomial time in the puzzle size. Crucially the encoding is *constructive*: when a SAT solver returns a satisfying assignment, you read the true X[r][c][v] variables straight back into the filled grid. The consequence is the heart of NP-completeness: **a fast SAT solver is automatically a fast Sudoku solver**. Every NP-complete problem has this relationship with every other — Sudoku → SAT → travelling salesman problem → graph coloring → back to Sudoku, in every direction. They look completely different on the surface but share one underlying structure. ## The caveat on 'the same problem' Interreducibility is about complexity class equivalence, not literal sameness. The translations can be messy and large (though still polynomial), and a reduction encodes the *problem* faithfully while telling you nothing about the *solution* until the solver actually runs. The asymmetry between an easily-described problem and a hard-to-find solution is exactly what makes NP difficult: verifying a solution is easy, finding one is hard.