怎么使用Python進行數獨求解

本篇內容主要講解“怎么使用Python進行數獨求解”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“怎么使用Python進行數獨求解”吧!

1. 引言

數獨這個名字的由來來自日語短語suuji wa dokushin ni kagiru，意思是“數字必須保持單一”。數獨游戲的流行也源于其規則的簡單性：數獨游戲要求在 9 x 9 空間的網格上進行數字填寫。在行和列中有 9 個“正方形”的格子block(由 3 x 3 個子單元格cell組成)。每一行、每一列、每一個block都需要填寫數字 1-9，行、列、block內不得重復任何數字。

好的，知道了上述數獨的規則，那么我們就來直接進入主體吧。 ：）

2.描述數獨九宮格

這一步主要為使用一組數字來初始化我們的九宮格。我們使用setBoard() 函數將輸入轉換為適合我們后續操作的數據類型。我們使用以下約定：

• 空的單元格cell初始化為默認值0。

• 維持數獨謎題數字值的數據類型是一個 9x9 大小的二維列表。

這里我們的輸入是一個多行字符串，我們將其處理成二維列表的形式。樣例代碼如下：

# Initialize a 2-D list with initial values described by the problem. 
# Returns board
def setBoard():
    board = list()
    sudokuBoard = '''
    200080300
	060070084
	030500209
	000105408
	000000000
	402706000
	301007040
	720040060
	004010003
	'''
    rows = sudokuBoard.split('\n')
    for row in rows:
        column = list()
        for character in row:
            digit = int(character)
            column.append(digit)
        board.append(column)
    return board

上述代碼運行后，如果展示在拼圖游戲中，他的樣子大概如下：

3.尋找下一個空子單元格

函數findEmpty() 函數的操作更加簡單：對初始化后的九宮格作為參數傳遞，然后該遍歷該九宮格中每一個子單元格cell，直到找到返回的第一個空的子單元格。如果沒有找到空的子單元格，這表明我們的問題已解決，因此它返回None。

樣例代碼如下：

# Find next empty space in Sudoku board and return dimensions
def findEmpty(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0 :
                return row,col
    return None

4. 子單元格中設置值的合法性

函數isValid()的操作是確認設定的數字是否是九宮格子單元格的有效選項。為了使設置的值滿足數獨九宮格的要求，該值的設置需滿足以下條件：

• 同一行的任何子單元格cell都不應包含該數字

• 同一列的任何子單元格cell都不應包含該數字

• 該子單元格cell所在的block不應該包含該數字

如果我們設定的值滿足以上所有條件，該函數返回True，否則返回False。代碼如下：

# Check whether a specific number can be used for specific dimensions
def isValid(board, num, pos):
    row, col = pos
    # Check if all row elements include this number
    for j in range(9):
        if board[row][j] == num:
            return False
    # Check if all column elements include this number
    for i in range(9):
        if board[i][col] == num:
            return False
    # Check if the number is already included in the block
    rowBlockStart = 3* (row // 3)
    colBlockStart = 3* (col // 3)

    rowBlockEnd = rowBlockStart + 3
    colBlockEnd = colBlockStart + 3
    for i in range(rowBlockStart, rowBlockEnd):
        for j in range(colBlockStart, colBlockEnd):
            if board[i][j] == num:
                return False

    return True

以下是通過isValid() 函數中描述的條件后成功插入新值的動態示例：

同時，若我們引入一個與九宮格數獨上已經存在的值沖突的數值，那么此時該值將不會被插入。圖例如下：

5. 實現回溯算法

下一個函數是我們整個解決方案的核心思想，這里引入了回溯思想，該算法的實現步驟如下：

• 搜索下一個空的子單元格cell。如果沒有找到，那么我們已經解決了這個難題；如果沒有，則轉到第 2 步。

• 通過迭代數字1-9 來猜測正確的數字，并參考已經確定的數字來檢查它是否是一個合法的數字。

• 如果找到一個有效的數字，此時遞歸調用solve() 函數并猜測下一個空的子單元格cell。

• 如果數字1-9均無效，則將將子單元格cell的值重置為 0，并繼續迭代以查找下一個有效數字。

# Solve Sudoku using backtracking
def solve(board):
    blank = findEmpty(board)
    if not blank:
        return True
    else:
        row, col = blank
    for i in range(1,10):
        if isValid(board, i, blank):
            board[row][col] = i

            if solve(board):
                return True

            board[row][col] = 0
    return False

由于遞歸理解起來不是那么直觀，不妨讓我們嘗試使用動態來將整個過程形象化：

正如我們在上面的示例中看到的那樣，該算法用有效數字填充空子單元格cell，直到出現死胡同；然后它回溯，直到重新迭代該過程。

6. 性能表現

上述我們的程序需要使用回溯算法來遍歷每個單元格的許多潛在值。這當然不是最優的解法，可以預想到我們的解決方法的性能會很慢。

我們使用上述代碼，來解決歐拉計劃的第96題中的50道數獨題目，運行時間為：

The execution time of above program is : 23.56185507774353 s

到此，相信大家對“怎么使用Python進行數獨求解”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！