今天是紀錄LeetCode解題的第三十七天
是一題困難題

第三十七題題目：Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The ' . ' character indicates empty cells.

寫程式來填滿所有空格以解數獨

需滿足以下規則：

1. 每行必須包含不重複的數字 1-9
2. 每列必須包含不重複的數字 1-9
3. 3x3九宮格中必須包含不重複的數字 1-9

' . '代表空格

解題思路

我們遍歷整個數獨，碰到空白格就去檢查該行、列、九宮格內可以填入哪些數字並儲存起來，然後我們要找出該空白格可以填入的數字是最少的，先從這個最少的空白格去填入數字(這題需要做這個步驟「剪枝」，如果只是遇到空格就填入可能的數字，直到還沒解完數獨就有空白格無法填入數字就回溯的做法的話，需要執行1640762次，會直接TLE，而剪枝的話只需執行4259次)，假設填完一個數字後，再進入方法做上述同樣的事情，那如果碰到可以填入的數字都已經填完，但還沒解完數獨，就回溯(表示我們假設可填入的數字是錯誤的)

主要步驟概念

1. 找空格
2. 用 findPossibleNum 得到可以填入的數字
3. 嘗試每個數字：
   • 填入數獨
   • 遞迴解剩下的數獨
   • 若失敗 → 回溯
4. 若棋盤無空格 → 成功，返回 True
5. 若某格無候選 → 返回 False（剪枝）

程式碼

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        backtracking(board)
def backtracking(board):
    min_candidates = 9
    next_ceil = None
    for i in range(9):
        for j in range(9):
            if board[i][j] == ".":
                candidates = findPossibleNum(i,j,board)
                if len(candidates) < min_candidates:
                    min_candidates = len(candidates)
                    next_ceil = (i,j)
                if min_candidates == 1:
                    break
        if min_candidates == 1:
            break
    if next_ceil is None:
        return True #沒有空格了，已解完數獨
    row,col = next_ceil
    for num in findPossibleNum(row,col,board):
        board[row][col] = str(num) #嘗試填入數字
        if backtracking(board): #填完後繼續找下一個要填入數字的地方 #返回到這裡會是False
            return True #如果上一輪遞迴已經回傳True，表示數獨已完成，那就不用再繼續找下一個空格了
        board[row][col] = "." #如果上一個填入的數字最後返回False的話，就回溯剛才填入的數字
    return False #如果上面的num抓不到可以填入的數字，就返回

def findPossibleNum(row,col,board):
    possible = set(range(1, 10))
    for i in range(9):
        if board[row][i] != ".":
            possible.discard(int(board[row][i]))
        if board[i][col] != ".":
            possible.discard(int(board[i][col]))
    start_row = (row // 3) * 3
    start_col = (col // 3) * 3
    for i in range(start_row,start_row + 3):
        for j in range(start_col,start_col + 3):
            if board[i][j] != ".":
                possible.discard(int(board[i][j]))
    return possible