Sudoku Solver

Table of Contents +

Sudoku is a puzzle most people have seen. You fill a nine by nine grid with digits one to nine. Each row, each column, and each small three by three box must hold every digit exactly once. Solving it by hand needs guessing and checking. A computer does the same, but in a careful, organized way. That careful guess-and-check is called backtracking, and this question is the perfect place to learn it.

🎯 The Problem

You get a nine by nine grid with some cells filled. You must fill every empty cell so the grid follows the Sudoku rules.

  • Some cells already hold a digit.
  • Empty cells are marked with a dot or a zero.
  • Every row must hold the digits one to nine with no repeat.
  • Every column must do the same.
  • Each of the nine small three by three boxes must do the same.
  • A proper puzzle has exactly one valid solution.
Input (a row of the grid, dots are empty):
  5 3 . | . 7 . | . . .
  6 . . | 1 9 5 | . . .
  ...


Output: the same grid with every empty cell filled
        so all rows, columns and boxes are valid.

You change the grid in place and the filled grid is the answer.

This diagram shows the three rules every digit must obey at once. A digit must be unique across its row, its column, and its box.

place digit D at cell r,c

check row r has no D

check column c has no D

check 3x3 box has no D

all three pass -> place D

🐢 Approach 1: Fill Everything Then Check at the End (Brute Force)

The idea in one line: fill every empty cell with any digit, build a full grid, then check it.

The idea:

  • Put some digit in every empty cell.
  • Build a complete grid first.
  • Only then check if the whole grid follows the rules.

How it works:

  • If the full grid is valid, you are done.
  • If not, change a digit somewhere and try the whole thing again.

Why it is weak:

  • There are nine choices per empty cell, and a hard puzzle has fifty or more empties.
  • So the number of full grids to test is astronomically large.
  • You finish filling the grid before learning an early choice was already wrong.
  • You waste effort on grids that broke at the very first cell.

Here is the plain backtracking code for that idea:

