Penyelesaian Sudoku dalam Python

Mencipta penyelesai sudoku boleh menjadi cara yang bagus untuk membiasakan diri dengan penjejakan ke belakang rekursif dan penyelesaian algoritma. Dalam catatan blog ini, kami akan meneroka beberapa fungsi pembantu daripada projek permainan Sudoku baris arahan yang saya buat untuk menunjukkan kaedah ini. Fail ini mengandungi fungsi pembantu penting yang memudahkan penyelesaian teka-teki Sudoku. Kami akan memecahkan fungsi utama: is_valid, find_empty dan solve.

Menyemak Kesahihan Nombor
Fungsi is_valid menyemak sama ada meletakkan nombor tertentu dalam sel tertentu adalah sah mengikut peraturan Sudoku.

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

Semakan Baris dan Lajur: Memastikan nombor belum ada dalam baris atau lajur yang sama.
Semakan Subgrid: Memastikan nombor tidak terdapat dalam subgrid 3x3.

Mencari Sel Kosong

Fungsi find_empty mencari sel kosong seterusnya (diwakili oleh 0) pada papan.

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

Lelaran: Lelaran melalui papan untuk mencari sel kosong.
Kembali: Mengembalikan koordinat sel kosong pertama ditemui atau Tiada jika papan penuh.

Menyelesaikan Teka-teki Sudoku

Fungsi selesai menggunakan penjejakan ke belakang untuk menyelesaikan teka-teki Sudoku.

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

Cari Sel Kosong: Menggunakan find_empty untuk mencari sel kosong seterusnya.
Menjejak ke belakang: Cuba meletakkan nombor 1-9 dalam sel kosong, menyemak kesahihan dengan is_valid.

Penyelesaian Rekursif: Secara rekursif cuba menyelesaikan papan. Jika peletakan membawa kepada penyelesaian, ia mengembalikan papan yang telah diselesaikan.
Backtrack: Jika peletakan tidak membawa kepada penyelesaian, ia menetapkan semula sel dan mencuba nombor seterusnya.

Kesimpulan

Fungsi pembantu adalah penting untuk kefungsian penyelesai Sudoku kami. Fungsi is_valid memastikan bahawa peraturan Sudoku dipatuhi, find_empty membantu mencari sel seterusnya untuk diisi dan menyelesaikan menggunakan penjejakan belakang rekursif untuk mencari penyelesaian. Memahami fungsi pembantu ini memberikan gambaran tentang logik di sebalik penyelesaian teka-teki Sudoku secara pemrograman.

Atas ialah kandungan terperinci Penyelesaian Sudoku dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!