52.md

N Queens ii

Description

link

---

Solution

See Code or pro 51

Code

Complexity T : O(n ^ 2)

class Solution:
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.res = 0
        
        def dfs(queens, xy_dif, xy_sum):
            p = len(queens)
            if p == n:
                self.res += 1
            for q in range(n):
                if q not in queens and p - q not in xy_dif and p + q not in xy_sum:
                    dfs(queens + [q], xy_dif + [p - q], xy_sum + [p + q])
        
        dfs([],[],[])
        return self.res