Sudoku Solver

solver.py

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

    def is_valid(puzzle, row, col, num):
        # check row
        for j in range(9):
            if puzzle[row][j] == num:
                return False
        # check column
        for i in range(9):
            if puzzle[i][col] == num:
                return False
        # check square
        square_row = (row // 3) * 3
        square_col = (col // 3) * 3
        for i in range(square_row, square_row + 3):
            for j in range(square_col, square_col + 3):
                if puzzle[i][j] == num:
                    return False
        return True

    def solve(puzzle):
        empty_cell = find_empty(puzzle)
        if empty_cell is None:
            return True
        row, col = empty_cell
        for num in range(1, 10):
            if is_valid(puzzle, row, col, num):
                puzzle[row][col] = num
                if solve(puzzle):
                    return True
                puzzle[row][col] = 0
        return False

    # create a copy of the input puzzle to avoid modifying the original
    puzzle_copy = [row[:] for row in puzzle]
    # solve the puzzle
    solve(puzzle_copy)
    return puzzle_copy

def test_solve_sudoku():
    puzzle = [
        [0, 0, 0, 2, 6, 0, 7, 0, 1],
        [6, 8, 0, 0, 7, 0, 0, 9, 0],
        [1, 9, 0, 0, 0, 4, 5, 0, 0],
        [8, 2, 0, 1, 0, 0, 0, 4, 0],
        [0, 0, 4, 6, 0, 2, 9, 0, 0],
        [0, 5, 0, 0, 0, 3, 0, 2, 8],
        [0, 0, 9, 3, 0, 0, 0, 7, 4],
        [0, 4, 0, 0, 5, 0, 0, 3, 6],
        [7, 0, 3, 0, 1, 8, 0, 0, 0]
    ]
    solution = solve_sudoku(puzzle)

    for row in solution:
        print(*row, sep=' ')

test_solve_sudoku()