October 28, 2025
Sudoku Wars ignite
SATisfying Solutions to Difficult Problems
Sudoku cracked! SAT superfans meet MILP stans and an armchair philosopher
TLDR: A talk explains how SAT solvers crack Sudoku by turning it into a yes/no logic setup. Comments explode into a brawl: fans say MILP and linear programming win in real-world tasks, skeptics shade SAT as “just for Sudoku,” and one philosopher questions whether problems exist outside our viewpoint.
A cheerful talk on SAT solvers—tools that answer yes/no logic puzzles by turning problems like Sudoku into math—sparked a full-on comment-section cage match. The post showed how to translate Sudoku rules into a SAT formula and let a solver find the answer. The audience? Less “wow,” more “actually…”
The loudest faction crowned MILP—Mixed Integer Linear Programming, think “math constraints with a goal”—as the true unsung hero. One fan argued you can encode any SAT into MILP and it’s way better for real-world optimization, not just puzzles. Another commenter swung harder: linear programming is everywhere, while SAT “only really seems to be good at Sudoku.” Ouch. Then a puzzle purist barged in with “exact cover” techniques, claiming most human-solvable Sudokus are easy anyway. Meanwhile, a philosopher arrived to declare problems are just… how we look at them. The thread went from Sudoku grids to existential dread in three replies flat.
Between the hot takes were memes about “NP” standing for “Not Practical” and jokes that SAT solvers are the kale of computer science—technically amazing, not always delicious. Verdict: the post explains SAT beautifully, but the crowd’s split—SAT for neat reductions, MILP/LP for the messy real world, plus one commenter asking if reality itself is a constraint satisfaction problem.
Key Points
- •The article explains NP-complete problems and their mutual reducibility, highlighting SAT as a key example.
- •SAT is defined as determining if a propositional formula can be satisfied, typically represented in CNF.
- •SAT solvers are programs that find satisfying assignments to SAT instances when they exist.
- •Sudoku rules are encoded into SAT using Boolean variables per cell-digit and CNF constraints for validity.
- •Constraints enforce at least one and at most one digit per cell, and ensure digits appear once per row, column, and sub-grid, including pre-filled cells.