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

Posted on by

1. 引言

本文是數獨遊戲問題求解的第二篇，在前文中我們使用回溯算法實現瞭最簡單版本的數獨遊戲求解方案。本文主要在前文解決方案的基礎上，來思考如何通過改進來提升數獨問題求解算法的性能。

閑話少說，我們直接開始吧。 ：）

2. 前文回顧

我們首先來回顧下前文的回溯算法，如下圖示：

在前文中，我們引入瞭回溯算法來對數獨問題求解，通過迭代每個子單元格cell的所有可能取值來暴力解決該問題，直到引入數獨九宮格中的新值與屬於同一行，列或block塊的子單元格中確定值之間沒有沖突為止。這種解決方案雖然可以有效解決該問題，但是它絕對不是最佳的解決方案，因為它沒有合理利用數獨九宮格中提供的附加先驗信息。下面，我們來一步步對前文算法進行優化吧。。。

3. 減少非比要的迭代次數

優化上述算法的第一個想法來自於這樣的觀察，我們的算法按順序迭代所有數字1到9，直到它找到一個與已經包含相同值的同一行，列或block塊中的另一個單元格不沖突的值。但是，數獨九宮格中一些確定值會已經為我們提供瞭一些信息，說明哪些數字不可能添加到某個子單元格cell中。

# 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

我們優化的思路是首先掃描我們的數獨九宮格，將每個子單元格的所有可能的合法候選值保存在內存中然後再逐個迭代它們，而不是迭代所有數字。參考下圖,演示瞭數獨九宮格的 2 個子單元格的候選值的集合。正如我們的遊戲規則所暗示的那樣，每行，每列和每個block塊不能包含相同的數字，因此在屬於給定子單元格的同一行，列和所屬block塊的單元格中已經確定的所有數字都被排除在外。

既然有瞭優化思路,那麼我們接下來就可以來用代碼實現上述想法啦.

3.1 生成候選值字典

接著我們需要一個數據結構(這裡我們選用字典)來保存每個子單元格的候選值列表,該函數通過遍歷整個九宮格中空的子單元格並調用我們的allowedValues()函數來返回子單元格的候選值列表.

樣例代碼如下:

# Store in a dictionary the legitimate 
# values for each individual cell
def cacheValidValues(board):
    cache = dict()
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                cache[(i,j)] = allowedValues(board,i,j)
    return cache

3.2 生成候選值列表

在上小節中的allowValues() 函數與我們在前篇文中看到的isValid() 函數具有類似的邏輯，但在本例中，它返回值為每個子單元格所提取到的合法數字的列表。

樣例代碼如下:

def allowedValues(board,row,col):

    numbersList = list()

    for number in range(1,10):

        found = False
        # Check if all row elements include this number
        for j in range(9):
            if board[row][j] == number:
                found = True
                break
        # Check if all column elements include this number
        if found == True:
            continue
        else:
            for i in range(9):
                if board[i][col] == number:
                    found = True
                    break

        # Check if the number is already included in the block
        if found == True:
            continue
        else:
            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] == number:
                        found = True
                        break
        if found == False:
            numbersList.append(number)
    return numbersList

3.3 函數調用

有瞭我們的單元格候選值緩存字典，下面我們準備測試該方案是否會顯著提高我們的程序性能。

為此我們還需要將 solve() 函數替換為一個新的函數solveWithCache()，該函數隻迭代每個子單元格cell的合法值列表，而不是所有數字 1–9。

代碼如下:

def solveWithCache(board, cache):
    blank = findEmpty(board)
    if not blank:
        return True
    else:
        row, col = blank

    for value in cache[(row,col)]:
        if isValid(board, value, blank):
            board[row][col] = value

            if solveWithCache(board, cache):
                return True

            board[row][col] = 0
    return False

在實現所有改動後測試我們的代碼為我們提供瞭所需的結果，與我們的第一個版本相比，跑同樣50組測試用例執行時間明顯縮短：

The execution time of above program is : 15.41820478439331 s

4. 總結

本文為數獨遊戲求解的第二篇,主要基於第一篇的回溯思想來思考如何利用數獨九宮格的先驗思想來減少回溯的迭代次數,進而提升算法提升效率,並給出瞭完整代碼實現.

到此這篇關於使用Python進行數獨求解詳解(二)的文章就介紹到這瞭,更多相關Python數獨求解內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：