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

2022-02-19 16:00:04

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數獨求解內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！