n皇后问题的回溯算法py

n皇后问题是一道经典的回溯算法问题，其目标是在一个nxn的棋盘上，放置n个皇后，使得它们不互相攻击。具体来说，皇后可以攻击同一行、同一列以及同一斜线上的任何棋子。下面是n皇后问题的回溯算法实现（Python语言）：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def is_valid(board, row, col):
            # 检查同一列是否有皇后
            for i in range(row):
                if board[i][col] == 'Q':
                    return False
            # 检查右上方是否有皇后
            for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
                if board[i][j] == 'Q':
                    return False
            # 检查左上方是否有皇后
            for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
                if board[i][j] == 'Q':
                    return False
            return True
        
        def backtrack(board, row):
            if row == n:
                res.append(list(board))
                return
            for col in range(n):
                if not is_valid(board, row, col):
                    continue
                board[row][col] = 'Q'
                backtrack(board, row+1)
                board[row][col] = '.'
                
        res = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        backtrack(board, 0)
        return res

其中，is_valid函数用于检查在row行col列上放置皇后是否合法，backtrack函数用于进行回溯搜索。这里我们使用一个二维数组board表示棋盘，其中'.'表示空位，'Q'表示皇后。在backtrack函数中，我们逐行搜索，在每一行中枚举每一个列，如果当前位置可以放置皇后，则在这个位置放置皇后，然后递归到下一行进行搜索。如果搜索到最后一行，则找到了一种合法的解。如果某一行中所有列都不能放置皇后，则回溯到上一行，重新枚举上一行的列。