sudoku_solver_brute_force.py
def solve_sudoku(board):
    def valid(row, col, value):
        box_row = (row // 3) * 3
        box_col = (col // 3) * 3
        for i in range(9):
            if board[row][i] == value or board[i][col] == value:
                return False
            if board[box_row + i // 3][box_col + i % 3] == value:
                return False
        return True


    def dfs():
        for row in range(9):
            for col in range(9):
                if board[row][col] == ".":
                    for value in "123456789":
                        if valid(row, col, value):
                            board[row][col] = value
                            if dfs():
                                return True
                            board[row][col] = "."
                    return False
        return True


    dfs()

⚡ Approach 2: Backtracking With Early Checks (Best)

The idea in one line: check validity the moment you place a digit, not at the end.

The idea:

  • Backtracking means place a digit, move forward, and step back if you hit a dead end.
  • Find the first empty cell and try the digits one to nine.
  • Check each digit before you accept it.

How it works:

  • Ask three questions: is this digit already in the row, the column, or the box?
  • If any answer is yes, the digit is not allowed, so try the next one.
  • If all three checks pass, place it and move to the next empty cell.
  • If a cell has no valid digit, erase the last cell you filled and try its next digit. That is the backtrack.

Why it is fast:

  • Checking at every placement cuts off bad paths early.
  • Most digits fail the row, column, or box test right away.
  • So you never build a whole broken grid before noticing the mistake.

This diagram shows the backtracking flow for one empty cell.

yes

no

yes

no

find first empty cell

try digit 1 to 9

is the digit valid here?

place it, solve the rest

try the next digit

did the rest solve?

puzzle solved

erase and backtrack

Steps to Solve

  1. Scan the grid to find the first empty cell.
  2. If there is no empty cell, the puzzle is already solved, so return success.
  3. Try each digit from one to nine in that cell.
  4. For each digit, check that it does not repeat in its row, its column, or its three by three box.
  5. If the digit is valid, place it and recurse to solve the rest of the grid.
  6. If the recursion solves the rest, you are done.
  7. If it fails, erase the cell and try the next digit. If no digit works, return failure so the caller can backtrack.

This Python version keeps the grid as a list of lists and solves it in place with backtracking.

sudoku_solver.py
board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]




def is_valid(r, c, d):
    for i in range(9):
        if board[r][i] == d:        # same row
            return False
        if board[i][c] == d:        # same column
            return False
    br, bc = (r // 3) * 3, (c // 3) * 3   # top-left of the 3x3 box
    for i in range(3):
        for j in range(3):
            if board[br + i][bc + j] == d:  # same box
                return False
    return True




def solve():
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:           # first empty cell
                for d in range(1, 10):
                    if is_valid(r, c, d):
                        board[r][c] = d     # place the digit
                        if solve():
                            return True
                        board[r][c] = 0     # backtrack
                return False                # no digit fit here
    return True                            # no empty cell left




solve()
for row in board:
    print(" ".join(str(n) for n in row))

The output of the above code will be:

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

Let us read the Python version line by line and see why it works.

The function is_valid answers one question. Can digit d go at row r and column c? The first loop walks index i from zero to eight. It checks board[r][i] == d for the row and board[i][c] == d for the column at the same time. If d already appears in that row or column, the function returns False.

The lines br, bc = (r // 3) * 3, (c // 3) * 3 find the top-left corner of the three by three box that holds this cell. The // 3 is integer division. So row five lands in box-row one, and 1 * 3 gives the starting row three. The double loop then checks all nine cells in that box for d.

In solve, the two outer loops find the first cell that is still zero, which means empty. The line for d in range(1, 10) tries each digit one to nine. The line if is_valid(r, c, d) is the early check. We only place a digit that already passes all three rules.

The line board[r][c] = d places the digit. Then if solve(): return True recurses to fill the rest. If the rest of the grid solves, we bubble True all the way up. The line board[r][c] = 0 is the backtrack. It erases the digit when the recursion failed, so the loop can try the next digit.

The line return False after the digit loop is important. It runs when no digit fit this cell. It tells the previous call that its own last choice was wrong, so that call backtracks. The final return True runs only when the loops found no empty cell, which means the grid is full and solved.

⏱️ Time and Space Complexity

In the worst case each empty cell could try nine digits, so the time is bounded by nine to the power of the number of empty cells. That sounds huge, but the validity check prunes almost all of it. Most digits fail the row, column, or box test right away, so the real search is small. The space is the recursion depth, which is at most the number of empty cells, plus the fixed grid.

Approach Time Complexity Space Complexity
Fill all then check O(9^m) with m empty cells, very slow O(m)
Backtracking with early checks O(9^m) worst case, fast in practice O(m) recursion depth

Tip

The whole speed of this solution comes from checking validity before you place a digit. Never fill a cell first and check later. Check, then place. That one habit turns a hopeless search into a quick one.

🧩 Key Takeaways

  • ✅ Find the first empty cell, then try digits one to nine in it.
  • ✅ Check the row, the column, and the three by three box before placing a digit.
  • ✅ Place a valid digit and recurse, then erase it if the rest of the grid fails.
  • ✅ Use integer division by three to find which box a cell belongs to.
  • ✅ The early validity check is what makes the search fast.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What three things must a digit satisfy before we place it in a cell?

    Why: A Sudoku digit must not repeat in its row, its column, or its 3x3 box.

  2. 2

    What does the backtracking step do when no digit fits a cell?

    Why: When a cell has no valid digit, we undo the previous choice and try the next digit in that earlier cell.

  3. 3

    How do we find which 3x3 box a cell at row r, column c belongs to?

    Why: Integer division by three maps the cell to its box, and times three gives the box's starting cell.

  4. 4

    Why is checking validity before placing a digit important?

    Why: Checking first cuts off invalid branches immediately instead of building a whole broken grid.

Score: 0 / 4

🚀 What’s Next?

Previous Expression Add Operators Next Word Break II