Sudoku Solver

What This Tool Does

This tool accepts a standard 9x9 Sudoku puzzle pasted or typed into the grid and returns the unique solution, along with a rough difficulty rating based on the number of clues and the constraint-propagation depth required. Empty cells are filled by a recursive backtracking solver augmented with naked-single propagation, so straightforward puzzles complete almost instantly while harder puzzles still finish in well under a second.

You can paste an existing puzzle, type clues one cell at a time using arrow-key navigation, or click Generate to create a fresh easy, medium, or hard puzzle on demand. Three modes are available: Solve runs the full solver and animates the fill, Validate highlights any conflicting cells without solving, and Generate produces a new uniqueness-checked puzzle at the selected difficulty.

Every computation runs entirely in your browser. No puzzle you enter is ever uploaded, logged, or persisted anywhere outside your local session. The difficulty rating uses clue count plus backtrack count as a proxy for human-perceived difficulty - puzzles requiring more backtracks are harder for the algorithm and typically harder for human solvers as well.

How to Use It

The interface is built around the 9x9 grid in the center. Click any cell to focus it; type a digit 1-9 to set a clue; press Backspace or Delete to clear a cell. Arrow keys move the focus between adjacent cells, so you can enter an entire puzzle without leaving the keyboard. Non-digit characters and zeros are silently filtered out by the input handler.

The three mode chips at the top of the tool switch behavior. Leave it on Solve (the default) to run the solver. Switch to Validate if you want to check a partial puzzle for rule violations - any cell that shares a row, column, or 3x3 box with a duplicate digit is highlighted in red. Switch to Generate, choose Easy, Medium, or Hard, and click Generate to produce a fresh puzzle with the appropriate clue density.

The Example button loads a classic moderate puzzle so you can see the solver in action without typing anything. The Clear button wipes the grid back to empty. Once a solve completes, the status bar reports the wall-clock time in milliseconds and the number of backtracks the algorithm performed - both useful indicators of puzzle difficulty.

Worked Example: A 30-Clue Moderate Puzzle

The example below is the canonical "moderate" Sudoku used in countless newspaper columns. It contains 30 given clues - five more than the symmetry-balanced 25 floor that defines the boundary between "hard" and "expert" classes - and can be solved by a human using only naked singles and hidden singles, no advanced techniques required.

Starting position (30 clues):

5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

The solver's first action is constraint propagation. It scans every empty cell and computes the set of candidate digits that don't conflict with the cell's row, column, or 3x3 box. Several cells will have exactly one candidate immediately - these are "naked singles" and get filled at once. The cell at row 1, column 3 (currently empty) has candidates {1, 2, 4} because 3, 5, 7, 8, 9 are blocked by the row and column; further propagation narrows this to {1, 4} after the top-right box constraints are applied.

After the first naked-single sweep places 8-12 digits, the solver re-scans for newly created naked singles. This loop continues until no more singles emerge. At that point - usually after 15-20 propagation rounds for a moderate puzzle - it switches to backtracking: it picks the empty cell with the fewest remaining candidates, tries each candidate in turn, and recurses. The figure below shows the grid mid-solve with one constraint highlighted.

Final solution: 5 3 4 | 6 7 8 | 9 1 2 / 6 7 2 | 1 9 5 | 3 4 8 / 1 9 8 | 3 4 2 | 5 6 7 / 8 5 9 | 7 6 1 | 4 2 3 / 4 2 6 | 8 5 3 | 7 9 1 / 7 1 3 | 9 2 4 | 8 5 6 / 9 6 1 | 5 3 7 | 2 8 4 / 2 8 7 | 4 1 9 | 6 3 5 / 3 4 5 | 2 8 6 | 1 7 9. On a modern laptop, this solve completes in approximately 0.4 ms with 7-15 backtracks.

Common Use Cases

Newspaper Puzzle Verification

