Sudoku Solving in Python

Creating sudoku solvers can be a great way to familiarize yourself with recursive backtracking and algorithm solving. In this blog post, we'll explore the some helper functions from a command-line Sudoku game project I created to demonstrate these methods. This file contains essential helper functions that facilitate solving Sudoku puzzles. We'll break down the key functions: is_valid, find_empty, and solve.

Checking Validity of a Number
The is_valid function checks whether placing a specific number in a given cell is valid according to Sudoku rules.

def is_valid(board, row, col, num):
    # Check if the number is not present in the same row and column
    if num in board[row] or num in [board[i][col] for i in range(9)]:
        return False

    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False
    return True

Row and Column Check: Ensures the number is not already present in the same row or column.
Subgrid Check: Ensures the number is not present in the 3x3 subgrid.

Finding an Empty Cell

The find_empty function locates the next empty cell (represented by 0) on the board.

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

Iteration: Iterates through the board to find an empty cell.
Return: Returns the coordinates of the first empty cell found or None if the board is full.

Solving the Sudoku Puzzle

The solve function uses backtracking to solve the Sudoku puzzle.

def solve(board):
    empty_cell = find_empty(board)
    # Board is solved
    if not empty_cell:
        return board

    row, col = empty_cell

    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    random.shuffle(numbers)

    for num in numbers:
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve(board):
                return board
            # Backtrack if current placement doesn't lead to a solution
            board[row][col] = 0
        # No valid number for current empty cell
    return False

Find Empty Cell: Uses find_empty to locate the next empty cell.
Backtracking: Tries placing numbers 1-9 in the empty cell, checking validity with is_valid.

Recursive Solve: Recursively attempts to solve the board. If a placement leads to a solution, it returns the solved board.
Backtrack: If a placement doesn't lead to a solution, it resets the cell and tries the next number.

Conclusion

Helper functions are crucial for the functionality of our Sudoku solver. The is_valid function ensures that the Sudoku rules are followed, find_empty helps locate the next cell to fill, and solve uses recursive backtracking to find the solution. Understanding these helper functions provides insight into the logic behind solving Sudoku puzzles programmatically.

The above is the detailed content of Sudoku Solving in Python. For more information, please follow other related articles on the PHP Chinese website!