51. N-Queens 八皇后问题

记得大二的时候上数据结构这门课就听过这门课，记得是当时的一个作业题目。
问题的核心是这里的is_valid函数，用于判断如果将第row行的皇后放在第column列是否合法(从row-1行到第0行依次判断)

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def printN():
            solution = []
            for i in range(n):
                tmp = ['.']*n
                tmp[result[i]] = 'Q'
                tmp = ''.join(tmp)
                solution.append(tmp)
            ret.append(solution)
        
        def cal8queens(row):
            if row == n:
                printN()
            for column in range(n):
                if is_valid(row, column, n, result):
                    result[row] = column
                    cal8queens(row+1)
        
        def is_valid(row, column, n, result):
            leftup = column - 1
            righttop = column + 1
            for i in range(row-1, -1, -1):
                if result[i] == column:
                    return False
                if leftup >= 0 and result[i] == leftup:
                    return False
                if righttop < n and result[i] == righttop:
                    return False
                leftup -= 1
                righttop += 1
            return True
        
        result = [-1]*n
        ret = []
        cal8queens(0)
        return ret