使用Python進行數獨求解詳解(一)

2022-02-19 16:00:17

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

好吧，確實有點慢。我們後面再來開篇講解數獨演演算法的優化。

7. 總結

本文講解了數獨遊戲的相關規則，以及如何在Python中利用回溯思想來一步一步解決數獨問題，並給出了完整的實現。

以上就是使用Python進行數獨求解詳解(一)的詳細內容，更多關於Python數獨求解的資料請關注it145.com其它相關文章！