[DFS]52. N-Queens II

• 分类：DFS
• 时间复杂度: O(n^2)

52. N-Queens II

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

N-Queen II

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4

Output: 2

Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.

[

 [".Q..", // Solution 1

 "...Q",

 "Q...",

 "..Q."],

 ["..Q.", // Solution 2

 "Q...",

 "...Q",

 ".Q.."]

]

代码：

方法:

class Solution:

    res=0
    
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.res=0
        if n==0:
            return res
        col=[True for i in range(n)]
        diag1=[True for i in range(2*n-1)]
        diag2=[True for i in range(2*n-1)]
        self.n_queens(0,n,col,diag1,diag2)
        return self.res

    def n_queens(self,y,n,col,diag1,diag2):
        if y==n:
            self.res+=1
            return
        for x in range(n):
            if not self.valid(x,y,n,col,diag1,diag2):
                continue
            self.updateBoard(x,y,n,False,col,diag1,diag2)
            self.n_queens(y+1,n,col,diag1,diag2)
            self.updateBoard(x,y,n,True,col,diag1,diag2)

    def updateBoard(self,x,y,n,isPut,col,diag1,diag2):
        col[x]=isPut
        diag1[x+y]=isPut
        diag2[x-y+(n-1)]=isPut

    def valid(self,x,y,n,col,diag1,diag2):
        return col[x] and diag1[x+y] and diag2[x-y+(n-1)]

---

讨论：

1.一道经典DFS题，我还是觉得自己有些智障的捋不清orz