Leetcode 51. N-Queens [Python]

Leetcode 51. N-Queens [Python]

回溯法，当遍历到最后一行，此时的组合就可以被记录了。而如果不到的话，还需要为当前的行的queen选择合适的列。注意设置对脚线数组记录选定当前行当前列后，向左上的对角线和向右上的对角线，判断是否合法。其位置的计算是当前行数+选定列数，和总行数N-当前行数+选定列数。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = [False]*n
        udg = [False]*(2*n)
        dg = [False]*(2*n)
        res = []
        grid = [['.' for _ in range(n)] for _ in range(n)]
        
        def dfs(currow):
            if currow == n:
                tempres = []
                for i in range(n):
                    line = ''
                    for j in range(n):
                        line += grid[i][j]
                    tempres.append(line)
                res.append(tempres)
                return 
            else:
                for i in range(n):
                    if not col[i] and not udg[currow + i] and not dg[n - currow + i]:
                        col[i] = udg[currow + i] = dg[n - currow + i] = True
                        grid[currow][i] = 'Q'
                        dfs(currow + 1)
                        grid[currow][i] = '.'
                        col[i] = udg[currow + i] = dg[n - currow + i] = False
        dfs(0)
        return res