How to Write a Sudoku Solver: Backtracking, Explained

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.

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 r9c9 and the grid has 18 solutions.
• Remove the 2 at r3c4 and 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 2003. 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.