HardBacktrackingRecursionMatrixConstraint Satisfaction

Sudoku Solver

1 approach, code in all languages

You are given a partially completed 9x9 Sudoku grid where empty cells are marked with the character '.'. Fill every empty cell with a digit from '1' to '9' so that the finished grid is valid: each row must contain the digits 1 through 9 without repetition, each column must do the same, and each of the nine 3x3 sub-grids must also contain every digit exactly once.

Modify the grid in place so it holds a complete, valid solution. The puzzle is guaranteed to have exactly one solution, so you do not need to handle ambiguous or unsolvable inputs.

Example 1

Input: board = [ ['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'] ]

Output: The same grid with every '.' replaced by a digit so that all rows, columns, and 3x3 blocks are valid.

Backtracking tries candidate digits for each blank cell and commits only to placements that keep the grid consistent, eventually producing the unique completed board.

Example 2

Input: board = [ ['.','.','9','7','4','8','.','.','.'], ['7','.','.','.','.','.','.','.','.'], ['.','2','.','1','.','9','.','.','.'], ['.','.','7','.','.','.','2','4','.'], ['.','6','4','.','1','.','5','9','.'], ['.','9','8','.','.','.','3','.','.'], ['.','.','.','8','.','3','.','2','.'], ['.','.','.','.','.','.','.','.','6'], ['.','.','.','2','7','5','9','.','.'] ]

Output: A fully filled 9x9 grid satisfying every row, column, and block constraint.

Each empty position is resolved by testing digits in order; whenever a partial assignment cannot lead to a solution, the search rewinds and tries the next digit.

Constraints

board.length == 9 and board[i].length == 9
Each cell holds a digit from '1' to '9' or the placeholder '.'
The input is guaranteed to have a single unique solution

Recursive Backtracking

Scan for the next empty cell, try each digit that does not break a row, column, or block rule, and recurse; undo the choice if the recursion fails.

Loading animation…

Intuition

Sudoku is a constraint-satisfaction puzzle: every empty cell has a small set of legal digits determined by its row, column, and 3x3 block. By placing a legal digit and immediately recursing on the next blank, we build the solution incrementally. If we ever reach a cell with no legal digit, the current path is a dead end, so we erase the last placement and let the caller try another digit. Because the puzzle has a unique answer, the first complete assignment we reach is the solution.

Algorithm walkthrough

1Walk the grid to locate the first cell still holding '.'; if none remain, the board is complete and we report success.
2For that cell, test digits '1' through '9' and keep only those absent from the same row, column, and 3x3 block.
3Place a valid digit, then recurse to solve the remainder of the board.
4If the recursive call succeeds, propagate success upward without touching the board again.
5If it fails, reset the cell back to '.' and try the next candidate; if all nine fail, return failure so an earlier cell can change its choice.

Implementation

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def is_valid(r: int, c: int, ch: str) -> bool:
            for i in range(9):
                if board[r][i] == ch or board[i][c] == ch:
                    return False
                if board[3 * (r // 3) + i // 3][3 * (c // 3) + i % 3] == ch:
                    return False
            return True

        def solve() -> bool:
            for r in range(9):
                for c in range(9):
                    if board[r][c] == '.':
                        for d in '123456789':
                            if is_valid(r, c, d):
                                board[r][c] = d
                                if solve():
                                    return True
                                board[r][c] = '.'
                        return False
            return True

        solve()

Time

O(9^(m)) where m is the number of empty cells in the worst case

Space

O(m) for the recursion stack on a fixed 9x9 grid

The 9x9 bound keeps validity checks constant time, so practical performance is far better than the theoretical worst case.

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI