【算法數據結構】leetcode37 解數獨

37. 解數獨 - 力扣（LeetCode）

題目描述：

題目要求每一行，每一列，每個3*3 的子框只能出現一次。每個格子的數字范圍1-9.

需要遍歷每個空格填入可能的數字，并驗證符合規則。如果符合就填入，不符合就回溯。

解法：?

回溯算法通常用于解決這種需要試錯的問題。當發現當前路徑無解時候，返回上一步重新選擇。

需要遍歷每個空格，找到需要填寫的空格，對每個空格嘗試填入1-9，檢查這個數字是否滿足行，列，子框的要求。如果滿足就填入這個數字，遞歸進行下一個空格，如果后續處理中，發現無法填入下去，就需要回溯。恢復這個空格的狀態，嘗試下一個可能的數字。

檢查某個數字是否可以填入當前位置

對于位置（i,i）需要檢查i 行，j 列，所在的子框是否有這個數字，屬于第幾個子框可以用 (i/3 )*3,(j/3 )*3來確定。i=4? ?4/3=1? ? 1*3=3?? ?,起始行是3 ，遍歷這個3*3的子框。

對于每個空格最多檢查1-9個數字。，每個數字需要檢查三個方向，最壞情況可能出現重復檢查。

優化方法

用哈希表或者數據記錄行，列，子框。已經出現的數字。用3個二維數組，記錄rowi 表示第i行是否存在數組num,colj 表示第j 列是否存在數據num,boxk 表示第k 個子框中是否存咋這個數字num,

k 可以通過? i//3*3 +j//3 來計算?

i=0 ,j=0? ?,k=0

i=3,j=3 ,k=4? 在第四個子框。

預處理這三個數組，遍歷整個數獨，對這個對每個非空的格子，將對應的行列，子框中蓋數字標記為存在。比如broad_i 為5 ，那么需要row_i? 設置為true ,col_j 設置為true ，box_k （k為子框的索引）設置為true。

對每個空格嘗試填入1-9 數字中的一個，

初始化? 9X10 數組其中索引 0不用?

步驟

1. 預處理三個數組row、col、box，記錄每個行、列、子框中已經存在的數字。

2. 收集所有需要填寫的空格的位置，存入一個列表spaces。

3. 編寫一個回溯函數，參數是當前處理到spaces中的第pos個位置。當pos等于spaces的長度時，說明已經填完所有空格，返回True。

4. 對于當前處理的空格位置(i,j)，嘗試填入1到9中的一個數字d。如果該數字滿足row[i][d]、col[j][d]、box[k][d]都為False，那么將該數字填入，并更新這三個數組的狀態。然后遞歸處理pos+1的位置。如果遞歸返回True，說明后續的填寫都成功，那么當前的選擇是正確的，直接返回True。如果遞歸返回False，則說明后續無法完成，需要回溯，恢復三個數組的狀態，并將board[i][j]恢復為'.'，然后嘗試下一個數字。

5. 如果所有數字都嘗試過且都不行，則返回False，觸發上一層遞歸的回溯。

這樣，當遞歸函數返回True時，說明已經找到解，此時board已經被正確填充。

    # 初始化 3個數組row = [[False] * 10 for i in range(9)]print(row)  # 每行十個元素col = [[False] * 10 for i in range(9)]box = [[False] * 10 for i in range(9)]

[[False, False, False, False, False, False, False, False, False, False],[False, False, False, False, False, False, False, False, False, False],[False, False, False, False, False, False, False, False, False, False],[False, False, False, False, False, False, False, False, False, False], 
[False, False, False, False, False, False, False, False, False, False],[False, False, False, False, False, False, False, False, False, False], 
[False, False, False, False, False, False, False, False, False, False], 
[False, False, False, False, False, False, False, False, False, False],[False, False, False, False, False, False, False, False, False, False]]

?遍歷數組填充已經有的數字 spaces 用于記錄空格的位置

# 遍歷整個數組 記錄每個行 ，列子框中已經存在的數字spaces = []for i in range(9):for j in range(9):if board[i][j] != '.':d = int(board[i][j])row[i][d] = Truecol[j][d] = Truek = (i // 3) * 3 + (j // 3)box[k][d] = True  # 第k 個箱子的d 是否存在# 保存空格的位置到spaceselse:spaces.append((i, j))print("空格的位置", spaces)

空格的位置 [(0, 2), (0, 3), (0, 5), (0, 6), (0, 7), (0, 8), (1, 1), (1, 2), (1, 6), (1, 7), (1, 8), (2, 0), (2, 3), (2, 4), (2, 5), (2, 6), (2, 8), (3, 1), (3, 2), (3, 3), (3, 5), (3, 6), (3, 7), (4, 1), (4, 2), (4, 4), (4, 6), (4, 7), (5, 1), (5, 2), (5, 3), (5, 5), (5, 6), (5, 7), (6, 0), (6, 2), (6, 3), (6, 4), (6, 5), (6, 8), (7, 0), (7, 1), (7, 2), (7, 6), (7, 7), (8, 0), (8, 1), (8, 2), (8, 3), (8, 5), (8, 6)]

d = int(board[i][j])? 填充的數字作為下標

? row：? row[i][d]=True

[[False, False, False, True（3）, False, True（5）, False, True（7）, False, False],[False, True（1）, False, False, False, True（5）, True（6）, False, False, True（9）],[False, False, False, False, False, False, True（6）, False, True（8）, True（9）], 
[False, False, False, True（3）, False, False, True（6）, False, True（8）, False],[False, True（1）, False, True（3）, True（4）, False, False, False, True（8）, False],[False, False, True（2）, False, False, False, True（6）, True（7）, False, False], 
[False, False, True（2）, False, False, False, True（6）, False, True（8）, False],[False, True（1）, False, False, True（4）, True（5））, False, False, False, True（9）],[False, False, False, False, False, False, False, True（7）, True（8）, True（9）]]

col : col[j][d]=true? ?縱坐標作為行 d作為列?

第一列? ?4 5? 6 7 8

?[False, False, False, False, True（4）, True（5）, True（6）, True（7）, True（8）, False]

[[False, False, False, False, True（4）, True（5）, True（6）, True（7）, True（8）, False], 
[False, False, False, True, False, False, True, False, False, True], 
[False, False, False, False, False, False, False, False, True, False],[False, True, False, False, True, False, False, False, True, False],[False, True, True, False, False, False, True, True, True, True], 
[False, False, False, True, False, True, False, False, False, True],[False, False, True, False, False, False, False, False, False, False], 
[False, False, False, False, False, False, True, True, True, False], 
[False, True, False, True, False, True, True, False, False, True]]

? ?box :? ? ? k = (i // 3) * 3 + (j // 3)
? ? ? ? ? ? ? ? box[k][d] = True ?# 第k 個箱子的d 是否存在

? 例如? board[4][3]=8? ?k=(4//3)*3 +(3//1) =4? 第4個子框? 第8個標記為true

[[False, False, False, True, False, True, True, False, True, True], 
[False, True, False, False, False, True, False, True, False, True],[False, False, False, False, False, False, True, False, False, False], 
[False, False, False, False, True, False, False, True, True, False],[False, False, True, True, False, False, True, False, True(8), False], 
[False, True, False, True, False, False, True, False, False, False],[False, False, False, False, False, False, True, False, False, False],[False, True, False, False, True, False, False, False, True, True], 
[False, False, True, False, False, True, False, True, True, True]]

定義回溯

# 定義回溯def backtrack(pos):print("pos", pos)if pos == len(spaces):  # 當pos 等于spaces長度時候說明已經填寫完 ，返回trueprint("結果", board)return Truei, j = spaces[pos]k = (i // 3) * 3 + (j // 3)for d in range(1, 10):  # 對這個位置嘗試填充1-9if not row[i][d] and not col[j][d] and not box[k][d]:  # 滿足為false 時候填入row[i][d] = Truecol[j][d] = Truebox[k][d] = Trueboard[i][j] = str(d)if backtrack(pos + 1):return True# 回溯row[i][d] = Falsecol[j][d] = Falsebox[k][d] = Falseboard[i][j] = '.'  # 恢復空格return Falsebacktrack(0)

代碼?

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""# 初始化三個數組row=[[False] *10 for _ in range(9)]col=[[False] *10 for _ in range(9)]box=[[False] *10 for _ in range(9)]spaces=[] # 記錄空格位置# 遍歷數組填充已經有的數字for i in range(9):for j in range(9):if board[i][j]!='.':d=int(board[i][j])row[i][d]=Truecol[j][d]=Truek=(i//3)*3+(j//3)box[k][d]=Trueelse:spaces.append((i,j)) # 記錄空格的坐標def  backtrack(pos):if pos ==len(spaces):#遍歷完了所有空格return Truei,j=spaces[pos] # 取出當前位置的空格坐標k=(i//3)*3+(j//3)for d in range(1,10):  # 嘗試對該位置填充1-9if row[i][d]==False and col[j][d]==False and box[k][d]==False:row[i][d]=Truecol[j][d]=Truebox[k][d]=Trueboard[i][j]=str(d)if backtrack(pos+1):return True#不滿足  回溯row[i][d]=Falsecol[j][d]=Falsebox[k][d]=Falseboard[i][j]='.' return Falsebacktrack(0)