题解 | #N皇后问题#

class Solution:
    def Nqueen(self, n):
        def dfs(i, j, n):
            if i == n:
                self.res += 1
                return
            for j in range(j, n):
                if isok(i, j):
                    dp[i][j] = 'Q'
                    dfs(i + 1, 0, n)
                    dp[i][j] = '.'
        #用来判断上方、右上、左上方是否有Q，这里注意每次while后要重定义i,j
        def isok(i, j):
            ii=i
            jj=j
            while i>=0:
                if dp[i][j] == 'Q':
                    return False
                i-=1
            i,j=ii,jj
            while i>=0 and j>=0:
                if dp[i][j] == 'Q':
                    return False
                i-=1
                j-=1
            i, j = ii, jj
            while i>=0 and j<n:
                if dp[i][j] == 'Q':
                    return False
                i-=1
                j+=1
            return True

        # write code here
        dp = [['.'] * n for _ in range(n)]
        self.res = 0
        dfs(0, 0, n)
        return self.res