Proven Sudoku

Techniques / Brute force and theory

Brute force, solvers and sudoku theory

Not techniques. How machines solve, rate and generate puzzles.

5 techniques in this family, introduced at tier 11. How to read a sudoku grid explains the notation used below.

What these have in common

Nothing here is a thing you do at the table. These are the methods and results that sit under solving. They are in the library because the line between logic and search is what this whole site is built around.

Why the logic holds

Sudoku is an exact cover problem. Each digit you write ticks off four things at once: a cell, a row, a column and a box. A full answer ticks off each one just once. Knuth's Dancing Links runs that search fast enough to crack any grid in a blink. SAT solvers do the same job a different way. None of them can say WHY the answer holds. That gap is the whole difference between solving a puzzle and just being told the end of it.

When to reach for it

Never while playing. Always while building. Every board here is checked this way before anyone sees it. That is what lets the site show a board needs no guess, rather than just say so.

How the members differ

Exact cover and SAT are two ways to write the same search. A rating engine runs a solver that may use only certain moves, then reports the hardest move it needed. That is the method behind the grading here. Unavoidable sets are the theory behind making puzzles. Such a set is a group of cells you cannot leave all blank, or the puzzle gains a second answer. The 17 clue result says no 16 clue sudoku has just one answer. It took a vast search to settle, and no short argument can show it.

The mistake to avoid

Reading a difficulty rating as fixed. An engine reports the hardest move in ONE solver's order. Other solvers use other orders. That is the whole reason a hard puzzle in one app is a medium in the next.

Start with Exact Cover and Dancing Links. A sudoku can be rewritten as a tidy tick box puzzle.

Every technique in this family