Print Sudoku puzzles occasionally contain typesetting errors - a clue mis-rendered as 3 instead of 8, or a duplicate digit slipping past the editor. Paste the printed puzzle into the solver and either it returns a unique solution (the puzzle is well-formed) or it returns "no solution" or "multiple solutions" (something is wrong). This is the fastest way to confirm whether a puzzle is solvable before committing 20 minutes to working it by hand.

Puzzle-Design Verification

Anyone hand-crafting Sudoku puzzles - for a school newsletter, a puzzle book, a holiday card - needs to confirm that the puzzle has exactly one solution. Two solutions means the puzzle is ambiguous and unfair to solvers. Zero solutions means a clue contradicts another clue. Run the design through this tool before publication. For full design-grade verification you'd want a uniqueness checker (the solver here returns the first solution it finds), but this tool catches most common design mistakes immediately.

Learning Solving Techniques

Solving by hand is more rewarding than letting the computer do it - but when you're stuck on a single cell after 45 minutes, the solver gives you the answer without spoiling the rest. Use it as a hint engine: enter your partial progress, solve, then compare the solved board against your work to find the cell you were missing. The status bar's backtrack count also gives you a rough difficulty signal - puzzles requiring fewer backtracks were solvable by pure constraint propagation, which means they were within reach for naked-singles and hidden-singles techniques.

Programming Puzzle Education

Computer science instructors use Sudoku as the canonical example for teaching backtracking, recursion, and constraint satisfaction. The solver's source code is short (under 100 lines for the core algorithm) and easy to inspect via View Source. Students can compare their own backtracking implementations against this one for correctness, or use it as a reference when their own solver loops forever on a difficult puzzle. The algorithm is also a stepping stone to teaching SAT solving, exact cover, and other constraint-satisfaction techniques.

Edge Cases and Limitations

Multiple-solution puzzles are not proper Sudoku. A well-formed Sudoku puzzle has exactly one solution. If your puzzle has two or more, it's technically not a Sudoku - it's an under-constrained logic puzzle. The solver returns the first solution it finds without flagging ambiguity. To check uniqueness, you'd need to run the solver twice with different cell ordering and compare results. Most newspaper and app puzzles are uniqueness-verified before publication; hand-built puzzles often need one or two additional clues to eliminate alternate solutions.

No-clue puzzles (blank grids) have 6.67 x 10^21 solutions. An empty 9x9 grid has roughly 6,670,903,752,021,072,936,960 valid completions according to a 2005 computer enumeration by Felgenhauer and Jarvis. The solver will return the first one it finds, which is essentially random based on the search order. If you actually want a fresh puzzle, use the Generate button instead - it builds a full solution first, then strategically removes cells to create a clue set.

Sudoku variants are not supported. Killer Sudoku (cage sums), Arrow Sudoku (arrow constraints), Jigsaw/Squiggly (irregular regions), Samurai (5 overlapping grids), Greater-Than Sudoku, and Anti-Knight Sudoku each add constraints beyond the row/column/box trio. The solver only enforces the classic 9x9 ruleset. For variant puzzles you'll need a specialized solver - SudokuWiki and the Penpa+ editor both support multiple variant types.

Expert puzzles with fewer than 22 clues may need advanced techniques. Below 22 clues, puzzles often require X-Wing, Swordfish, XY-Wing, Coloring, or Forcing Chains to crack by hand - the solver's pure backtracking handles them but takes more time and produces a high backtrack count. The status bar's backtrack number is your hint that the puzzle required deep search rather than straightforward propagation.

The 17-clue minimum is rigorously proven. In 2012, McGuire, Tugemann, and Civario published the proof that 17 is the minimum number of clues a Sudoku puzzle can have while still possessing a unique solution. They exhaustively searched all 5.47 billion essentially different completed Sudoku grids and confirmed no 16-clue puzzle with a unique solution exists. So if your "minimalist" puzzle has 16 clues, it has at least two solutions - guaranteed.

Behind the Algorithm

Constraint Propagation Plus Backtracking

