How Computers Solve Sudoku

Computers can solve ordinary 9×9 Sudoku extremely quickly, but there is no single “Sudoku algorithm.” Different solvers are built for different jobs.

A complete solver tries to determine whether a puzzle has zero, one, or multiple solutions.

A human-style solver tries to explain the puzzle using named logical techniques in a useful order.

A generator, validator and difficulty rater may use both.

Sudoku as a constraint problem

For every cell, the program tracks a domain of possible digits.

Constraints require:

• one digit per cell;
• each digit once per row;
• each digit once per column;
• each digit once per box.

When a value is fixed, incompatible values can be removed elsewhere. This is constraint propagation — the computational analogue of updating candidates after a human placement.

Candidate propagation

A simple solver can repeatedly:

1. calculate legal candidates;
2. place forced cells;
3. remove candidates blocked by new placements;
4. repeat until no direct progress remains.

This solves easy puzzles but not every valid Sudoku.

A complete solver needs a way to explore alternatives when propagation alone stops.

Backtracking

Backtracking is one of the simplest complete approaches.

1. choose an unsolved cell;
2. try one legal candidate;
3. propagate constraints;
4. if a contradiction appears, undo the choice;
5. try another candidate;
6. continue until a complete grid is found or all alternatives fail.

Good implementations choose a highly constrained cell first to reduce branching.

Backtracking is not the same as how VeyraPlay teaches a human to solve. It is an efficient search method for a machine.

Solution counting

To validate uniqueness, a solver should not stop merely because it found one solution.

It can continue searching until:

• no solution exists;
• exactly one solution is proven;
• or a second solution is found, which is enough to prove non-uniqueness.

This is fundamental for generation and uniqueness-technique safety.

Sudoku as exact cover

Classic 9×9 Sudoku can be encoded as an exact cover problem.

There are four families of requirements:

• 81 cell constraints: each cell receives one value;
• 81 row-digit constraints;
• 81 column-digit constraints;
• 81 box-digit constraints.

Total:

81 × 4 = 324 constraints

There are 729 possible row/column/digit assignments:

9 × 9 × 9 = 729 candidate placements

Each placement satisfies exactly four relevant constraints.

The task becomes selecting assignment rows that cover each constraint exactly once.

Algorithm X

Donald Knuth's Algorithm X is a recursive method for solving exact-cover problems.

At each stage it:

1. chooses an uncovered constraint;
2. selects a candidate row satisfying it;
3. covers conflicting constraints/rows;
4. recurses;
5. backtracks if needed.

The same method can find one Sudoku solution or enumerate enough solutions to test uniqueness.

Dancing Links (DLX)

Dancing Links is an efficient data structure/implementation technique for Algorithm X on sparse matrices.

Sudoku's 729×324 exact-cover matrix is sparse: each candidate placement touches only four constraints.

DLX makes covering and uncovering those sparse relationships efficient during recursive search.

Algorithm X is the search idea; Dancing Links is a famous implementation technique for it.

Constraint programming and SAT-style models

Sudoku can also be expressed to general-purpose solving systems:

• constraint satisfaction (CSP/CP);
• SAT/Boolean encodings;
• integer programming;
• graph or exact-cover representations.

The best representation depends on whether you need speed, explanation, counting, extensibility to variants, or research analysis.

Human-style solvers

A human-style solver searches for named deductions such as:

• Singles;
• Locked Candidates;
• subsets;
• Fish;
• Wings;
• Coloring;
• Chains;
• ALS.

Instead of asking only “can I find a solution?”, it records a solution path.

That path can be used for:

• hints;
• tutorials;
• difficulty rating;
• generator quality filters;
• identifying which technique unlocks a puzzle.

Why complete and human-style solvers should be separate

A puzzle can be easy for backtracking and hard for a human.

Machine search cost does not map directly to recognition difficulty.

A robust Sudoku platform can therefore use:

• complete solver → validity and solution count;
• human solver → explanation and rating;
• generator → candidate puzzle creation;
• analyzer → metadata and quality checks.

How a generator uses solvers

When clues are removed from a solution grid, a complete solver tests whether uniqueness survives.

Then a human-style solver can ask:

• is the puzzle logically solvable with the allowed technique set?
• which hardest technique is required?
• how many steps are needed?
• where are the bottlenecks?
• does the intended technique actually appear in the solution path?

This is why “generate a Sudoku” is much more than “delete random digits.”

Do computers guess?

Search algorithms explore alternatives, but “guess” is not a very useful technical description.

A complete backtracking solver systematically enumerates a finite search space with constraint pruning and proof through exhaustion.

A human Guide about guessing is concerned with whether the player is making unsupported commitments while solving. Those are different contexts.

FAQ

What is the fastest algorithm for Sudoku?

There is no universal answer. For 9×9 puzzles, optimized backtracking, exact-cover/DLX and constraint solvers are all extremely fast. Choice depends on the task and implementation.

What are the 324 exact-cover constraints?

81 cell constraints plus 81 row-digit, 81 column-digit and 81 box-digit constraints.

Why are there 729 candidate rows?

There are 9 rows × 9 columns × 9 possible digits, one row for each possible placement.

Is Algorithm X the same as Dancing Links?

No. Algorithm X is the recursive exact-cover algorithm; Dancing Links is a data structure technique often used to implement its cover/uncover operations efficiently.

Do human Sudoku solvers use backtracking?

Human-style logical solvers usually try to avoid it because the goal is an explainable deduction path. Complete validators commonly use search.

What to learn next

Read Generation for how validators and human solvers fit a puzzle pipeline, or Create a Sudoku Puzzle for the practical construction process.