1. 引言

本文為介紹流行的數(shù)獨游戲的系列文章中的第一篇。更具體地說，我們?nèi)绾螛?gòu)建一個腳本來解決數(shù)獨難題，本文的重點在于介紹用于構(gòu)建數(shù)獨求解器的回溯算法。

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

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

2.描述數(shù)獨九宮格

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

• 空的單元格cell初始化為默認值0。
• 維持數(shù)獨謎題數(shù)字值的數(shù)據(jù)類型是一個 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.尋找下一個空子單元格

函數(shù)findEmpty() 函數(shù)的操作更加簡單：對初始化后的九宮格作為參數(shù)傳遞，然后該遍歷該九宮格中每一個子單元格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. 子單元格中設置值的合法性

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

• 同一行的任何子單元格cell都不應包含該數(shù)字
• 同一列的任何子單元格cell都不應包含該數(shù)字
• 該子單元格cell所在的block不應該包含該數(shù)字

如果我們設定的值滿足以上所有條件，該函數(shù)返回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() 函數(shù)中描述的條件后成功插入新值的動態(tài)示例：

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

5. 實現(xiàn)回溯算法

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

• 搜索下一個空的子單元格cell。如果沒有找到，那么我們已經(jīng)解決了這個難題；如果沒有，則轉(zhuǎn)到第 2 步。
• 通過迭代數(shù)字1-9 來猜測正確的數(shù)字，并參考已經(jīng)確定的數(shù)字來檢查它是否是一個合法的數(shù)字。
• 如果找到一個有效的數(shù)字，此時遞歸調(diào)用solve() 函數(shù)并猜測下一個空的子單元格cell。
• 如果數(shù)字1-9均無效，則將將子單元格cell的值重置為 0，并繼續(xù)迭代以查找下一個有效數(shù)字。

# 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

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

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

6. 性能表現(xiàn)

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

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

The execution time of above program is : 23.56185507774353 s

好吧，確實有點慢。我們后面再來開篇講解數(shù)獨算法的優(yōu)化。

7. 總結(jié)

本文講解了數(shù)獨游戲的相關(guān)規(guī)則，以及如何在Python中利用回溯思想來一步一步解決數(shù)獨問題，并給出了完整的實現(xiàn)。

以上就是使用Python進行數(shù)獨求解詳解(一)的詳細內(nèi)容，更多關(guān)于Python數(shù)獨求解的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論