所謂leetcode hard級(jí)別的回溯問題
回溯問題其實(shí)就是一個(gè)模板題悲立，都是通過【帶狀態(tài)恢復(fù)的dfs】實(shí)現(xiàn)
我們知道回溯的模板如下
def backTrack(visited_path, choice_list, global_result, target):
# visited_path表示當(dāng)前的問題階段坷檩，choice_list表示當(dāng)前問題面臨的可選項(xiàng)尘惧，target出現(xiàn)表示問題無需繼續(xù)向下搜索棚饵，這時(shí)result結(jié)算可行解漆改，
# 遞歸出口
if visited_path meets target:
update global_result
return
# 嘗試每一個(gè)【當(dāng)前可行】的選擇
for c in choice_list:
# 2.更新問題狀態(tài): 必須包含3項(xiàng)沾瓦，visited_path+choice_list+target
visited_path.add(c)
new_choice_list = choice_list.remove(c)
update target
# 3.遞歸
backTrack(visited_path, new_choice_list, global_result, target)
# 4.狀態(tài)復(fù)原
visited_path.remove(c)
reset target
hard題難在什么地方呢满着？要說難，它就難在【當(dāng)前可行】的選擇需要滿足更為復(fù)雜的限制條件贯莺，也僅此而已了
只要我們翻譯好限制條件风喇，將限制條件用code正確表示出來，其實(shí)就還是板子題
例1 leetcode51 N皇后
給定一個(gè)整數(shù) n缕探，返回所有不同的 n 皇后問題的解決方案魂莫，要求皇后彼此不能相互攻擊，也就是說：任何兩個(gè)皇后都不能處于同一條橫行爹耗、縱行或斜線上耙考。
每一種解法包含一個(gè)明確的 n 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位潭兽。
示例：
輸入：4
輸出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解釋: 4 皇后問題存在兩個(gè)不同的解法倦始。
思路：
假定我們從上到下逐行放置一個(gè)皇后，現(xiàn)在我們?cè)诘趇行要放置一個(gè)皇后山卦，那么當(dāng)前可行的選擇有哪些呢鞋邑？第i行的哪幾個(gè)位置能放呢？解決了這個(gè)問題就好账蓉。我們知道枚碗，前i-1行已經(jīng)放置的皇后所在的行、列铸本、斜線都不能放肮雨，認(rèn)為是前皇后勢力覆蓋區(qū)域
那么，我們維護(hù)一個(gè)dict來記錄整個(gè)棋盤的每個(gè)方格的勢力值箱玷，初始化為0怨规。
- 我們只能在勢力值為0的方格放置新的皇后
- 每放置一個(gè)皇后陌宿，則她所在的行、列椅亚、斜線的各個(gè)方格的勢力值+1
- 每次回溯撤回一個(gè)皇后限番，則她所在的行、列呀舔、斜線的各個(gè)方格的勢力值-1
這樣，我們把【已放置皇后所在的行扩灯、列媚赖、斜線都不能放新皇后】這個(gè)限制條件很好地翻譯成了代碼形式來確定當(dāng)前可行的選擇，得解
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# 設(shè)置好規(guī)則珠插，【dfs】暴力嘗試所有解惧磺。如果能夠dfs到第n層的，說明整個(gè)路徑上的皇后位置合法捻撑，納入結(jié)果集磨隘。
# 用queen_pos list記錄可行的皇后位置；用字典invalid_pos記錄當(dāng)前不可放置的位置顾患，0可放番捂，非0不可放
queen_pos = list()
invalid_pos = dict()
for i in range(n):
for j in range(n):
invalid_pos[(i,j)] = 0
final_res = []
def helper(queen_pos, invalid_pos, row_index, final_res):
# 已經(jīng)到整個(gè)棋盤的n行，說明0-n-1行都放好了江解，結(jié)算并返回
if row_index == n:
temp = []
for p in queen_pos:
s = '.'*p[1] + 'Q' + '.'*(n-1-p[1])
temp.append(s)
final_res.append(temp)
return
for i in range(n):
pos = (row_index, i)
if invalid_pos[pos] == 0:
# 嘗試放一個(gè)皇后
queen_pos.append(pos)
## 更新不可放的位置 ##
additional_invalid_pos = []
for j in range(n):
# 同一行不可再放
additional_invalid_pos.append((row_index, j))
for j in range(n):
# 同一列不可再放
additional_invalid_pos.append((j, i))
s = row_index + i
delta = i - row_index
for j in range(n):
# 雙斜線不可再放
if n > s-j >= 0 : additional_invalid_pos.append((j, s-j))
if 0 <= j + delta < n: additional_invalid_pos.append((j, j+delta))
for ele in additional_invalid_pos:
invalid_pos[ele] += 1
## 更新不可放的位置设预，完畢 ##
# dfs
helper(queen_pos, invalid_pos, row_index+1, final_res)
# 狀態(tài)復(fù)原
queen_pos.pop()
for ele in additional_invalid_pos:
invalid_pos[ele] -= 1
helper(queen_pos, invalid_pos, 0, final_res)
return final_res
例2 leetcode 37. 解數(shù)獨(dú)
編寫一個(gè)程序，通過已填充的空格來解決數(shù)獨(dú)問題犁河。
一個(gè)數(shù)獨(dú)的解法需遵循如下規(guī)則：
數(shù)字 1-9 在每一行只能出現(xiàn)一次鳖枕。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次桨螺。
空白格用 '.' 表示宾符。
假設(shè)給定的數(shù)獨(dú)只有唯一解，且數(shù)獨(dú)棋盤為9 x 9規(guī)模
思路：
好了灭翔，又是翻譯復(fù)雜限制條件來確定當(dāng)前可行選擇的回溯問題
維護(hù)3個(gè)set row_d, col_d, block_d魏烫，對(duì)應(yīng)3個(gè)限制條件，記錄每行缠局、每列则奥、每塊當(dāng)前含有的數(shù)字
- 從上到下從左到右先遍歷一次數(shù)獨(dú)棋盤，初始化3個(gè)set
- 從上到下從左到右再遍歷一次數(shù)獨(dú)棋盤狭园，
- 如果遇到數(shù)字读处，到下一格去
- 如果遇到空格，從1到9中選出不在3個(gè)set中的數(shù)字嘗試放置唱矛，期間更新set和恢復(fù)set即可
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# 維護(hù)3個(gè)set罚舱，記錄每行井辜、每列、每塊當(dāng)前含有的數(shù)字
row_d, col_d, block_d = dict(), dict(), dict()
for i in range(9):
row_d[i] = set()
col_d[i] = set()
block_d[i] = set()
# 初始化這3個(gè)set
for i in range(9):
for j in range(9):
row_d[i].add(board[i][j])
col_d[j].add(board[i][j])
block_d[(i//3)*3+j//3].add(board[i][j])
def backTracking(board, i, j, row_d, col_d, block_d) -> bool:
# 遞歸出口管闷，填到棋盤外的第九行粥脚，，包个，
if i == 9:
return True
# 碰到數(shù)字格
if board[i][j] != '.':
if j == 8:
res = backTracking(board, i+1, 0, row_d, col_d, block_d)
if res:
return res
else:
res = backTracking(board, i, j+1, row_d, col_d, block_d)
if res:
return res
# 碰到空格
else:
for ii in range(1, 10):
ele = str(ii)
if ele not in row_d[i] and ele not in col_d[j] and ele not in block_d[(i//3)*3+j//3]:
# 修改狀態(tài)
board[i][j] = ele
row_d[i].add(board[i][j])
col_d[j].add(board[i][j])
block_d[(i//3)*3+j//3].add(board[i][j])
# dfs
if j == 8:
res = backTracking(board, i+1, 0, row_d, col_d, block_d)
if res:
return res
else:
res = backTracking(board, i, j+1, row_d, col_d, block_d)
if res:
return res
# 恢復(fù)狀態(tài)
row_d[i].remove(board[i][j])
col_d[j].remove(board[i][j])
block_d[(i//3)*3+j//3].remove(board[i][j])
board[i][j] = '.'
return False
backTracking(board, 0, 0, row_d, col_d, block_d)
