# Leetcode 51

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.anss = []
        ans = [0] * n
        col = [False] * n
        topRight = [False] * (2 * n - 1)
        topLeft = [False] * (2 * n - 1)
        self.search(0, n, ans, col, topRight, topLeft)
        res = []
        for a in self.anss:
            res.append([])
            for c in a:
                s = ["."] * n
                s[c] = "Q"
                res[-1].append("".join(s))
        return res
        
    def search(self, cur, n, ans, col, topRight, topLeft):
        if cur == n:
            self.anss.append(ans.copy())
            return
        
        for i in range(n):
            if col[i]:
                continue
            if topRight[cur + i]:
                continue
            if topLeft[i - cur + n - 1]:
                continue
            col[i] = True
            topRight[cur + i] = True
            topLeft[i - cur + n - 1] = True
            ans[cur] = i
            self.search(cur + 1, n, ans, col, topRight, topLeft)
            col[i] = False
            topRight[cur + i] = False
            topLeft[i - cur + n - 1] = False