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

Posted on by

1. 引言

本文為介紹流行的數獨遊戲的系列文章中的第一篇。更具體地說，我們如何構建一個腳本來解決數獨難題，本文的重點在於介紹用於構建數獨求解器的回溯算法。

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

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

2.描述數獨九宮格

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

  • 空的單元格cell初始化為默認值0。
  • 維持數獨謎題數字值的數據類型是一個 9×9 大小的二維列表。

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

# 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數獨求解的資料請關註WalkonNet其它相關文章！

推薦閱讀：