HardBacktrackingRecursionMatrixConstraint Satisfaction

Sudoku Solver

1 approach, code in every language

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 see the solution

You get 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

After the pattern

Now solve one you haven't seen.

Complete the Planting Frame is our own problem on the technique behind Sudoku Solver: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free