The solver runs two passes in alternation. The first pass is constraint propagation: for each empty cell, compute the set of candidate digits not already present in its row, column, or 3x3 box. Any cell with exactly one candidate (a "naked single") gets filled immediately, which in turn shrinks the candidate sets for cells in its row, column, and box. The pass loops until no more naked singles emerge. For easy and most medium puzzles, this single technique solves the entire grid without any search.

When propagation stops short of a complete solution, the second pass kicks in: backtracking. The solver picks the empty cell with the fewest remaining candidates (the most-constrained-variable heuristic, which dramatically prunes the search tree), tries each candidate in turn, and recursively re-runs propagation plus backtracking on the resulting state. If a branch reaches a contradiction (some cell ends up with zero candidates), it undoes the last placement and tries the next candidate.

Dancing Links and Algorithm X

Donald Knuth published the Dancing Links paper in 2000, introducing an elegant implementation of Algorithm X for solving exact-cover problems. Sudoku reduces neatly to exact cover: every row, column, box, and cell position must be "covered" exactly once by a digit placement. DLX uses doubly-linked lists where removing and restoring a node are both O(1) operations - exactly what backtracking needs. A well-tuned DLX Sudoku solver finishes the world's hardest puzzles in microseconds.

Why Pure Backtracking Is O(9^81) but Sub-Second in Practice

The theoretical worst case for naive backtracking on a Sudoku grid is 9 candidates per cell across 81 cells, or 9^81 - an astronomically large number (around 1.97 x 10^77). In practice the solver finishes in well under a second on the hardest known puzzles because pruning eliminates almost the entire search tree. Constraint propagation reduces most candidate sets from 9 to 2-3 before backtracking even starts, and the most-constrained-variable heuristic ensures the algorithm spends its time on cells with few options rather than cells with many options.

The SAT-Solver Alternative

Sudoku also reduces to Boolean satisfiability: encode each "digit d in cell (r,c)" as a Boolean variable and add CNF clauses for the row/column/box uniqueness rules. A modern SAT solver like MiniSat or Glucose then solves it in milliseconds using conflict-driven clause learning (CDCL). This approach scales beautifully to Sudoku variants - just add more clauses for the killer-sums, arrows, or thermos. The downside is encoding overhead: a 9x9 Sudoku produces around 11,000 CNF clauses, more than constraint propagation handles directly.

Comparison: This Tool vs. Other Sudoku Solvers

Several established Sudoku solvers occupy different niches, and choosing the right one depends on whether you want speed, explainability, or variant support.

SudokuWiki Solver (sudokuwiki.org) is the gold standard for teaching solving techniques. It steps through each technique it applies - naked pairs, hidden triples, X-Wing, swordfish, XY-Wing, coloring - and shows you which cells each technique eliminates. Use it when you want to learn how to solve harder puzzles by hand rather than just see the answer. Its solver is slower than DLX-based tools but the explainability is unmatched.

Hodoku (hodoku.sourceforge.net) is a downloadable Java application that covers an even broader technique catalog than SudokuWiki, including obscure chain methods like AIC (Alternating Inference Chains) and exotic patterns like Unique Rectangles. Hodoku also generates puzzles tuned to specific technique requirements - useful if you want to practice a particular method. It's the power-user choice but requires installing Java.

Bart Massey's sudoku solver is a classic Haskell implementation that demonstrates constraint propagation in a functional-programming style. It's not interactive and not built for end users - it's a reference implementation cited heavily in academic literature on constraint satisfaction. Read its source if you're interested in seeing Sudoku solving expressed declaratively.

This tool sits in a different niche: zero install, zero account, browser-only, optimized for the common cases of "I need this puzzle solved right now" and "I need to verify this generated puzzle is valid." It deliberately doesn't try to compete with SudokuWiki on explainability or with Hodoku on technique breadth - it just gives you the answer and the difficulty signal in well under a second, with no ads near the input grid and no data leaving your device.