N皇后问题求解算法：Python实现与优化

class Solution: def solveNQueens(self, n: int) -> List[List[str]]: # 判断当前位置是否可以放置皇后 def is_valid(board, row, col): # 检查列是否有皇后 for i in range(n): if board[i][col] == 'Q': return False # 检查左上方是否有皇后 i, j = row - 1, col - 1 while i >= 0 and j >= 0: if board[i][j] == 'Q': return False i, j = i - 1, j - 1 # 检查右上方是否有皇后 i, j = row - 1, col + 1 while i >= 0 and j < n: if board[i][j] == 'Q': return False i, j = i - 1, j + 1 return True

    # 将棋盘转换成输出格式
    def board_to_list(board):
        res = []
        for row in board:
            res.append(''.join(row))
        return res
    
    # 深度优先搜索
    def dfs(board, row, res):
        # 搜索到最后一行，将当前解法加入结果列表
        if row == n:
            res.append(board_to_list(board))
            return
        for col in range(n):
            if is_valid(board, row, col):
                board[row][col] = 'Q'
                dfs(board, row + 1, res)
                board[row][col] = '.'
    
    # 初始化棋盘，全部置为'.'
    board = [['.' for _ in range(n)] for _ in range(n)]
    res = []
    dfs(board, 0, res)
    return res