A Sudoku solver takes the digits sitting on your grid and hands back the completed one. If it hands back nothing, that is the more useful answer. It means the digits you have written no longer fit together, so one of them is wrong.
Two things it will not do. It will not tell you which move to make next, and it will not tell you which of your digits was the bad one. Almost every solver returns an answer rather than a reason.
Inside, a solver is two ideas stacked. The first works the way you do: take a cell, cross off every digit its twenty peers already use, and write down the survivor. The second is nothing like you. Pick a cell, write any digit that fits, carry on as though it were true, and unwind the moment the grid contradicts itself. How much of each a program uses decides whether it finishes in a millisecond or grinds for a minute, and this page measures exactly that on two real grids.
Solving a printed grid? Sudoku Master reads a newspaper puzzle through the phone camera and returns the finished grid, or nothing at all. Free, works with no signal, and the photo stays on the device.
What a solver can answer
| You ask | What you get back |
|---|---|
| Finish this grid | The completed grid, in well under a second |
| Is my grid still legal? | Yes or no. A solver that returns nothing has told you no |
| Which digit did I get wrong? | Nothing. It sees a contradiction, not your history |
| What move would a person make next? | Nothing, from most solvers. An answer is not a technique |
| Does this puzzle have exactly one solution? | Only if it keeps searching after the first answer. Most stop |
| Why is this one so hard? | Nothing useful. Hard for you and hard for a search are different things |
Rows three and five are where people get caught. A solver knows the grid is broken and has no idea who broke it, and it will happily finish a puzzle that has fifty other endings without mentioning them.
The grid this page uses
Twenty-six givens, which is a normal hard.
. . 1 9 . . 4 . .
. 8 4 . . . 6 2 .
7 . . . . 5 . . .
8 . 9 7 1 . . . 3
. . . . . 2 1 9 .
. 3 . . . . . . .
. . 2 4 . . 8 . .
. . . . . . . 7 .
3 1 8 . . . . . 4
r4c5 means row 4, column 5, counting rows downward and columns rightward from
the top left corner. That is the 1 sitting in the middle of box 5. Cross-hatching and singles place 25 digits into this
grid and then stop dead:
2 5 1 9 . . 4 3 7
9 8 4 . . . 6 2 5
7 6 3 2 4 5 9 . .
8 2 9 7 1 . 5 . 3
. 4 7 . . 2 1 9 .
1 3 . . . . 7 . 2
. 7 2 4 . . 8 . 9
4 9 . . 2 . 3 7 .
3 1 8 . . . 2 . 4
Thirty blanks. Row 1 is missing a 6 and an 8 across r1c5 and r1c6. Column 1
is missing a 5 and a 6 across r5c1 and r7c1. The grid is full of cells with
exactly two candidates and not one of them will settle.
A person's next move here is a hard one. I ran naked and hidden pairs, triples and quads over the stalled grid, then pointing pairs, box-line reduction and a full X-Wing search. Between them they crossed off a handful of candidates and placed nothing at all. This grid wants a chain.
A brute-force solver does not know that, and does not need to.
Guess, check, unwind
Backtracking is four instructions long, and it is the whole of most solvers.
- Find an empty cell.
- List the digits that its row, column and box do not already use.
- Write the first one and move to the next empty cell.
- If a cell runs out of legal digits, rub out the last digit you wrote, and try the next one on that cell's list instead. If that cell is exhausted too, step back again.
It cannot fail to terminate and it cannot get the answer wrong, because it only ever writes digits that are legal at the moment of writing and it never stops until the grid is full. What it can do is take a very long time.
Here is the count on the grid above. A solver that just walks the empty cells left to right, top to bottom, wrote 2,144 digits to fill 55 blanks. That means 2,089 of them came back out again.
Now change one line of it. Instead of taking the next empty cell, take the empty cell with the fewest legal digits left. Same algorithm, same guesses allowed, one different choice of where to guess:
| Version | Digits written | Digits rubbed out |
|---|---|---|
| Next empty cell, left to right | 2,144 | 2,089 |
| Emptiest cell first | 64 | 9 |
| Emptiest cell, singles run to exhaustion first | 66 | 11 |
The third row is what a good solver actually does, and at first glance it looks like a step backwards. Before each guess it runs the human part: naked singles, hidden singles, cross off what the peers use, repeat until nothing moves. Two more placements, not fewer.
Count the guesses instead and the picture inverts. The second version branches at six cells and picks wrong at three of them. The third branches at two and picks wrong at one. That 30-cell stall, the one that beat every technique up to the X-Wing, cost a solver exactly two guesses.
Which is the honest shape of the thing. Mostly logic, with a little guessing to cover what the logic misses, and the logic is the part that decides how much guessing there has to be.
Seventeen clues that need no guessing at all
A properly made puzzle has exactly one solution, and 17 is the fewest clues that can carry one. McGuire, Tugemann and Civario settled that in 2012 by running out of places to look: every arrangement of 16 clues was checked, none had a single answer. So a sixteen-clue puzzle is not a rare and difficult thing. There are none.
Here is a 17-clue grid.
. . . . . . . . .
. . . . . 3 . 8 5
. . 1 . 2 . . . .
. . . 5 . 7 . . .
. . 4 . . . 1 . .
. 9 . . . . . . .
5 . . . . . . 7 3
. . 2 . 1 . . . .
. . . . 4 . . . 9
Nine clues fewer than the last one, and an entirely empty top row. Left-to-right backtracking was still running on it after three million placements, so I stopped it. The emptiest-cell version got there in 58,233. And the version that crosses off candidates first placed all 64 missing digits without a single guess: plain scanning and singles finish this puzzle from the first move to the last.
So the sparse grid is easy and the crowded one is hard, which is worth sitting with for a second. Clue count is not difficulty. What sets difficulty is the hardest technique the grid forces on you, and how often it forces it, which is the same for a person as it is for a program. More on that in what makes a Sudoku easy, medium, hard or extreme, and the minimum-clue result has its own page in seventeen clues.
Why this is easy for a computer and hard for you
Not because the computer is cleverer. Because undo is free.
When the program writes a 6 in a cell, it is not committing to anything. If the grid dies forty cells later, it walks back, and it walks back to exactly the right place, having lost nothing. You cannot do that on newsprint with a biro. One wrong digit costs you the puzzle, or twenty minutes of rebuilding, which is why the whole human craft is built around never writing a digit you cannot justify.
Which answers the question from the other side: can a grid be hard enough to beat the solver? No. Nine rows and nine columns is a small, finite thing, and the worst grid anyone prints is still a few tens of thousands of placements. You will read that Sudoku is NP-complete, and it is, but the proof (Yato and Seta, 2003) is about boards of any size you like. Your morning puzzle is not one of those.
When reaching for one is the right call
| Situation | Solver? |
|---|---|
| You finished the grid and want it checked | Yes. This is the cheapest use there is |
| Something contradicts and you cannot find where | Yes, and see the method below |
| You suspect the puzzle itself is broken | Yes, if the solver counts solutions rather than stopping at one |
| The paper prints the answer tomorrow and you want it now | Yes |
| You are stuck and still want to solve it | No. You want a hint or a checklist, not the answer |
| You want to learn the technique the grid needs | No. A solver teaches nothing, by design |
| You are timing yourself | No, obviously, but people do ask |
The line runs between checking and playing. A solver is a very good referee and a terrible teacher. If you are stuck rather than wrong, work the stuck checklist first, and if you do want help mid-puzzle, a hint has to be spent carefully or the rest of the grid falls apart on its own.
Use it to find the mistake, not the answer
This is the use worth learning, because it gets you unstuck without showing you a single digit you had not earned.
Say you wrote a 6 into r1c5 on the grid above. It was legal when you wrote it.
Nothing in row 1, column 5 or box 2 holds a 6, the cell genuinely reads {6,8},
and you can carry on placing digits for a long time before anything complains.
Feed that grid to a solver and it returns nothing. There is no answer, and the
6 is why.
The message "no solution" is worth more than it looks. It tells you the error already exists, so you can stop hunting forward and start hunting backward. Then narrow it:
- Type in the givens only. The solver returns the true grid. Do not read it.
- Type in the givens plus half the digits you added. If it still solves, your error is in the other half.
- Halve again. Five or six rounds of this on a 30-cell fill and you are down to one cell.
You end up knowing which digit was wrong and nothing else, which leaves the rest of the puzzle intact for you to finish. That beats reading the answer, and it beats starting over.
The puzzle with 59 answers
Take the grid at the top of this page and rub out one clue: the 4 in r1c7.
That single change turns it into a puzzle with 59 different valid completions.
Hand that to a solver and it hands back one of the 59, with no warning, looking exactly like a real answer. Both of you would be right and you would still disagree, which is the thing to remember before you argue with an app about a puzzle you got out of a free printable.
To know a puzzle is properly made, a solver has to carry on searching after it finds the first solution and see whether a second one exists. That costs real time and most solvers do not bother, including mine.
The reverse case is on the same grid. Rub out the 1 at r4c5 instead and the
puzzle still has exactly one solution, because that clue was doing no work. A
puzzle can carry passengers. Clue count really is a poor guide to anything.
What to check before you trust one
Six checks, and you can run all of them in a couple of minutes.
| Check | How | Why |
|---|---|---|
| It refuses an illegal grid | Type the same digit twice into one row | If it "solves" that, it is not checking |
| It says no solution out loud | Feed it a grid with one wrong digit | Silence or a spinner is a bad sign |
| It works offline | Flight mode, then solve | A grid does not need a server |
| The photo stays on your phone | The privacy label, and whether scanning works offline | An uploaded photo is a choice, and you should make it knowingly |
| You can correct a misread digit | Scan anything and look for an editable grid | Recognition gets digits wrong. Always |
| It is honest about what it returns | Look for a claim to explain moves | An answer and an explanation are different products |
The scanning ones matter more than they sound, because most solver failures on a photographed puzzle are not solver failures. They are reading failures: 1 read as 7, 6 read as 5, 8 read as 3. When a scanned grid comes back with no solution, suspect the read before you suspect your own solving, and go and look at what the app thinks is on the page. There is more on that in solving a Sudoku from a photo.
What I built, and where it stops
I built Sudoku Master. Its solver is the plain kind this page has been describing. Legality check, search, then either the finished grid or nothing. No narration of a technique, and no finger pointed at the cell you got wrong. Better you read that here than discover it halfway through a stuck puzzle.
The scanning half is where the work went. Google ML Kit does the reading, on the phone, so nothing about the picture goes to a server. A folded newspaper defeats that often enough that the read is treated as a draft: it lands in an editor where any digit can be tapped and changed, and typing the grid by hand is a screen away when the photo is hopeless. Old scans stay in a list, so last Sunday's puzzle is still there. The 4,000 classic puzzles are compiled into the binary rather than fetched, which is the whole reason none of it needs a signal or an account.
Common mistakes
Treating "no solution" as a bug. It is the most informative thing a solver ever says. Something on your grid is wrong, and now you know it before you spend another hour.
Reading the whole answer to fix one cell. The halving method above finds the bad digit without spoiling the other twenty-nine.
Assuming the answer it gives is the answer. On an improper puzzle there are several, and the solver picks one without telling you.
Expecting it to explain. Backtracking has no reasoning to report. The sequence it took would read as nonsense to a person, because most of it was undone.
Blaming the solver for a bad scan. Check the digits it read before you check anything else.
Using one because you are stuck. Stuck and wrong are different states. Run the legality tests first, then the technique ladder, and keep the solver for when you actually need a referee.
Questions people ask
Is using a Sudoku solver cheating?
There is nobody to cheat. The question people are really asking is whether it costs them anything, and the answer depends on when. Checking a finished grid, hunting a mistake you already know is in there, or settling what tomorrow's paper will print all happen outside the puzzle. Reading the answer at cell forty of sixty happens inside it, and it ends the thing you were doing.
Can a Sudoku solver solve any puzzle?
Any legal 9x9 grid with at least one solution, yes, and quickly. If it returns nothing, the grid you gave it has no completion, which means either you entered a digit wrong or the puzzle is misprinted. Difficulty ratings do not slow a solver down in any way you would notice.
Why does the solver say there is no solution?
Because two of your digits contradict each other somewhere, even if every one of them looked legal when you wrote it. A wrong digit stays legal for a long time and then kills a cell far away. Re-enter the original clues alone. If those solve, the fault is in what you added.
Can a solver show the next move instead of the whole answer?
Some can, and they are a different kind of program: they apply human techniques in order and report the first one that fires. A backtracking solver cannot, and that includes most of the ones bundled into puzzle apps. If step-by-step logic is what you want, solving a grid step by step walks the techniques in the order they should be tried.
How fast is a Sudoku solver?
Milliseconds for a classic grid, on hardware that is a decade old. The counts on this page are in the tens of thousands of placements at worst, and a phone does millions per second. Any wait you experience is the camera, the recognition or the interface, not the search.
Does a Sudoku solver need an internet connection?
It should not. Solving a 9x9 grid is a small amount of arithmetic that any phone can do on its own. If an app insists on a connection to finish a puzzle, it is sending your grid somewhere, and that is worth knowing before you feed it a photo.
Can it solve a puzzle from a photo?
Yes, and the solving is the easy half. Reading nine rows of printed digits off a curved page under a lamp is the hard half, which is why every scanner worth using lets you fix what it read. Scanning a Sudoku with your phone camera covers how to shoot the page so the read comes back clean.
How do I check a newspaper answer without waiting for tomorrow?
Type the printed clues into any solver and compare its grid against yours. If you only want to know whether you are right, compare a single row rather than the whole thing, and you keep the rest of the puzzle unspoiled. The longer version is in checking a newspaper Sudoku answer.
Can I write my own solver?
Yes, and it is a short program. The four steps in this page are the entire algorithm, and a working version fits in about forty lines in most languages. Writing a Sudoku solver with backtracking takes it from those four steps to code, including the cell-ordering change that turned 2,144 placements into 64.
Keep reading
- Sudoku, from the rules up, the short version of everything in the series
- Solving a Sudoku from a photo: what works, what fails, for the misreads behind most failed scans
- How to write a Sudoku solver: backtracking explained, if you want the code rather than the behaviour
- Solve any Sudoku step by step, using only logic, the human version of what the solver skipped
- How to check a newspaper Sudoku answer, the most common honest reason to open one
- How to use a Sudoku hint without ruining the puzzle, for when you are stuck rather than wrong
Get it: Sudoku Master, free on iPhone and Android. 4,000 classic puzzles, an on-device scanner, and no ads while you solve.
