LC 51N 皇后N-Queens　困难

在 n×n 棋盘上放 n 个皇后使彼此互不攻击（不同行、列、对角线），返回所有解，Q 表示皇后、. 表示空位。

思路 按行回溯，用集合记录已占列、主对角线 row-col、副对角线 row+col；放满 n 行按列号生成棋盘串。O(n!)。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans, q = [], []
        cols, d1, d2 = set(), set(), set()

        def dfs(row):
            if row == n:
                ans.append(
                    ["." * c + "Q" + "." * (n - 1 - c)
                     for c in q])
                return
            for col in range(n):
                if (col in cols or row - col in d1
                        or row + col in d2):
                    continue
                cols.add(col)
                d1.add(row - col)
                d2.add(row + col)
                q.append(col)
                dfs(row + 1)
                cols.remove(col)
                d1.remove(row - col)
                d2.remove(row + col)
                q.pop()

        dfs(0)
        return ans