Python Program to Solve Sudoku Puzzle

You can solve Sudoku in Python using backtracking by defining a function that tries numbers 1 to 9 in empty cells and recursively checks if the board is valid, for example: def solve(board): ... with backtracking logic.

Examples

Input[[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]]

Output[[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]]

Input[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]

Output[[1,2,3,4,5,6,7,8,9],[4,5,6,7,8,9,1,2,3],[7,8,9,1,2,3,4,5,6],[2,3,4,5,6,7,8,9,1],[5,6,7,8,9,1,2,3,4],[8,9,1,2,3,4,5,6,7],[3,4,5,6,7,8,9,1,2],[6,7,8,9,1,2,3,4,5],[9,1,2,3,4,5,6,7,8]]

Input[[1,2,3,4,5,6,7,8,9],[4,5,6,7,8,9,1,2,3],[7,8,9,1,2,3,4,5,6],[2,3,4,5,6,7,8,9,1],[5,6,7,8,9,1,2,3,4],[8,9,1,2,3,4,5,6,7],[3,4,5,6,7,8,9,1,2],[6,7,8,9,1,2,3,4,5],[9,1,2,3,4,5,6,7,0]]

Output[[1,2,3,4,5,6,7,8,9],[4,5,6,7,8,9,1,2,3],[7,8,9,1,2,3,4,5,6],[2,3,4,5,6,7,8,9,1],[5,6,7,8,9,1,2,3,4],[8,9,1,2,3,4,5,6,7],[3,4,5,6,7,8,9,1,2],[6,7,8,9,1,2,3,4,5],[9,1,2,3,4,5,6,7,8]]

How to Think About It

To solve Sudoku, think of filling empty cells one by one with numbers 1 to 9. For each empty cell, try a number and check if it breaks Sudoku rules (no repeats in row, column, or 3x3 box). If it fits, move to the next empty cell. If stuck, go back and try a different number. This trial and error is called backtracking.

Algorithm

1

Find an empty cell in the Sudoku board.

2

If no empty cell is found, the puzzle is solved; return true.

3

Try numbers 1 to 9 in the empty cell.

4

For each number, check if placing it is valid according to Sudoku rules.

5

If valid, place the number and recursively try to solve the rest of the board.

6

If recursion fails, reset the cell and try the next number.

7

If all numbers fail, return false to backtrack.

Code

python

def solve(board):
    empty = find_empty(board)
    if not empty:
        return True
    row, col = empty
    for num in range(1, 10):
        if valid(board, num, (row, col)):
            board[row][col] = num
            if solve(board):
                return True
            board[row][col] = 0
    return False

def find_empty(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    return None

def valid(board, num, pos):
    row, col = pos
    # Check row
    for i in range(9):
        if board[row][i] == num and i != col:
            return False
    # Check column
    for i in range(9):
        if board[i][col] == num and i != row:
            return False
    # Check box
    box_x = col // 3
    box_y = row // 3
    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x*3, box_x*3 + 3):
            if board[i][j] == num and (i, j) != pos:
                return False
    return True

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]
]
if solve(board):
    for row in board:
        print(row)
else:
    print("No solution exists")

Output

[[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]]

Dry Run

Let's trace the first empty cell filling in the example board.

1

Find first empty cell

Empty cell found at position (0, 2) with value 0.

2

Try number 1 in (0, 2)

Check row 0, column 2, and 3x3 box for number 1. Number 1 is valid.

3

Place number 1 and recurse

Place 1 at (0, 2) and call solve recursively.

4

If recursion fails, backtrack

If no solution found, reset (0, 2) to 0 and try next number.

Step	Cell	Number Tried	Valid?	Action
1	(0,2)	1	Yes	Place and recurse
2	(0,2)	2	No	Skip
3	(0,2)	3	Yes	Place and recurse

Why This Works

Step 1: Backtracking tries all options

The code tries numbers 1 to 9 in empty cells and moves forward only if the number fits Sudoku rules, otherwise it backtracks.

Step 2: Validation ensures Sudoku rules

The valid function checks rows, columns, and 3x3 boxes to prevent duplicates.

Step 3: Recursion explores solutions

The solve function calls itself to fill the next empty cell, building the solution step-by-step.

Alternative Approaches

Constraint Propagation with Backtracking

python

import copy

def solve_cp(board):
    def find_empty_cp(b):
        for i in range(9):
            for j in range(9):
                if b[i][j] == 0:
                    return (i, j)
        return None

    def valid_cp(b, num, pos):
        row, col = pos
        for i in range(9):
            if b[row][i] == num and i != col:
                return False
        for i in range(9):
            if b[i][col] == num and i != row:
                return False
        box_x = col // 3
        box_y = row // 3
        for i in range(box_y*3, box_y*3 + 3):
            for j in range(box_x*3, box_x*3 + 3):
                if b[i][j] == num and (i, j) != pos:
                    return False
        return True

    empty = find_empty_cp(board)
    if not empty:
        return True
    row, col = empty
    for num in range(1, 10):
        if valid_cp(board, num, (row, col)):
            board[row][col] = num
            if solve_cp(board):
                return True
            board[row][col] = 0
    return False

board_cp = copy.deepcopy(board)
if solve_cp(board_cp):
    for row in board_cp:
        print(row)
else:
    print("No solution")

This method is similar but can be extended with constraint propagation to reduce guesses, improving speed.

Using a Sudoku Solver Library

python

import sudoku

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]
]
solver = sudoku.Sudoku(board)
solution = solver.solve()
print(solution.board)

Using a library is easiest but depends on external code and may hide the solving logic.

Complexity: O(9^(n)) where n is number of empty cells time, O(n) for recursion stack and board state space

Time Complexity

The algorithm tries up to 9 numbers for each empty cell, leading to exponential time in worst case.

Space Complexity

Uses recursion stack proportional to number of empty cells and modifies board in place.

Which Approach is Fastest?

Backtracking with constraint propagation is faster than plain backtracking; using libraries can be faster but less educational.

Approach	Time	Space	Best For
Backtracking	O(9^n)	O(n)	Learning and small puzzles
Backtracking + Constraint Propagation	Faster than plain backtracking	O(n)	Larger puzzles, better performance
Sudoku Solver Library	Depends on implementation	Depends	Quick solutions without coding