1. 引言

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

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

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

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

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

• 空的單元格cell初始化為默認(rèn)值0。
• 維持?jǐn)?shù)獨(dú)謎題數(shù)字值的數(shù)據(jù)類型是一個(gè) 9x9 大小的二維列表。

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

# 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

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

3.尋找下一個(gè)空子單元格

函數(shù)findEmpty() 函數(shù)的操作更加簡(jiǎn)單：對(duì)初始化后的九宮格作為參數(shù)傳遞，然后該遍歷該九宮格中每一個(gè)子單元格cell，直到找到返回的第一個(gè)空的子單元格。如果沒(méi)有找到空的子單元格，這表明我們的問(wèn)題已解決，因此它返回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è)置值的合法性

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

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

如果我們?cè)O(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

以下是通過(guò)isValid() 函數(shù)中描述的條件后成功插入新值的動(dòng)態(tài)示例：

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

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

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

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

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

正如我們?cè)谏厦娴氖纠锌吹降哪菢樱撍惴ㄓ糜行?shù)字填充空子單元格cell，直到出現(xiàn)死胡同；然后它回溯，直到重新迭代該過(guò)程。

6. 性能表現(xiàn)

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

我們使用上述代碼，來(lái)解決歐拉計(jì)劃的第96題中的50道數(shù)獨(dú)題目，運(yùn)行時(shí)間為：

The execution time of above program is : 23.56185507774353 s

好吧，確實(shí)有點(diǎn)慢。我們后面再來(lái)開篇講解數(shù)獨(dú)算法的優(yōu)化。

7. 總結(jié)

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

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

最新評(píng)論