题解 | #N皇后问题#

#
# 
# @param n int整型 the n
# @return int整型
#
class Solution:
    def Nqueen(self , n ):
        num = [0 for i in range(n)]
        res = [0]
        mark = {}
        self.dfs(num,0,mark,res)
        return res[0]
    
    def dfs(self,num,i,mark,res):
        if i==len(num):
            res[0] += 1
            return 
        for j in range(len(num)):
            num[i] = j
            if self.valid(num,i,mark):
                mark[j] = i
                self.dfs(num,i+1,mark,res)
                mark[j] = -1
                
    def valid(self,num,i,mark):
        if mark.get(num[i],-1) > -1:
            return False
        for j in range(i-1,-1,-1):
            if (num[i]-num[j]== i-j) or (num[i]-num[j]==j-i) :
                return False
        return True