51.N皇后

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import copy
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        nums = [ [ '.' for _ in range(n)] for _ in range(n) ]
        result = []
        def check_legal(nums,row,col) ->bool:
            # 查上方
            for i in range(0,row):
                if nums[i][col]=="Q": return False
            # 查左上角
            i,j = row-1,col-1
            while i>=0 and j>=0:
                if nums[i][j]=="Q": return False
                i -= 1
                j -= 1
            # 查右上角
            i,j = row-1,col+1
            while i>=0 and j<=n-1:
                if nums[i][j]=="Q": return False
                i -= 1
                j += 1
            return True 
        def split_tree(nums,row=0)->List[List[str]]:
            if row==n:
                # print(nums)
                return result.append(copy.deepcopy(nums))
            for j in range(0,n):
                if check_legal(nums,row,j)==False: 
                    continue  
                nums[row][j] = "Q"
                split_tree(nums,row+1)
                nums[row][j] = "." 

            # 我这里绕了一下，因为我不小心看错题目了，用了两个list，这里转回str。
            for values in result:
                for index,value in list(enumerate(values)):
                    # print(value)
                    values[index] = ''.join(value)
            return result 
        return split_tree(nums,0)