题解 | #N皇后问题#

from math import fabs
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 the n
# @return int整型
#
class Solution:
    def Nqueen(self , n: int) -> int:
        # write code here
        # 每行有且只有一个数，每列有且只有一个数，每次选中一个位置，这个位置的8个方向的位置都不能被选择
        # 从第一行第一列(i=0,j=0)的位置开始遍历，从二行中找一个元素不能选择i=0,j=0，且i=j的数，将其加入到列表中
        # 循环操作，从第三行中找，如果找不到即在第三行中没有满足要求的位置坐标，则返回上一层找第二层中其他符合条件的位置
        dp_list = [[] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                dp_list[i].append([i,j])
        
        tmp = []  #记录皇后的位置，数组的第一个值
        count = []
        def isvalid(arr,tmp):   
            for i in range(len(tmp)):
                if arr[0]==tmp[i][0] or arr[1] == tmp[i][1] or abs(tmp[i][0]-arr[0])==abs(tmp[i][1]-arr[1]):
                    return False
            return True

        def dfs(dp_list,tmp):
            if not dp_list :
                if len(tmp)==n:
                    count.append(1)
                return True
            else:
                for arr in dp_list[0]:
                    if isvalid(arr,tmp):
                        dfs(dp_list[1:],tmp+[arr])

        
        dfs(dp_list,tmp)
        return (sum(count))

写了两个半小时，主要卡在了怎么判断一个两个数是不是在同一列、同一行或者同一个斜线上，判断方式是：记录每一次皇后的位置，然后遍历所有皇后的位置，只要新的位置和列表里面任意的横坐标、纵坐标相同或者是满足斜率的关系，就输出True，否则输出False。