leetcode 51 N皇后问题

通过回溯方法解决，构建一棵树，然后根据N皇后不互相攻击的限制条件，不在同一行，同一列，以及同一对角线上，其中对角线注意是两个方向的。不过判断条件都是对应行列坐标作差绝对值相等。

这个题目自己随便改改，居然accepted了，开心，再去看看其他解法！

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def dfs(i,n,path,result):
            flag=[True,True,True,True]
            if i==n:
                strvalue=''
                res=[]
                for m in range(n):
                    for k in range(n):
                        if k==path[m]:
                            strvalue+='Q'
                        else:
                            strvalue+='.'
                    res.append(strvalue)
                    strvalue=''
                result.append(res)
                return 

            for j in range(n):
                flag=False
                if path:          
                    for index,item in enumerate(path):
                        if abs(j-item)==abs(i-index) or j==item:
                            flag=True
                            break
                    if not flag:
                        dfs(i+1,n,path+[j],result)

                else:
                    path.append(j)
                    dfs(i+1,n,path,result)
                    path.pop()


        result=[]
        dfs(0,n,[],result)
        return result

按照答案写了一遍，把判断是否N皇后的问题交给数组，把之前的列值，与坐标的加和和坐标的差值，都放入数组中，如果当前位置的坐标在对应的数组中，那么就不满足条件。
其中需要注意的是，左对角线上的坐标作差相等，右对角线上的坐标作和相等。
其中打印答案也封装在一个函数中。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def print_result(column):
            strvalue=''
            res=[]
            for m in range(len(column)):
                for k in range(len(column)):
                    if k==column[m]:
                        strvalue+='Q'
                    else:
                        strvalue+='.'
                res.append(strvalue)
                strvalue=''
            return res
        def dfs(i,n,column,diagonal_left,diagonal_right,result):

            if i==n:
                res=print_result(column)
                result.append(res)
                return 

            for j in range(n):

                if j  in column or i+1-j in diagonal_left or i+1+j  in diagonal_right:
                    continue
                else:
                    column.append(j)
                    diagonal_left.append(i-j+1)
                    diagonal_right.append(j+i+1)
                    dfs(i+1,n,column,diagonal_left,diagonal_right,result)
                    column.pop()
                    diagonal_left.pop()
                    diagonal_right.pop()

        result=[]
        dfs(0,n,[],[],[],result)
        return result