---

前置

【算法】回溯算法專題① ——子集型回溯 python
【算法】回溯算法專題② ——組合型回溯 + 剪枝 python

---

小試牛刀

全排列 https://leetcode.cn/problems/permutations/description/

給定一個不含重復數字的數組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums = [0,1]
輸出：[[0,1],[1,0]]
示例 3：

輸入：nums = [1]
輸出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整數 互不相同

思路:

用一個vis標記數組:對已選的數字打上標記

題解:

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:n = len(nums)path = []ans = []vis = [0] * (n + 1)def dfs(i):if i == n:ans.append(path.copy())returnfor j in range(n):if not vis[j]:vis[j] = 1path.append(nums[j])dfs(i + 1)path.pop()vis[j] = 0 # 別忘了回溯時將vis打回0dfs(0)return ans

當然vis標記數組可以通過遞歸時傳入一個set參數代替

題解2:

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:n = len(nums)path = []ans = []def dfs(i, s): # s:setif i == n:ans.append(path.copy())returnfor x in s:path.append(x)dfs(i + 1, s - {x})path.pop()dfs(0, set(nums)) # 用集合可以 O(1)判斷元素是否在里面return ans

---

回歸經典

N皇后 https://leetcode.cn/problems/n-queens/description/

按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數 n ，返回所有不同的 n 皇后問題 的解決方案。

每一種解法包含一個不同的 n 皇后問題 的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇后和空位。

示例 1：

輸入：n = 4
輸出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解釋：如上圖所示，4 皇后問題存在兩個不同的解法。

示例 2：

輸入：n = 1
輸出：[[“Q”]]

提示：
1 <= n <= 9

思路:

同一對角線不能有多個皇后
（可以通過計算行號加或減列號來判斷）

題解code:

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:ans = []col = [0] * n  # col:列vis = [0] * n  # vis:標記數組diag1 = [0] * (2 * n)diag2 = [0] * (2 * n)# 分別表示兩個對角線def dfs(r):  # row:行if r == n:ans.append(["." * c + "Q" + "." * (n - 1 - c) for c in col])returnfor c in range(n):if not vis[c] and not diag1[r + c] and not diag2[r - c]:col[r] = cvis[c] = diag1[r + c] = diag2[r - c] = 1dfs(r + 1)vis[c] = diag1[r + c] = diag2[r - c] = 0dfs(0)return ans

---

舉一反三

小小變化一下,可以在對角線上,但有前提: 行號至少相差3

受傷的皇后 https://www.lanqiao.cn/problems/552/learning/

思路:

主要問題在于判斷相同對角線上行號之差
以(2, 2)為例：
【右對角線】 的點是 (1, 3)，【左對角線】 的點是 (3, 3)，
可以發現：
(2, 2)和 (1, 3)的橫坐標之差的絕對值=縱坐標之差的絕對值
同樣的(2, 2)和 (3, 3)亦是如此，
所以判斷兩點是否在同一對角線，
即判斷這兩點的橫縱坐標絕對值之差是否相等

題解code:

col = [0] * n
vis = [0] * n
diag1 = [0] * 2 * n
diag2 = [0] * 2 * ndef check(x, y):if not vis[y] and not diag1[x + y] and not diag2[x - y]:for i in range(x):if abs(i - x) == abs(col[i] - y) and abs(x - i) < 3:return 0return 1return 0def dfs(r):if r == n:global ansans += 1returnfor c in range(n):if check(r, c):col[r] = cvis[c] = diag1[r + c] = diag2[r - c] = 1dfs(r + 1)col[r] = 0vis[c] = diag1[r + c] = diag2[r - c] = 0n = int(input())
ans = 0
dfs(0)
print(ans)

---

總結

回溯法是一種通過嘗試每一種可能性來找到所有解的算法。對于N皇后問題，特別是帶有額外約束條件的問題（如本題中的皇后之間在同一條45度角斜線上至少相隔3行），回溯法是一個非常合適的選擇。

---

END
如果有更多問題或需要進一步的幫助，可以在評論區留言討論哦！
如果喜歡的話，請給博主點個關注 謝謝