Python sudoku

sudoku.py

# Write a function solve_sudoku(board) that takes a 9x9 grid representing a Sudoku puzzle and solves it using backtracking.

def find_empty(board):
  for x in range(9):
    for y in range(9):
      if board[x][y] == 0: # zero means "empty"
        return x, y
  return None

def check_valid(board, row, col, num):
  for x in range(9): # check num in row
    if board[row][x] == num:
      return False
  for y in range(9): # check num in column
    if board[y][col] == num:
      return False
  grid_x = row - row % 3
  grid_y = col - col % 3
  for i in range(3): # check num in 3x3 grid
    for j in range(3):
      if board[i + grid_x][j + grid_y] == num:
        return False
  return True

def solve_sudoku(board):
  empty = find_empty(board)
  if not empty:
    return board # solved

  row, col = empty

  for num in range(1, 10): # numbers from 1 to 9
    if check_valid(board, row, col, num):
        board[row][col] = num

        res = solve_sudoku(board)
        if res:
          return res
        
        board[row][col] = 0 # backtrack - no solution

  return None

# Test (example from Wikipedia), zero means "empty"
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]
]

solved = solve_sudoku(board)

if solved:
  for x in solved:
    print(x)
else:
  print("No solution.")