A Sudoku solver is one idea and about thirty lines of code. Find an empty cell,
try the digits 1 to 9 in it, and the moment a digit leads to a cell with nothing
legal left to put in, take it back out and try the next one.
That is backtracking. It is a depth-first search over partly filled grids, it
needs no solving technique you have to invent, and it finishes an ordinary 9x9
puzzle in milliseconds.
Below is the whole solver in Python, a trace of it walking into a wall and
reversing out, the two changes that took one puzzle from 1,407 placements down
to 58 and from 37 milliseconds down to three, and the check that stops it
finishing a puzzle nobody asked it to finish.
Want something to check your output against?
Sudoku Master reads a puzzle off paper with the camera and
returns the finished grid, which is a fast second opinion on a puzzle you did
not type in yourself. Free.
The whole thing, on one screen
def solve(board):
"""Solve a 9x9 grid in place. 0 is an empty cell. True if it worked."""
cell = find_empty(board)
if cell is None:
return True
row, col = cell
for digit in range(1, 10):
if is_legal(board, row, col, digit):
board[row][col] = digit
if solve(board):
return True
board[row][col] = 0
return False
def find_empty(board):
for row in range(9):
for col in range(9):
if board[row][col] == 0:
return row, col
return None
def is_legal(board, row, col, digit):
if digit in board[row]:
return False
if any(board[r][col] == digit for r in range(9)):
return False
top, left = row - row % 3, col - col % 3
for r in range(top, top + 3):
for c in range(left, left + 3):
if board[r][c] == digit:
return False
return True
Five lines in solve carry the whole algorithm, and each one is the answer to a
question people ask about it.
board[row][col] = digit is the guess. Nothing clever chose that digit. It is
the smallest one that is legal right now.
if solve(board): return True is the recursion. Every call fills one more cell,
so the stack is at most 81 deep and the search always terminates.
board[row][col] = 0 is the backtrack, and it is the line beginners leave out.
Without it the grid keeps digits that were legal when they were placed and are
nonsense now.
return False is how a dead end is reported upward. The caller hears it, undoes
its own digit, and moves on to the next one.
if cell is None: return True is the base case, and it is stronger than it
looks. No empty cell means every one of the 81 cells was legal against the whole
grid at the moment it was filled, and legality is symmetric. So a full grid built
this way needs no final validation. It is a solution by construction.
You need two more helpers to run it on anything real:
def parse(text):
"""Read an 81-character grid. Both '.' and '0' mean empty."""
digits = [int(ch) if ch.isdigit() else 0
for ch in text if ch.isdigit() or ch == "."]
return [digits[i * 9:i * 9 + 9] for i in range(9)]
def show(board):
return "\n".join("".join(str(d) if d else "." for d in row)
for row in board)
The rules are one function
Sudoku has one constraint repeated three ways. No digit twice in a row, no digit
twice in a column, no digit twice in a 3x3 box. is_legal is that sentence, and
there is nothing else in the game to encode.
Another way to say it: a cell has twenty peers, the other cells sharing its row,
its column or its box. Eight plus eight plus eight, minus the four counted twice
inside the box. A digit is legal in a cell when none of those twenty peers holds
it.
The one piece of arithmetic worth reading twice is the box. row - row % 3 and
col - col % 3 give the top-left corner of the 3x3 block the cell sits in.
Row 4 gives 3, row 5 gives 3, row 6 gives 3, and those three rows share a band.
row // 3 * 3 is the same number if you prefer it that way. Getting this wrong
produces a solver that finds answers with a repeated digit in a box and looks
correct until somebody checks one.
Watch it walk into a wall
Take a real newspaper puzzle. Thirty givens, 51 empty cells.
2..3..198
3...9..2.
..12.53.7
.......3.
..8..6...
.....18..
.65.1..8.
..7..3..6
.396..7.5
Print a line every time the solver places or removes a digit, and the first ten
events look like this:
place r1c2 = 4
place r1c3 = 6
place r1c5 = 7
dead end at r1c6
undo r1c5 = 7
dead end at r1c5
undo r1c3 = 6
dead end at r1c3
undo r1c2 = 4
place r1c2 = 5
Follow it on the grid. Row 1 reads 2..3..198, so it is missing 4, 5, 6 and 7,
and they belong in r1c2, r1c3, r1c5 and r1c6. The solver starts at the
first empty cell, rejects 1, 2 and 3 because row 1 already holds them, and
commits to 4.
Now it is trapped, and it does not know yet. At r1c3 the only survivor is 6,
because column 3 already carries a 5 at r7c3 and a 7 at r8c3. At r1c5 the
only survivor is 7, because box 2 already carries a 5 at r3c6. That leaves the
5 for r1c6, and box 2 will not take a second one. No legal digit. Dead end.
The search reverses out of three placements to learn one thing: r1c2 is not 4.
A person never pays that. Row 1 needs a 5 somewhere. It cannot be r1c5 or
r1c6, because box 2 holds a 5 already. It cannot be r1c3, because column 3
holds a 5 already. One cell is left, so the 5 goes in r1c2 and the rest of the
row falls out behind it. That is a hidden single, it takes about four seconds to
see, and it is covered properly in naked singles and hidden
singles.
The machine reaches the same digit. It just pays for it in dead ends.
Count placements, not seconds
Time your solver and you have measured your laptop. Count placements and you
have measured your algorithm, and anyone can reproduce the number in any
language.
The puzzle above has 51 empty cells, so a run that never guessed wrong would
place exactly 51 digits. Here is what four versions of the same search actually
cost, on that one grid.
| Version | Placements | Time |
|---|---|---|
| First empty cell, digits 1 to 9 | 1,407 | 37 ms |
| First empty cell, digits 9 down to 1 | 835 | 17 ms |
| Last empty cell first, digits 1 to 9 | 12,364 | 337 ms |
| Fewest candidates first | 58 | 20 ms |
Read the third row again. Scanning for the last empty cell instead of the first
is not a worse algorithm in any principled sense. It is the same search with the
cells visited in a different order. It costs nine times what the first row costs
and more than two hundred times what the last one costs.
That is the real lesson of backtracking. The recursion is fixed. Everything you
can still choose is about which cell you branch on next.
Choose the cell, not the digit
The rule that buys the last row of that table has a name: minimum remaining
values. Before branching, look at every empty cell, work out how many digits are
legal in it, and branch on the smallest list.
def find_best(board):
"""The empty cell with the fewest legal digits, and that list of digits."""
best, best_digits = None, None
for row in range(9):
for col in range(9):
if board[row][col] == 0:
digits = [d for d in range(1, 10)
if is_legal(board, row, col, d)]
if best_digits is None or len(digits) < len(best_digits):
best, best_digits = (row, col), digits
if len(digits) <= 1:
return best, best_digits
return best, best_digits
def solve(board):
cell, digits = find_best(board)
if cell is None:
return True
row, col = cell
for digit in digits:
board[row][col] = digit
if solve(board):
return True
board[row][col] = 0
return False
Two things happen at once here, and both are worth naming.
A cell with exactly one candidate gets placed with no branch at all. That is a
naked single, and the search now performs the cheapest human technique for free
rather than discovering it by trial.
A cell with zero candidates fails the branch immediately. The naive version
would have kept filling other cells for a while before it stumbled into that
cell and found it empty of options. Failing early is most of the saving.
The early return when a cell has one candidate or fewer matters too. Without
it you scan all 81 cells every single call, and a scan that costs more than the
branch it saves is not an optimisation.
Fifty-eight placements against 51 perfect ones means the search guessed wrong
seven times on the whole puzzle. That is close to how a competent person solves.
Bitmasks, when you actually need the speed
is_legal walks up to 20 peers every time it is asked. Keep three arrays of
nine-bit masks instead, and the same question becomes one and.
def solve_fast(board):
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
empties = []
for r in range(9):
for c in range(9):
d = board[r][c]
if d:
bit = 1 << (d - 1)
rows[r] |= bit
cols[c] |= bit
boxes[r // 3 * 3 + c // 3] |= bit
else:
empties.append((r, c))
def search(i):
if i == len(empties):
return True
r, c = empties[i]
b = r // 3 * 3 + c // 3
free = ~(rows[r] | cols[c] | boxes[b]) & 0x1FF
while free:
bit = free & -free
free ^= bit
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
board[r][c] = bit.bit_length()
if search(i + 1):
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
board[r][c] = 0
return False
return search(0)
free is a nine-bit number with a 1 for every digit still available. free & -free
peels off the lowest set bit, and bit.bit_length() turns that bit back into the
digit it stands for. Placing and unplacing are both a single exclusive or on
three integers.
On the same newspaper puzzle this runs in 3.2 ms against the first version's
37 ms, and it does it while making exactly the same 1,407 placements. Nothing
about the search changed. The constant did.
Combine the two ideas if you want the fast version to also be the clever one:
pick the empty cell whose free mask has the fewest bits set, which
bin(free).count("1") gives you cheaply, and branch there.
The answer, or the first answer it happened to find
Here is the bug that ships. solve returns the first solution the search order
reaches. If the puzzle has one solution, first is the same as only. If it has
several, first is an accident of writing range(1, 10) rather than
range(9, 0, -1).
One solution, exactly, is part of the definition of a puzzle. Two or more and
you have a grid with digits on it that no chain of logic can close. So counting
solutions is not an academic exercise. It is the line between a generator and a
generator that lies.
Counting is the same search with the return statements removed.
def count_solutions(board, limit=2):
"""Number of solutions, stopping as soon as `limit` have been found."""
cell = find_empty(board)
if cell is None:
return 1
row, col = cell
total = 0
for digit in range(1, 10):
if is_legal(board, row, col, digit):
board[row][col] = digit
total += count_solutions(board, limit)
board[row][col] = 0
if total >= limit:
break
return total
The limit is not decoration. Stop at 2 and you get an answer in the same time
the solver takes, because one extra solution is all the proof of ambiguity you
need. Leave it uncapped on a puzzle with a hole in it and the count can run for
a long time.
Run it on the newspaper grid above and it returns 1. Now delete one given and
watch what happens.
- Remove the 5 at
r9c9and the grid has 18 solutions. - Remove the 2 at
r3c4and it has 16.
Neither puzzle fails. Neither one complains. Both hand back a complete grid with
1 to 9 in every row, every column and every box.
Solve the first and 15 cells come out different from the printed answer. Solve
the second and, on my digit order, the grid it returns is the right one, by
luck. The lucky run is the dangerous one, because the two outputs are
indistinguishable and the solution count appears nowhere on the screen. That is
exactly what a dropped given does to a camera scanner, which is why checking a
scan against the paper matters more than
the code behind it.
While you are at it, reject illegal input before you search rather than after.
def is_consistent(board):
"""No given repeats a peer. Cheaper and clearer than failing at depth 40."""
for row in range(9):
for col in range(9):
digit = board[row][col]
if digit:
board[row][col] = 0
ok = is_legal(board, row, col, digit)
board[row][col] = digit
if not ok:
return False
return True
Lifting the digit out before testing it is the trick there. Otherwise every cell
clashes with itself.
The two kinds of failure now report differently, which is the whole point.
Suppose the 7 at r8c3 is typed as a 1. Row 8 reads ..1..3..6 and looks
entirely healthy; the clash is in column 3, which already holds a 1 at r3c3.
is_consistent finds it in microseconds and can name the cell. A legal grid
that simply has no completion cannot be named like that: it comes back from the
search empty handed, and the honest message is "check your input", because a
typed or scanned grid is wrong far more often than a printed puzzle is.
LeetCode 37, and the four ways people fail it
The problem hands you a List[List[str]] with "." for empty, wants the board
modified in place, and returns nothing. The board is promised to have one
solution. Same algorithm, four traps.
Not returning after success. Convert solve to return None and the
recursion carries on past the answer, unwinds, and the undo line erases it. The
boolean return value is what freezes the finished board.
Forgetting the undo. The grid fills with digits that were legal at the
moment they were written. The result passes no check at all.
Comparing a character to a number. board[r][c] == 5 is never true when the
cell holds "5". Convert once at the boundary or keep everything as strings, but
do not mix.
Rebuilding candidate sets on every call. It passes and it is slow. Maintain
three sets or three bitmasks as you place and unplace, and precompute the list of
empty cells instead of rescanning 81 cells at every level.
One difference between the exercise and real code. Returning on the first
solution is correct for LeetCode because the input is promised unique. In a
solver you ship it is a choice you should make on purpose, because a user's grid
carries no such promise.
Generating a puzzle is the same search, run backwards
Solving is the easy half. To make a puzzle you run the search twice.
First, fill an empty grid. That is solve with the digit loop shuffled, and it
returns a random completed grid out of the 6,670,903,752,021,072,936,960 that
exist.
import random
def fill(board):
cell = find_empty(board)
if cell is None:
return True
row, col = cell
digits = random.sample(range(1, 10), 9)
for digit in digits:
if is_legal(board, row, col, digit):
board[row][col] = digit
if fill(board):
return True
board[row][col] = 0
return False
Second, dig holes. Visit the 81 cells in random order, blank each one, and count
the solutions with the cap set to 2. If the count is still 1, leave the hole. If
it is more, put the digit back. What you are left with is a puzzle whose
uniqueness you have proved rather than hoped for.
Random digging like that stops somewhere in the twenties. Twelve runs of the
code above landed between 23 and 26 clues, which is ordinary newspaper
territory. Do not be tempted to keep digging past it. 17 clues is the floor
for a unique solution, and it is a hard floor: McGuire, Tugemann and Civario
established it in 2012 by exhausting the 16-clue case on a computer. Your
generator can fail to reach 17. It cannot beat it, and neither can anyone
else's.
The harder gap is at the other end. Your generator has no idea how hard the
puzzle it just made is, and clue count will not tell it: a 30-clue grid can beat
a 24-clue one comfortably. Grading means writing a second solver that works the
human ladder in order and records the most expensive rule it had to reach for.
That is a bigger program than this one, and it is why difficulty labels differ
between publishers.
What the search will never give you
Backtracking returns an answer. It does not return a reason.
Sudoku Master, which I built, does these same two things in Dart: validate the
grid, then backtrack. Finished grid, or nothing. It narrates none of it, and
there was never anything to narrate. A trail of 1,407 placements with 1,356 of
them withdrawn is not an explanation of anything, to anybody.
A program that names one cell and one reason is a different program. It keeps
candidate sets, runs singles, then pairs, then pointing pairs, applies the
cheapest rule that changes anything, and halts with a sentence rather than a
grid. That is the shape of solving step by step with logic
alone, and every line of it is harder than
the thirty above.
One last thing to keep in proportion. Generalised to grids of any size, deciding
whether a Sudoku has a solution is NP-complete, a result due to Yato and Seta in
- That is a statement about the whole family of puzzles and it says nothing about the 9x9 in your terminal, which is a finite problem your first attempt already solves in milliseconds.
Common bugs
No undo. The single most common one. board[row][col] = 0 after the failed
recursive call, every time.
No return value. A solver that returns None cannot tell its caller the
branch worked, so the recursion keeps going and erases the answer on the way
back up.
Off by one on the box. row // 3 * 3 and row - row % 3, not row // 3.
The wrong one gives a solver that produces boxes with repeated digits.
Mutating the caller's grid without saying so. Solving in place is fine and
fast. Silently destroying the puzzle somebody passed you is not. Copy it, or
document it loudly.
Reading "no solution" as a broken puzzle. It nearly always means the input is
wrong. Validate first, then tell the user which cell clashes.
Benchmarking in seconds. Count placements. Seconds change with your machine,
your language and what else is running.
Stopping at one solution when you needed to know about two. A solver may. A
generator, a validator and anything checking user input must not.
Questions people ask
What is the time complexity of a Sudoku backtracking solver?
Exponential in the number of empty cells in the worst case, and the honest
answer is that the bound is useless. Nine digits across m empty cells gives a
crude ceiling of nine to the power m, which for 51 empties is a number nothing
will ever count to. Real grids are nowhere near it because each placement kills
candidates in twenty peer cells. Measure placements on real puzzles instead.
Is there a faster algorithm than backtracking?
Yes, in two directions. Add constraint propagation, so after each placement you
push the consequences through the grid and place every forced digit before
branching again. Or reformulate the puzzle as exact cover and run Knuth's
Algorithm X with dancing links: 729 candidate placements, 81 cells times 9
digits, against 324 constraints, one for each cell plus each digit in each row,
column and box. Both are faster. Neither is necessary for a 9x9 grid, which
plain backtracking finishes in milliseconds.
Can I write a Sudoku solver without recursion?
Yes. Precompute the list of empty cells, keep an index into it and an array
recording the last digit tried in each cell, then step forward when a digit fits
and step backward when a cell runs out of digits. It is the same search with the
call stack written by hand. Worth doing in a language with a small stack, or on
a microcontroller. In Python the depth never exceeds 81, so recursion is fine.
How do I check that a puzzle has exactly one solution?
Count solutions with a cap of 2, which is the count_solutions function above.
If it returns 2 the puzzle is ambiguous and you can stop searching. Do this
before you publish a generated puzzle, and do it before you trust a grid a user
typed or scanned in.
Why does my solver return a filled grid that is not the right answer?
Because the grid it was given is not the puzzle you meant. A missing given makes
the puzzle ambiguous, and your search returns whichever solution its digit order
reaches first. Count the givens against the source before anything else: if the
counts differ, you have found the bug without reading a single digit.
Does the same code solve 16x16 or 6x6 grids?
The algorithm is identical. The constants are not. Replace 9 with the side
length, and replace the single // 3 with the box height and the box width,
which are not equal for every size: a 6x6 grid uses boxes 2 cells tall and 3
wide. A 16x16 grid also needs a symbol table, since it runs 0 to 9 plus A to F.
How do I make my solver explain its moves?
You do not retrofit it. Write a second solver that implements techniques in
order of cost, applies the cheapest one that changes the grid, and records what
it applied. Backtracking has no explanation to give, because its reasoning is
"this digit failed, so I tried the next one" repeated a few thousand times.
Why is my LeetCode 37 solution timing out?
Almost always because legality is being recomputed from scratch. Scanning a row,
a column and a box on every candidate at every level multiplies out fast. Keep
three arrays of used digits updated as you place and unplace, and precompute the
empty cells so you are not rescanning the board to find the next one.
Keep reading
- How a Sudoku solver works, and when you should use one, for the same algorithm without the code, and the argument about when to reach for it
- Solve any Sudoku step by step using only logic, which is the program you write when you want reasons instead of answers
- Naked singles and hidden singles, with worked grids, the technique the trace above shows the search paying for in dead ends
- Seventeen clues: the smallest Sudoku that can exist, on the floor your generator will never reach
- Scan a Sudoku with your phone camera and get the answer, for the other half of the problem, which is getting 81 correct digits into the solver
- The complete Sudoku guide, start there if you would rather see the whole picture in order
Get it: Sudoku Master, free on iPhone and Android. The
link sends you to whichever store your phone uses.
Top comments (0)