用回溯法实现n皇后问题，python实现

好的，下面是 Python 实现的代码：

def solveNQueens(n):
    def could_place(row, col):
        return not (cols[col] + hill_diagonal[row - col] + dale_diagonal[row + col])

    def place_queen(row, col):
        queens.add((row, col))
        cols[col] = 1
        hill_diagonal[row - col] = 1
        dale_diagonal[row + col] = 1

    def remove_queen(row, col):
        queens.remove((row, col))
        cols[col] = 0
        hill_diagonal[row - col] = 0
        dale_diagonal[row + col] = 0

    def add_solution():
        solution = []
        for _, col in sorted(queens):
            solution.append('.' * col + 'Q' + '.' * (n - col - 1))
        output.append(solution)

    def backtrack(row = 0):
        for col in range(n):
            if could_place(row, col):
                place_queen(row, col)
                if row + 1 == n:
                    add_solution()
                else:
                    backtrack(row + 1)
                remove_queen(row, col)

    cols = [0] * n
    hill_diagonal = [0] * (2 * n - 1)
    dale_diagonal = [0] * (2 * n - 1)
    queens = set()
    output = []
    backtrack()
    return output

这里用到了回溯算法解决 N 皇后问题，时间复杂度为 O(N!)，空间复杂度为 O(N)。