What powers Sudoku? Combinatorial counts, graph coloring, Exact Cover (DLX), difficulty metrics, uniqueness (17 clues) and symmetry.
sudoku math • combinatorics • graph coloring • exact cover (dlx) • uniqueness
Sudoku’s backbone is combinatorics. The number of valid completed 9×9 grids is about 6.67×1021. Counting proceeds via permutations of rows/columns, band/stack structure, and symmetry reduction. Practical generators first build a full solution, then remove clues while keeping the puzzle logically solvable and unique.
We model Sudoku as a constraint satisfaction problem: 81 variables with domain {1,…,9}, and all-different constraints for rows, columns, and boxes. Solvers use domain filtering, consistency (e.g., AC-3), and guided search. Human techniques—Naked/Hidden Singles, Pairs, X-Wing—are readable labels for the same logical operations.
Transform the board into a conflict graph: nodes are cells, edges connect cells sharing a row/column/box. The goal is a 9-coloring so adjacent nodes differ. The 3×3 constraint densifies the graph, which is why global patterns like X-Wing and Swordfish are powerful.
Sudoku reduces to Exact Cover: satisfy each constraint exactly once. We build a 729×324 binary matrix encoding cell-fill and row/column/box–digit constraints. DLX (Dancing Links) searches this matrix with extremely efficient backtracking and underpins many high-performance solvers.
Difficulty isn’t just “more blanks”. It’s (1) the information content of clues (average candidate entropy), and (2) the search cost—depth and variety of inference chains required. Good puzzles maintain a smooth information flow and avoid accidental bifurcations.
Quality Sudoku has a unique solution. For standard 9×9, the smallest known clue count ensuring uniqueness is 17; no classical unique example with 16 clues exists. Symmetries (rotations/reflections) add aesthetics, but must be balanced to prevent multiple solutions.
Sudoku is a playful gateway to deep ideas: combinatorics, graph coloring, CSP, and Exact Cover. Designing and solving is about shaping information flow. Put it to work now on Ozerlyn Sudoku.