8皇后问题回溯算法Python

8皇后问题是一个经典的问题，它的目标是在8x8的棋盘上放置8个皇后，使得每个皇后都不能互相攻击。回溯算法是一种常用的解决8皇后问题的方法。下面是Python代码实现：

class Solution:
    def __init__(self):
        self.res = []
        self.cols = set()
        self.pie = set()
        self.na = set()

    def solveNQueens(self, n: int) -> List[List[str]]:
        if n < 1:
            return []
        self._dfs(n, 0, [])
        return self.res

    def _dfs(self, n, row, cur_state):
        if row >= n:
            self.res.append(cur_state)
            return
        for col in range(n):
            if col in self.cols or row + col in self.pie or row - col in self.na:
                continue
            self.cols.add(col)
            self.pie.add(row + col)
            self.na.add(row - col)

            self._dfs(n, row + 1, cur_state + [col])

            self.cols.remove(col)
            self.pie.remove(row + col)
            self.na.remove(row - col)

在这段代码中，我们使用了一个递归函数 `_dfs`。对于每一行，我们尝试放置皇后在每一列中。如果当前位置不会与之前的皇后相互攻击，则将当前位置的列、撇和捺记录下来，然后递归到下一行。如果无法找到一个合法的位置，则回溯到上一行并且继续寻找其他的位置。