【每日一题】- 2019-08-12 八皇后问题

[azl397985856]

【每日一题】- 2019-08-12 八皇后问题

[3460741663]

认领

[azl397985856]

认领

done

[wjj31767]

python3

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        tmp = [-1] * n
        ct = set()
        res = []
        def dfs(n,tt,ct,i):
            # print(tt,ct,tmp)
            if tt == 0: 
                #print(ct,tmp)
                res.append([])
                for k in tmp:
                    res[-1].append('.' * (k) + 'Q' + '.' * (n - k - 1))
                return
            for j in range(n):
                if (i, j) not in ct:
                    tmp[i] = j
                    ctt = set()
                    for k in range(n):
                        if (i, k) not in ct:
                            ctt.add((i, k))
                        if (k, j) not in ct:
                            ctt.add((k, j))
                        if i + k < n and j + k < n and (i + k, j + k) not in ct:
                            ctt.add((i + k, j + k))
                        if i + k<n and j - k > -1 and (i + k, j - k) not in ct:
                            ctt.add((i + k, j - k))
                        if i - k > -1 and j + k < n and (i - k, j + k) not in ct:
                            ctt.add((i-k, j+k))
                        if i - k > -1 and j - k > -1 and (i - k, j - k) not in ct:
                            ctt.add((i - k, j - k))
                    # print(ct,ctt)
                    ct |= ctt
                    dfs(n, tt - 1, ct, i + 1)
                    tmp[i] = -1
                    ct -= ctt
            return
        dfs(n, n, ct, 0)
        return res