- 分类：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相比难一些，这个要输出棋盘
