This document provides a complete implementation of a Sudoku solver using Python. The solver employs a backtracking algorithm to fill the Sudoku board efficiently.

Program Structure

• Function Definition: The main function is solve_sudoku(board), which solves the given Sudoku board.
• Finding Empty Spaces: The function find_empty(board) identifies empty cells in the Sudoku grid.
• Validation: The function is_valid(board, guess, row, col) checks whether placing a number in a specific cell is valid according to Sudoku rules.
• Backtracking Algorithm: The solver uses recursion to try numbers 1-9 in empty spaces, backtracking when necessary.

Implementation

def solve_sudoku(board):
    empty = find_empty(board)
    if not empty:
        return True  # Puzzle solved
    else:
        row, col = empty

    for guess in range(1, 10):  # Try numbers 1-9
        if is_valid(board, guess, row, col):
            board[row][col] = guess  # Place guess
            
            if solve_sudoku(board):  # Recurse
                return True
            
            board[row][col] = 0  # Reset (backtrack)
    
    return False  # Trigger backtracking


def find_empty(board):
    for r in range(len(board)):
        for c in range(len(board[r])):
            if board[r][c] == 0:  # 0 represents an empty cell
                return (r, c)  # Return row, col
    return None


def is_valid(board, guess, row, col):
    # Check row
    if guess in board[row]:
        return False

    # Check column
    for r in range(len(board)):
        if board[r][col] == guess:
            return False

    # Check 3x3 box
    box_row = row // 3 * 3
    box_col = col // 3 * 3
    for r in range(box_row, box_row + 3):
        for c in range(box_col, box_col + 3):
            if board[r][c] == guess:
                return False

    return True


# Example Sudoku board (0 represents empty cells)
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]
]

solve_sudoku(sudoku_board)
print(sudoku_board)  # Print solved Sudoku board

Documentation

Function: solve_sudoku(board)

Solves the given Sudoku board using backtracking.

• Parameters: board (list of lists): The Sudoku grid to be solved.
• Returns: True if solved, otherwise False.

Function: find_empty(board)

Finds an empty cell in the Sudoku board.

• Parameters: board (list of lists): The Sudoku grid.
• Returns: Tuple of coordinates (row, column) of the first empty cell, or None if no empty cell is found.

Function: is_valid(board, guess, row, col)

Checks if a guessed number can be placed in the specified cell.

• Parameters:
  • board (list of lists): The Sudoku grid.
  • guess (int): The number to place.
  • row (int): Row index of the cell.
  • col (int): Column index of the cell.
• Returns: True if valid, otherwise False.

Conclusion

This Sudoku solver effectively utilizes backtracking to solve puzzles of varying difficulty. By understanding the program structure and its components, you can adapt or enhance it further as needed.