N皇后¶

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:

        def gen_board(queens):
            """格式化输出"""
            board = ["." * n] * n
            for i, q in enumerate(queens):
                board[i] = board[i][:q] + "Q" + board[i][q + 1 :]
            return board

        def backtrack(row):
            """回溯搜索"""
            nonlocal columns, diag1, diag2, queens, sol # 外部变量
            # 递归出口
            if row == n:
                board = gen_board(queens)
                sol.append(board)
            else:
                for i in range(n):
                    # 不满足条件的情况下就跳过这个位置
                    if i in columns or row - i in diag1 or row + i in diag2:
                        continue

                    # 记录答案
                    queens[row] = i

                    # 记录已经被占据的地方
                    columns.add(i)
                    diag1.add(row - i)
                    diag2.add(row + i)

                    # 压栈
                    backtrack(row + 1)

                    # 出栈
                    columns.remove(i)
                    diag1.remove(row - i)
                    diag2.remove(row + i)

        columns = set()
        diag1 = set()
        diag2 = set()
        sol = []
        queens = [-1] * n
        backtrack(0)
        return sol