Leetcode 51. N-Queens

参考别人的算法做出了n皇后，开心。n皇后本质是求矩阵中如何放棋子，使每行每列，斜着的没有同时放两颗棋子。
用一维数列记录棋子的位置，例如 [1,2,3,0]就表示4*4的期盼中，第一行放在第一列，第二行放第二列，第三行放第三列，第四行放第零列。然后用dfs和backtracking去放每一行，直到放到最后一行。
python代码：

class Solution:
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        pos = [-1] * n
        usedcol = set()
        useddia = set()
        output = []
        self.dfs(n, pos, usedcol, useddia, output, 0)
        res = []
        for i in range(len(output)):
            res.append([])
            for j in output[i]:
                string = ['.']*n
                string[j] = 'Q'
                res[i].append(''.join(string))
        return res
    
    def dfs(self, n, pos, usedcol, useddia, output, index):
        if index >= n:
            output.append(list(pos))
            return
        for i in range(n):
            if i not in usedcol and not self.isdia(index, i, useddia):
                pos[index] = i
                usedcol.add(i)
                useddia.add((index, i))
                self.dfs(n, pos, usedcol, useddia, output, index+1)
                usedcol.remove(i)
                useddia.remove((index, i))
        return
    def isdia(self, i, j, useddia):
        for pos_x, pos_y in useddia:
            if abs(i - pos_x) == abs(j - pos_y):
                return True
        return False