[DFS]51. N-Queens

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

51. N-Queens

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:
    
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        res=[]
        
        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)]
        board=[["." for i in range(n)] for i in range(n)]
        
        self.n_queen(0,n,col,diag1,diag2,board,res)
        
        return res
        
    def n_queen(self,y,n,col,diag1,diag2,board,res):
        
        #出口
        if y==n:
            board_=[]
            for i in range(n):
                board_.append("".join(board[i]))              
            res.append(board_.copy())
            return
            
        for x in range(n):
            if not self.is_valid(x,y,n,col,diag1,diag2):
                continue
                
            self.updateBoard(x,y,n,col,diag1,diag2,board,False)
            self.n_queen(y+1,n,col,diag1,diag2,board,res)
            self.updateBoard(x,y,n,col,diag1,diag2,board,True)
            
    def is_valid(self,x,y,n,col,diag1,diag2):
        return col[x] and diag1[x+y] and diag2[x-y+(n-1)]
    
    def updateBoard(self,x,y,n,col,diag1,diag2,board,isPut):
        col[x]=isPut
        diag1[x+y]=isPut
        diag2[x-y+(n-1)]=isPut
        if isPut:
            board[x][y]='.'
        else:
            board[x][y]='Q'

---

讨论：

1.一道经典DFS题，和52相比难一些，这个要输出棋盘