題目描述

撰寫一個程式，通過已填充的空格來解決數獨問題，

一個數獨的解法需遵循如下規則：

數字 1-9 在每一行只能出現一次，

數字 1-9 在每一列只能出現一次，

數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次，

空白格用 '.' 表示，

一個數獨，

答案被標成紅色，

Note:

給定的數獨序列只包含數字 1-9 和字符 '.' ，

你可以假設給定的數獨只有唯一解，

給定數獨永遠是 9x9 形式的，

輸入格式：

[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

輸出格式：

[['5', '3', '4', '6', '7', '8', '9', '1', '2'], ['6', '7', '2', '1', '9', '5', '3', '4', '8'], ['1', '9', '8', '3', '4', '2', '5', '6', '7'], ['8', '5', '9', '7', '6', '1', '4', '2', '3'], ['4', '2', '6', '8', '5', '3', '7', '9', '1'], ['7', '1', '3', '9', '2', '4', '8', '5', '6'], ['9', '6', '1', '5', '3', '7', '2', '8', '4'], ['2', '8', '7', '4', '1', '9', '6', '3', '5'], ['3', '4', '5', '2', '8', '6', '1', '7', '9']]

難度分類

困難

演算法分析

這道題的的思考是在9x9的格子里面找到未填充的數字，比如當找到第n個未填充數字的格子，此時嘗試在里面填寫1可以保證當前行不沖突，列不沖突，小方塊不沖突，那么就在第n個格子里面填寫1，然后查看第n+1個格子，如果第n+1個格子發現填寫1-9都沖突，說明第n個格子填寫1的情況下無法找到解，此時我們需要回到第n個格子，填寫另外一個不沖突的數字，一直到能填充到第81個格子為止，

將上述解題思路轉換為代碼設計：

1. 定義col_used存盤對應列的值，col_used = [[[] for i in range(9)]]
2. 定義row_used存盤對應行的值，row_used=[[] for i in range(9)]
3. 定義box_used存盤對應小方塊的值，box_used = [[[], [], []] for i in range(3)]
4. 先遍歷九宮格將已填充的數字記錄進對應的行，列和小方塊
5. 通過定義i,j,遍歷遍歷九宮格，i代表行的index，j代表列的index，遍歷九宮格
6. 讀取當前九宮格的值，當當前九宮格的值為“”.“”的時候進行以下操作：

a)     從1-9九個數字中選擇一個數字（滿足與當前行的數字不沖突，列的數字不沖突，小方塊的數字不沖突）填入當前格子

b)     將這個填入的數字記錄進對應的行，對應的列，對應的小方塊

c)     判斷在當前格子填寫當前數字的基礎上接下來的格子填充能否填滿九宮格

d)     如果當前格子填寫數字的基礎上接下來的格子填充不能填滿九宮格，則需要取消當前數字的填充即①取消已填充的數字，②將已填充的數字從對應的行取出，③將已填充的數字從對應的列取出，④將已填充的數字從對應的小方塊取出，然后嘗試填入其他數字

e)     通過True和False判斷能否填寫九宮格，僅當第81個格子填寫完成（填寫的程序中已經進行了條件校驗）才回傳True，否則回傳False

1. 如果當前格子已有數字直接查看下一個格子

要點：如果下層回傳False,證明基于當前數字的填充沒有解，重置九宮格，行，列，小方塊狀態，選取新的數字填充

代碼示例

def solveSudoku(board):
    # 記錄某一列已使用的數字
    row_used = [[] for i in range(9)]
    # 記錄某一個小方塊已使用的數字
    col_used = [[] for i in range(9)]
    # 記錄某一行已使用的數字
    box_used = [[[], [], []] for i in range(3)]
    # 首先記錄九宮格中每行，每列，每一個小方塊中已使用的數字，以用于填充數字的時候檢查填充數字是否已被使用
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] in "123456789":
                row_used[i].append(board[i][j])
                col_used[j].append(board[i][j])
                box_used[i // 3][j // 3].append(board[i][j])
    def dfs(board, i=0, j=0):
        # 從左到右一個一個格子的遍歷九宮格，當某一行遍歷結束遍歷下一行的第一個格子
        if j == 9:
            i,j = i+1,0
        if i == 9:
            return True
        # 當遍歷到某一行為"."，即需要填充數字的時候，此時需要從1-9九個數字中選擇一個不沖突的數字填入當前格子
        if board[i][j] ==".":
            for num in ("123456789"):
                # 填充格子的前提條件是行不沖突（每一行每一個數字僅出現一次），列不沖突（每一列每一個數字僅出現一次），小方塊不沖突（每一小方塊每一個數字僅出現一次）
                if num not in row_used[i] and num not in col_used[j] and num not  in box_used[i // 3][j // 3]:
                    # 填充格子的同時需要將當前數字計入對應的行，列，小方塊，用于當其他格子填充的時候檢查是否行，列，小方塊沖突
                    row_used[i].append(num)
                    col_used[j].append(num)
                    box_used[i // 3][j // 3].append(num)
                    # 填充當前格子
                    board[i][j] = num
                    # 填充完成格子后此時檢查基于當前格子已經填充了數字的基礎上，填充下一個格子
                    if dfs(board,i,j+1):
                        return True
                    # 如果下一個格子填充失敗，1-9九個數字都有沖突，證明當前格子填充當前數字不能找到有效的解，此時需要找到另外一個數字來填充當前格子，因此需要將當前格子恢復原始狀態
                    # 恢復當前格子為未填充狀態
                    row_used[i].pop()
                    col_used[j].pop()
                    box_used[i // 3][j // 3].pop()
                    board[i][j] = "."
            return False
        # 當遍歷到某一格子為數字，直接查看下一個格子
        else:
            return dfs(board, i,j+1)
    dfs(board)
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
solveSudoku(board)
print(board)

考點分析

1. 矩陣的遍歷
2. 帶回傳值的回溯用法

標籤：其他

上一篇：ArrayList 與LinkedList 的區別及分別的優缺點

下一篇：圖論篇6——割點（關節點）