回溯法

回溯法是一种搜索算法，常用于解决组合优化问题和枚举问题等。以下是关于回溯法的详细介绍：

基本概念

  • 解空间：回溯法通常用于求解问题的所有可能解，这些解构成一个解空间。解空间可以用树或图的结构来表示，其中每个节点代表一个部分解。
  • 约束条件条件：在搜索解空间的过程中，需要根据问题的约束条件来判断一个部分解是否有可能扩展为一个完整的可行解。
  • 递归和回溯：回溯法通常使用递归的方式来遍历解空间树。在递归的过程中，当发现当前的部分解不满足约束条件或者不可能得到更优的解时，就进行回溯，即撤销上一步的选择，尝试其他的选择。

算法步骤

  • 定义问题的解空间：确定问题的解可以表示为什么形式，以及所有可能的解构成的空间结构。
  • 确定状态空间树的结构：根据问题的特点构建状态空间树，树的节点代表问题的部分解，从根节点到叶子节点的路径代表一个完整的解。
  • 深度优先搜索：从根节点开始，以深度优先的方式搜索状态空间树。在搜索过程中，根据约束条件判断每个节点是否可行，如果可行则继续向下搜索，否则回溯到上一层。
  • 剪枝操作：在搜索过程中，利用约束条件进行剪枝，即剪掉那些不可能产生可行解或最优解的子树，以提高算法的效率。
  • 记录解：当搜索到叶子节点时，如果该叶子节点代表的解满足问题的要求，则将其记录下来。

N皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def isLineAvailable(arr, i, j, idx, idy):
    x, y = i, j
    avail = True
    while 0 <= x < len(arr[i]) and 0 <= y < len(arr[i]):
        if x != i and y != j and arr[x][y] == "Q":
            avail = False
        x += idx
        y += idy
    return avail

def isNodeAvailable(arr, i, j):
    available = True
    for (idx, item) in enumerate(arr[i]):
        if item == "Q" and idx != j:
            available = False
    for idx in range(len(arr[i])):
        if idx != i and arr[idx][j] == "Q":
            available = False
    for idx, idy in [(-1, -1), (1, 1), (-1, 1), (1, -1)]:
        if not isLineAvailable(arr, i, j, idx, idy):
            available = False
            break
    return available

def doRecord(arr):
    res = []
    for line in arr:
        res.append("".join(line))
    return res

def placeQ(arr, i, result):
    if i == len(arr):
        result.append(doRecord(arr))
        return
    for j in range(len(arr)):
        if isNodeAvailable(arr, i, j):
            arr[i][j] = "Q"
            placeQ(arr, i + 1, result)
            arr[i][j] = "."

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        arr = [["." for i in range(n)] for j in range(n)]
        result = []
        placeQ(arr, 0, result)
        return result