用 Python 求解數獨

建立數獨求解器是熟悉遞歸回溯和演算法求解的好方法。在這篇文章中，我們將探討我創建的命令列數獨遊戲專案中的一些輔助函數，以示範這些方法。該檔案包含有助於解決數獨謎題的基本輔助函數。我們將分解關鍵函數：is_valid、find_empty 和solve。

檢查號碼的有效性
is_valid 函數根據數獨規則檢查在給定儲存格中放置特定數字是否有效。

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

行和列檢查：確保數字不存在於同一行或列中。
子網格檢查：確保數字不存在於 3x3 子網格中。

找到一個空白單元格

find_empty 函數定位棋盤上的下一個空白單元格（以 0 表示）。

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

迭代：迭代棋盤以尋找空白單元格。
傳回：傳回找到的第一個空單元格的座標，如果棋盤已滿，則傳回 None。

解決數獨難題

解函數使用回溯來解決數獨難題。

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 定位下一個空白儲存格。
回溯：嘗試將數字 1-9 放入空白儲存格中，使用 is_valid 檢查有效性。

遞迴求解：遞迴嘗試求解棋盤。如果某個位置產生了解決方案，則會傳回已解決的棋盤。
回溯：如果放置沒有產生解決方案，則會重設儲存格並嘗試下一個數字。

結論

輔助函數對於數獨解算器的功能至關重要。 is_valid 函數確保遵循數獨規則，find_empty 幫助定位下一個要填入的儲存格，solve 使用遞歸回溯來找到解決方案。了解這些輔助函數可以深入了解以程式方式解決數獨謎題背後的邏輯。

以上是用 Python 求解數獨的詳細內容。更多資訊請關注PHP中文網其他相關文章！