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)