37. Sudoku Solver

37. Sudoku Solver

這一題和 51. & 52. N Queens 的本質不會差太多。

如我在前言裡面所提到的，回溯法的本質和窮舉有關，思考排列組合窮舉的方式可以幫助我們思考回溯法如何的走訪。

以數獨的題目來說，我們要走訪的方式會是一列一列走，在走訪該列時，一行一行走，最後去判斷該位置可否放下符合數獨題目條件的數字，回朔法在某些題目中，可能會是這樣的出現。

for row in range(len(rows)):
    for col in range(len(cols)):
        backtrack(row, col)

可是這樣一定是不對的因為上面那樣子的走法的意思是，我要從一個座標平面中的每一個點都當作出發點，並在每個出發點都進行一次回溯法（ 79. Word Search 為例）。

而數獨的題目，(0, 0) 就可以當作出發座標，我們要走訪的是 (0, 0) -> (n-1, n-1) ，但是接下來要注意到的是，那我們到底要怎麼走？回溯法很多題目是在二維矩陣上面做搜尋的，通常我們並不在意搜尋的方向性，只要不越過邊界、符合題目條件，我們都可以往前移動後，再視情況進行回溯。

可是數獨的最好的方法其實是按照一個方向走下去，例如當人類在玩的時候，會盡可能地先完成一行、一列或一個正方形，這裡就是題目比較需要注意的地方，那就是我們要怎麼走訪數獨中的所有元素？

前面有提到走訪的方式會是一列一列走，在走訪該列時，一行一行走，因此在回溯法之中，我們每次走到該行的最後一個位置後，我們就要換下一列走，並且回到行的開頭，如果列可以成功走完了，代表目前數獨題目的所有位置都成功放對數字了，存在著解答，還有一個條件就是，如果走訪時遇到題目中已經先放置好的數字，那我們就繼續往下一個位置探索。

def backtrack(row, col):
    # 每次走到該行的最後一個位置後，我們就要換下一列走，並且回到行的開頭
    if col == 9:
        return backtrack(row + 1, 0)

    # 列可以成功走完了，代表目前數獨題目的所有位置都成功放對數字了，存在著解答。
    if row == 9:
        return True

    if board[i][j] != '.':
        return backtrack(i, j+1)

    # TODO

剩下問題的部分就是，如何驗證該位子可以放哪個數字？這個部分比較簡單，可以自行理解，接下來就是如何進行回溯法。

基本上就是看從 1 - 9 哪個數字可以放進去，可以放進去，就繼續搜索，不行就退回，不過有一個小地方要注意是這個題目有非常大的搜索空間，題目只問了提供一組解就好，所以要盡快的回覆答案。

class Solution:


    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        def isValid(row, col, num):
            # 驗證該行沒有重複元素
            for i in range(9):
                if board[row][i] == str(num):
                    return False
            # 驗證該列沒有重複元素
            for i in range(9):
                if board[i][col] == str(num):
                    return False
            # 驗證該方形沒有重複元素        
            for i in range(row//3*3, row//3*3+3):
                for j in range(col//3*3, col//3*3+3):
                    if board[i][j] == str(num):
                        return False
            return True

        def backtrack(row, col):

            if col == 9:
                return backtrack(row + 1, 0)

            if row == 9:
                return True

            if board[row][col] != '.':
                return backtrack(row, col+1)

            for num in range(1, 10):
                if isValid(row, col, num):
                    board[row][col] = str(num)
                    if backtrack(row, col+1):
                        return True
                    board[row][col] = '.'                    

            return False

        return backtrack(0, 0)