【基础算法】回溯法与八皇后问题

回溯法是一种常用的解决问题的算法，它通常用于在一个大的搜索空间中找到所有符合要求的解。它的基本思想是从问题的可能解开始搜索，如果发现当前的解不符合要求，就回溯到上一个分支点，继续搜索其他可能的解。

八皇后问题是回溯法的一个经典应用，它是指在一个 8x8 的棋盘上放置 8 个皇后，使得每个皇后都不会互相攻击（即不在同一行、同一列、同一对角线上）。这个问题可以用回溯法来解决，具体步骤如下：

1. 定义一个数组 queens 存放每个皇后的位置，初始化为 -1。
2. 从第一行开始，对于每个列位置，判断该位置是否可以放置皇后。
3. 如果可以放置，将该位置的值存入 queens 数组中，并递归处理下一行。
4. 如果下一行没有可行解，就回溯到上一行，重新处理该行的下一个位置。
5. 如果所有列位置都尝试过了，但是没有找到可行解，就回溯到上一行。

具体的代码实现可以参考以下示例：

def solve_n_queens(n):
    queens = [-1] * n
    res = []

    def is_valid(row, col):
        for i in range(row):
            if queens[i] == col or \
               queens[i] - i == col - row or \
               queens[i] + i == col + row:
                return False
        return True

    def backtrack(row):
        if row == n:
            res.append(queens[:])
            return

        for col in range(n):
            if is_valid(row, col):
                queens[row] = col
                backtrack(row + 1)
                queens[row] = -1

    backtrack(0)
    return res

以上代码定义了两个函数，solve_n_queens(n) 函数用于解决 n 皇后问题，is_valid(row, col) 函数用于判断当前位置是否可以放置皇后。其中 queens 数组存储每个皇后的位置，-1 表示该行还没有放置皇后。

回溯函数 backtrack(row) 用于搜索当前行可行的位置，如果找到可行解则递归处理下一行，否则回溯到上一行。当搜索到最后一行时，将当前的解存入 res 数组中。

最后，调用 solve_n_queens(n) 函数即可得到所有符合要求的解。